遞歸原來可以so easy|-連載（2）
一個簡單的例子
下面用一個簡單的例子來演示遞進和回歸。
public class Hello {
static int s=1;
static void rd(int n){
System.out.format("%d 遞進，n:%d
",s++,n);
if(n==1)
return;
else{
rd(n-1);
System.out.format("%d 回歸，n:%d
",s++,n);
}
}
public static void main(String[] args) {
int a=4;
rd(a);
}
}
程序運行結果：
用一個圖來描述遞進和回歸的過程：
斐波那契數列
斐波那契數列指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……，數學上，斐波納契數列以如下被以遞歸的方法定義：
F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>2，n∈N*）
這個數學公式本身就有遞歸的，因此，我們可以用遞歸來實現。
static int fib(int n){
int val;
if(n==0||n==1){
val=1;
}
else{
val=fib(n-1)+fib(n-2);
}
return val;
}
public static void main(String[] args) {
int a=10;
for(int i=0;i<=a;i++){
int f=fib(i);
System.out.print(f+" ");
}
}
最大不超過某個數的所有偶數
如果用循環來做，很直接就可以寫出來：
public static void main(String[] args) {
System.out.println("請輸入不超過某數的所有偶數：");
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
for(int i=2;i<=a;i+=2){
System.out.print(i+" ");
}
}
?
如果用遞歸來做呢？
讀者可以先先思考一下怎麼寫。
...................
?
public class Hello {
static int len=0; //偶數個數
static int[] all; //存放所有的偶數
?
static void evenNum(int n){
if(n<=0)
return;
if(n%2==0){
all[len]=n;
len++;
}
evenNum(--n);
}
public static void main(String[] args) {
System.out.println("請輸入不超過某數的所有偶數：");
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
int maxNum=a/2+1; //最多有多少個偶數
all=new int[maxNum];
evenNum(a);
for(int i=0;i<len;i++){
System.out.format("%d ",all[i]);
}
}
}
求年齡
問題描述
有5個人坐在一起，問第5個人多少歲？他說比第4個人大2歲。問第4個人歲數，他說比第3個人大2歲。問第3個人，又說比第2人大兩歲。問第2個人，說比第1個人大兩歲。最後 問第1個人，他說是10歲。請問第5個人多大？
解題
分析一下，可以發現遞推公式為： f(n)=2+f(n-1)。
可以用遞歸程序來解。
static int age(int n) {
if (n == 1)
return 10;
return 2 + age(--n);
}
?
public static void main(String[] args) {
int a = age(5);
System.out.println(a);
}
猴子喫桃子
問題描述
猴子第一天摘下N個桃子，當時就喫了一半，還不過癮，就又多喫了一個。第二天又將剩下的桃子喫掉一半，又多喫了一個。以後每天都喫前一天剩下的一半零一個。到第10天在想喫的時候就剩一個桃子了,問第一天共摘下來多少個桃子？並反向列印每天所剩桃子數。
解題
這個題目，要倒過來算：
今天有1個桃子，記為 f(0)=11天前的桃子數為 (今天的桃子數+1)2：f(1)= (f(0)+1)2 2天前的桃子數為 (1天前的桃子數+1)2：f(2)= (f(1)+1)2 …10天前的桃子數為 (9天前的桃子數+1)2：f(10)= (f(9)+1)2得到遞推公式為：f(n)= (1+f(n-1))*2
通過這個公式，可以計算任意天前的桃子數。
public class Hello {
static int day=10;
static int peach(int n){
int num;
if(n==1){
num=1;
}else{
num=(1+peach(n-1))*2;
}
System.out.format("第%2d天，桃子數：%d
",day-n+1,num);
return num;
}
public static void main(String[] args) {
int a=peach(day);
}
}
練習題
用遞歸逆序輸出一個包含整型數據的鏈表。
答案下期給出。
提示 自己實現一個鏈表類
源碼、更多資深講師相關課程資料、學習筆記請入羣後向管理員免費獲取，更有專業知識答疑解惑。入羣即送價值499元在線課程一份。
QQ羣號：560819979
敲門磚（驗證信息）：高山流水
推薦閱讀：
