---

一、什么是遞歸？

在代碼運行中，有時候我們碰到冗長的代碼無法進行下筆進行編碼，這時候我們將會學習到應用函數遞歸進行運算。那么什么是遞歸呢?

1.1遞歸的思想

什么是函數遞歸？函數遞歸就是把大事化小，把小事在進行化小，直到解決問題。函數遞歸主要分為兩個過程一個叫遞推，一個叫回歸。

遞推主要是將大事簡化成一個個小事逐漸往下進行，回歸就是把最小的事情解決然后逐漸傳遞給上一個值進行回歸計算值，直到返回最初需要解決的問題。

1.2遞歸的限制條件

遞歸存在兩種限制條件 ：

1.遞歸存在限制條件， 遞推不能無限一直遞推下去，即遞推存在限制條件：什么時候進入遞歸，遞歸什么時候結束，遞歸存在進入遞歸的條件和遞歸的結束條件。只有滿足這個限制條件，遞歸將不會繼續遞歸下去。

為什么函數遞歸不能無限遞歸的原因

在這里我簡單寫了一個遞歸函數，內存中分為幾個不同的區域，在函數運行中產生的局部變量都會存放在內存中的棧區，接著我們看到函數，首先進入主函數main，然后我們會創建一個棧幀空間存儲main函數中的變量，然后代碼繼續運行下去我們調用test函數，調用test函數會開辟一個棧幀空間，在test函數中再次進行調用test函數就會出現如上圖一樣的情況，內存中的棧區也是有一定空間的，每次調用函數都會額外開辟一份空間，如果一直無限調用下去棧區將會溢出。

2.每次遞歸調?之后越來越接近這個限制條件

因為每次遞歸，相當于都是一次新的函數調用，而每次函數調用系統必須給該函數劃分棧幀空間，內部的遞歸函數沒有退出，上層的遞歸就不能退出，棧幀就會累積許多塊，如果累積超過棧的總大小，就會棧溢出。所以函數遞歸每次都需要逐漸的接近這個函數遞歸的停止條件，否則他就會無限一直遞歸下去。

---

提示：以下是本篇文章代碼部分，下面案例可供參考

二、遞歸案例

2.1 案例1：求n的階層

?個正整數的階乘（factorial）是所有?于及等于該數的正整數的積，并且0的階乘為1。
?然數n的階乘寫作n!。

題?：計算n的階乘（不考慮溢出），n的階乘就是1~n的數字累積相乘。

2.1.1分析

上面分析圖解中，我們就要有遞歸的思想：把一個較大的事情轉化為一個與原問題相似，但規模較小的問題進行求解。

當n==0的時候，n的階乘是1，其余的階乘都是可以用如上圖一樣的規律可以推出來的。

2.1.2 遞歸函數（Fact）的代碼實現

int Fact(int n)
{if(n==0)return 1;elsereturn n*Fact(n-1);
}

2.1.3 測試：main函數實現

#include <stdio.h>
int Fact(int n)  
{if(n==0)  return 1;  else  return n*Fact(n-1);  
}
int main()  
{int n = 0;  scanf("%d", &n);  int ret = Fact(n);  printf("%d\n", ret);  return 0;  
}

2.1.4 運行結果和畫圖推演

注意此處不考慮n太大，n太大會存在溢出的情況,因為這是一個整型變量，存儲的最大值65530

2.1.5 擴展：迭代方法求解n的階乘

#include<stdio.h>int Fact(int n)
{int i = 0;int sum = 1;for (i = 1; i <= n; i++){sum = sum * i;}return sum;
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fact(n);>   printf("%d\n", ret);   return 0;   
}

2.2 案例2：順序打印?個整數的每?位

題目：輸??個整數m，打印這個按照順序打印整數的每?位。
例如：

輸入1234，打印1 2 3 4
輸入4578，打印4 5 7 8

2.2.1分析

首先看到打印的第一步，我們想到的是怎么求出該數的每一位：
如果該數是一位數，那我們直接打印這一位即可。
如果該數超過一位數，那我們就得一個個求出該數的每一位。

假如我們要打印1234的每一位，我們得先求出他的每一位

1234 % 10 = 4，在這里我們得到了個位上的數4。 1234 / 10 = 123；
123 % 10 = 3, 在這里我們得到了十位上的數3。 123 / 10 = 12；
12 % 10 = 2，在這里我們得到了百位上的數2。 12 / 10 =1；
1 % 10 = 1 ，此時一位數我們直接打印即可。1 / 10 =0；由這里可以判斷結束遞歸的條件是該數大于9.
但是這里發現最先得到的是個位上的數，因此我們這里弄出一個函數print
print（1234） = print（123） + printf（4）；= print(1234/10) + printf(1234%10)
print(123) = print(12) + printf(3) + printf(4) ; = print(123/10) + printf(123%10)
print(12) = printf(1) + printf(2)+ printf(3) + printf(4) ;

2.2.2打印數（print)的每一位代碼實現

void Print(int n) voidPrint（國際）       
{if(n>9) 如果（n>9）       {Print(n/10); 打印（n/10）;       }printf("%d ", n%10); printf（“%d ”，n%10）;       
}

2.2.3 測試：print函數實現

#include<stdio.h>
void Print(int n)  
{if(n>9)  {Print(n/10);  }printf("%d ", n%10);  
}
int main()
{int m = 0;scanf("%d", &m);Print(m);return 0;
}

2.2.4 運行結果和畫圖推演

2.3 案例3：求第n個斐波那契數

題目：求第n個斐波那契數；

輸入： 5 輸出：5
輸入：10 輸出：55

2.3.1分析

有不知道什么叫斐波那契數列的同學可以百度搜索詳細了解一下，在這里小編就簡單給大家介紹一下什么叫斐波那契數列。斐波那契數第n個數等于前兩個數之和的相加，因此斐波那契數列第一第二個數都為1，以此推導剩下的斐波那契數：
1 1 2 3 5 8 13 21 34 55 。。。。
因此我們可以推導出求第n個斐波那契數的公式為：

2.3.2求第n個斐波那契數（fib) 的代碼實現

int fib(int n)
{if (n <= 2)return 1;elsereturn fib(n - 1) + fib(n - 2);
}

2.3.3 測試：fib函數實現

#include<stdio.h>
int fib(int n)
{if (n <= 2)return 1;elsereturn fib(n - 1) + fib(n - 2);
}
int main()
{int m = 0;scanf("%d", &m);int ret = fib(m);printf("%d ",ret);return 0;
}

2.2.4 運行結果和畫圖推演

2.1.5 擴展：迭代方法求解斐波那契數

在上面細心的人就會發現我們求解第50個斐波那契數，電腦突然間瘋狂的轉起來，但是始終等了很久也沒有得到第50個斐波那契數的值，這是為什么呢？

由上面的圖我們可以看出，當我們在進行遞歸運算的時候，他會重復計算很多的重復值，例如我們上面再遞歸求fib（49）需要求fib（48）和fib（47）；而我們求fib（48）又會求一次fib（47）和fib（46），這時隨著遞歸的層次原來越深，我們會發現我們會重復計算很多次重復的值，接下來我們計算一下算fib（3）一共計算了多少次。

#include<stdio.h>
int count = 0;
int fib(int n)
{if (n == 3)count++;if (n <= 2)return 1;elsereturn fib(n - 1) + fib(n - 2);
}
int main()
{int m = 0;scanf("%d", &m);int ret = fib(m);printf("%d\n",ret);printf("count = %d",count);return 0;
}

這時我們可以發現fib（3）重復計算了39088619次，這大大加大了計算機運行的難度，因此求解斐波那契數的時候遞歸求解是一個錯誤的選擇。因此我們可以直接采用迭代的求法。

#include<stdio.h>
int fib(int n)
{int a = 1; //開始時第一個斐波那契數int b = 1; //開始時第二個斐波那契數int c = 1; //返回求解的斐波那契數，因為如果n<=2返回1所以c的初始值為1while (n > 2){c = a + b;a = b; b = c; n--; }return c; 
}
int main() 
{int m = 0; scanf("%d", &m); int ret = fib(m); printf("%d\n",ret); return 0; 
}

2.4 案例4：遞歸實現n的k次方

模擬實現pow函數實現求解n的k次方

輸入：2 3 輸出：8
輸入：3 3 輸出：27

2.4.1分析

當k的值為0的時候，返回1；
當k的值為1的時候，返回n；
當k的值大于1的時候，返回n*mypow(k-1);
綜上：

2.4.2 mypow函數實現

int mypower(int k, int n)
{if (n == 0)return 1;else if(n >= 1)return k * mypower(k, n - 1);
}

2.4.3 測試：主函數實現mypow函數

int mypower(int k, int n)
{if (n == 0)return 1;else if(n >= 1)return k * mypower(k, n - 1);
}
int main()
{int k = 0;int n = 0;scanf("%d%d", &k, &n);int ret = mypower(k, n); printf("%d ", ret); return 0;  }

2.4.4 運行結果

---

總結

通過上面案例我們初步了解了函數遞歸的思想 ：把大事化小的特點。明白函數遞歸的充要條件是1，首先要有限制條件，即進入遞歸的條件和結束遞歸的條件。2，在函數遞歸的時候我們要逐漸的接近這個遞歸條件。
當然函數遞歸的學習遠不如于此，需要大家在不斷的實踐練習中不斷了解函數遞歸的妙用。這是小編對于函數遞歸的理解如果有讀者有看不懂的地方或者更好的建議歡迎評論下方留言。