?各位CSDN的uu們大家好呀，今天將會給大家帶來關于C語言的函數遞歸的知識，這一塊知識理解起來稍微會比較難，需要多花點時間。

話不多說，讓我們開始今天的內容吧！

目錄

1.函數遞歸

1.1 什么是遞歸？

1.2 遞歸的兩個必要條件

1.3 遞歸實例練習

2.函數的迭代

2.1 什么是迭代

2.2 遞歸與迭代實例

2.2.1 求第n個斐波那契數

2.2.2?實現n的階乘

3.總結

---

1.函數遞歸

1.1 什么是遞歸？

遞歸是程序調用自身的一種編程技巧，也是在程序設計語言中被廣泛應用的一種算法，一個過程或函數在其定義或說明中有直接或間接調用自身的方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，這樣一來，只需少量的程序就可以描述出解題過程所需要的多次重復計算，大大減少程序的代碼量。

遞歸的思考方式：把大化小

1.2 遞歸的兩個必要條件

·在使用遞歸時一定要設定限制條件，當滿足這個限制條件時，遞歸就不再繼續；

·每次遞歸調用之后越來越接近這個限制條件。

1.3 遞歸實例練習

1.接收一個無符號整型值，按順序打印它的每一位

如：輸入1234 打印1 2 3 4

代碼實現如下：

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

我們來看一下輸入1234后的運行結果：

?

?可以看到，運行結果符合我們的需求。現在讓我們一起來閱讀這段代碼，看看函數的遞歸體現在哪里：

我們在main函數中用scanf對定義的num變量進行輸入賦值，并調用print函數，將num的值傳給print，完成了main函數的編寫，我們回到main函數前面(函數先聲明(定義)后使用)，開始print函數的實現；

這里print函數的實現通過畫圖給大家講解(很重要！！！)：

2.函數的迭代

2.1 什么是迭代

迭代是函數利用自身已有的變量來推算需要的新變量，和遞歸直接調用自身存在一定差異，二者在某些情況下是可以相互轉換的，同種情況下，這兩種方法優先考慮迭代，因為遞歸很容易造成棧溢出，下面就通過兩個實例來感受一下迭代與遞歸的差異。

2.2 遞歸與迭代實例

2.2.1 求第n個斐波那契數

斐波那契數列是一個特殊的數列，從第三項開始，每一項都是前兩項之和，

1,1,2,3,5,8,......,(n-2),(n-1),(n-2)+(n-1)

現在我們用遞歸的方法實現一下：

#include<stdio.h>
//遞歸實現求第n個斐波那契數
int fib(int n)
{if (n <= 2)return 1;elsereturn fib(n - 2) + fib(n - 1);
}int main()
{int n = 0;scanf("%d", &n);printf("%d", fib(n));return 0;
}

但事實上，用遞歸求第n個斐波那契數會出現很多重復的計算，我們可以通過畫圖來看一下：

假設我們要求第50個斐波那契數：?

那么就要調用fib函數求第49個和第48個，求第49個和第48個又要再調用fib函數求第48、47、46個，其中第47個還調用了兩次，越往下存在的重復計算越多，這樣即浪費內存空間，又可能造成棧溢出。

為了讓大家更清晰地感受到求第n個斐波那契數需要調用fib函數的次數，我們在原先代碼基礎上改進一下：

#include<stdio.h>
int count = 0;
int fib(int n)
{
//這里計算的是第三個斐波那契數被重復計算多少次if (n == 3)count++;if (n <= 2)return 1;elsereturn fib(n - 2) + fib(n - 1);
}int main()
{int n = 0;scanf("%d", &n);/*printf("%d\n", fib(n));*/printf("%d", count);return 0;
}

我們來求一下第40個斐波那契數，運行一下看看count的值是多少：

?可以看到，count的值高達39088169，也就是說第三個斐波那契數被重復計算了39088169次。

為了避免這種不必要的大量重復計算，我們采用了非遞歸的形式改進代碼，也就是迭代，代碼實現如下：

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

可以看到，在fib函數里，程序通過while循環不斷使用兩個已知變量求第三個需要的變量，這樣的方式要比直接調用函數自身(即遞歸)減少很多重復計算。

2.2.2?實現n的階乘

#include<stdio.h>//遞歸實現
int factorial(int n)
{if (n <= 1)return 1;elsereturn n * factorial(n - 1);
}//迭代實現
int  factorial(int n)
{int result = 1;while (n > 1){result *= n;n--;}return result;
}int main()
{int n = 0;scanf("%d", &n);printf("%d", factorial(n));return 0;
}

實現n的階乘和求第n個斐波那契數也是同樣的道理，uu們可以自行探究一下，用遞歸求n的階乘，會造成多少重復計算。

3.總結

我們要知道，系統分配給程序的空間是有限的，如果出現了死循環或者是死遞歸，就可能導致系統一直不停地開辟棧空間，最終耗盡棧空間，造成棧溢出的現象。

許多問題以遞歸的形式來解釋，會讓問題變得更清晰易懂，但這些問題的迭代實現往往要比遞歸實現效率更高，但同樣的，迭代實現的代碼理解起來沒有遞歸那么容易。

在能用迭代的情況下，盡量不用遞歸，除非該問題的迭代實現非常復雜，那么此時遞歸實現的簡潔性就足以彌補它運行時所產生的一系列問題。

這篇文章就到這里啦，關于遞歸與迭代的知識，還需要uu們多去找題練習，遞歸雖好，但不要經常用哦。

如果你覺得這篇文章對你有幫助的話，麻煩動動小手為我點個贊哦，你的喜歡就是我創作的動力！