函數(shù)遞歸

什么是遞歸

程序調(diào)用自身的編程技巧稱為遞歸（recursion）。遞歸作為一種算法在程序設(shè)計(jì)語言中廣泛應(yīng)用。一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復(fù)雜問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可以描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。遞歸的主要思考方式在于：把大事化小。

遞歸的兩個必要條件

• 存在限制條件，當(dāng)滿足這個限制條件的時候，遞歸便不再繼續(xù)。
• 每次遞歸調(diào)用之后越來越接近這個限制條件。

史上最簡單的遞歸

int main() {printf("hehe\n");main();return 0; }

運(yùn)行結(jié)果


什么是棧溢出呢？

我們的內(nèi)存分為棧區(qū)，堆區(qū)和靜態(tài)區(qū)。棧區(qū)存放局部變量和函數(shù)參數(shù)，堆區(qū)存放動態(tài)開辟的內(nèi)存，靜態(tài)區(qū)存放全據(jù)變量和Static修飾的變量。

代碼每調(diào)用一次函數(shù)就會在棧區(qū)為它分配新的空間，在函數(shù)遞歸的過程中每遞歸一次就在棧區(qū)開辟一份新空間。內(nèi)存是有限的，像上面那樣不停的遞歸main函數(shù)，總有溢出的那一刻。

題目：接受一個整型值（無符號），按照順序打印它的每一位。例如：輸入：123，輸出：1 2 3

void print(int n) {if (n > 9){print(n/10);}printf("%d ", n%10); }int main() {unsigned int num = 0;scanf("%d", &num);print(num);return 0; }

運(yùn)行結(jié)果


主函數(shù)調(diào)用print函數(shù)傳入?yún)?shù)123，123大于9，除法運(yùn)算后得12，12作為參數(shù)傳入新調(diào)用的print函數(shù)（這里內(nèi)存為新調(diào)用的print函數(shù)開辟了一個新的空間，所以我在旁邊復(fù)制了一遍print函數(shù)），12大于9，除法運(yùn)算后得1，1作為參數(shù)又傳入一個又新調(diào)用的print函數(shù)（這里內(nèi)存為新調(diào)用的print函數(shù)開辟了一個新的空間，我又復(fù)制了一遍），比較大小后小于9進(jìn)入printf函數(shù)，模運(yùn)算打印輸出1，這時返回到上一個復(fù)制的print函數(shù)，執(zhí)行printf函數(shù)，模運(yùn)算打印輸出2。返回到最初的print函數(shù)，模運(yùn)算打印輸出3。

題目：編寫函數(shù)不允許創(chuàng)建臨時變量，求字符串長度。

int my_strlen(char *str) {if (*str != '\0')return 1 + my_strlen(str + 1); //str+1地址加一elsereturn 0; }int main() {char arr[] = "bit";int len = my_strlen(arr); //arr是數(shù)組，數(shù)組傳參，傳過去的不是整個數(shù)組，而是首元素的地址printf("len =%d\n", len);return 0; }

運(yùn)行結(jié)果

遞歸與迭代

題目：求n的階乘（不考慮溢出）

迭代

int Fac1(int n) {int i = 0;int ret = 1;for (i = 1; i <= n; i++){ret *= i;}return ret; }int main() {int n = 0;int ret = 0;scanf("%d",&n);ret = Fac1(n);//循環(huán)的方式printf("%d\n",ret);return 0; }

運(yùn)行結(jié)果

遞歸

數(shù)學(xué)公式

int Fac2(int n) {if (n <= 1)return 1;elsereturn n * Fac2(n - 1); }int main() {int n = 0;int ret = 0;scanf_s("%d",&n);ret = Fac2(n);//循環(huán)的方式printf("%d\n",ret);return 0; }

題目：求第n個斐波那契數(shù)。（不考慮溢出）

遞歸

int Fib(int n) {if (n <=2)return 1;elsereturn Fib(n - 1) + Fib(n - 2); }int main() {int n = 0;int ret = 0;scanf("%d", &n);ret = Fib(n);printf("ret = %d\n", ret);return 0; }

但是我們發(fā)現(xiàn)有問題

• 在使用Fib這個函數(shù)的時候如果哦我們要計(jì)算第50個斐波那契數(shù)字的時候特別消耗時間。
• 使用Fib函數(shù)求10000的階乘（不考慮結(jié)果的正確性），程序會崩潰。

為什么？

我們發(fā)現(xiàn)Fib函數(shù)在調(diào)用的過程中很多計(jì)算其實(shí)在一直重復(fù)，我們把代碼改一下。

定義一個全局變量count來計(jì)算Fib函數(shù)運(yùn)行多少次。

int count = 0; int Fib(int n) {if (n == 3) //用if判斷循環(huán)多少次{count++;}if (n <=2)return 1;elsereturn Fib(n - 1) + Fib(n - 2); }int main() {int n = 0;int ret = 0;scanf("%d", &n);ret = Fib(n);printf("ret = %d\n", ret);printf("count = %d\n", count);return 0; }

運(yùn)行結(jié)果

我這電腦求第50個斐波那契數(shù)會崩潰，求第40個斐波那契數(shù)，調(diào)用Fib函數(shù)三千九百萬次。

我們改用迭代。

迭代

int Fib(int n) {int a = 1;int b = 1;int c = 1;while (n > 2){c = b + c;a = b;b = c;n--;}return c; } int main() {int n = 0;int ret = 0;scanf("%d", &n);ret = Fib(n);printf("ret = %d\n", ret);return 0; }

總結(jié)：

• 許多問題是以遞歸的形式進(jìn)行解釋的，這只是因?yàn)樗确沁f歸的形式更為清晰。
• 這些問題的迭代實(shí)現(xiàn)往往比遞歸實(shí)現(xiàn)效率更高，雖然代碼的可讀性稍微差些。
• 當(dāng)一個問題相當(dāng)復(fù)雜，難以用迭代實(shí)現(xiàn)時，此時遞歸實(shí)現(xiàn)的簡潔性便可以補(bǔ)償它所帶來的運(yùn)行時開銷。

下一節(jié)數(shù)組

總結(jié)

以上是生活随笔為你收集整理的C语言函数递归的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。