文章目錄
- 前言
- 一、什么是遞歸
- 二、遞歸的限制條件
- 三、遞歸舉例
- 1.求n的階乘
- 2. 舉例2：順序打印一個整數的每一位
- 四、遞歸的優劣
- 總結
前言
不多廢話了，直接開始。
一、什么是遞歸
遞歸是學習C語言函數繞不開的?個話題，那什么是遞歸呢？
遞歸其實是?種解決問題的方法，在C語言中，遞歸就是函數調用自己。
寫?個史上最簡單的C語言遞歸代碼：
#include <stdio.h>
int main()
{printf("hehe\n");main();//main函數中?調?了main函數return 0;
}
上述就是一個簡單的遞歸程序，只不過上面的遞歸只是為了演示遞歸的基本形式，不是為了解決問題，代碼最終也會陷入死遞歸，導致棧溢出（Stack overflow）。
遞歸的思想：
把一個大型復雜問題層層轉化為?個與原問題相似，但規模較小的子問題來求解；直到子問題不能再被拆分，遞歸就結束了。所以遞歸的思考方式就是把大事化小的過程。
遞歸中的遞就是遞推的意思，歸就是回歸的意思，接下來慢慢來體會。
二、遞歸的限制條件
遞歸在書寫的時候，有2個必要條件：
? 遞歸存在限制條件，當滿足這個限制條件的時候，遞歸便不再繼續。
? 每次遞歸調用之后越來越接近這個限制條件。
在下面的例子中，我們逐步體會這2個限制條件。
三、遞歸舉例
1.求n的階乘
計算n的階乘（不考慮溢出），n的階乘就是1~n的數字累積相乘。
分析和代碼實現:
我們知道n的階乘的公式： n！ = n ? (n ? 1)!
舉例：
5! = 5×4×3×2×1
4! = 4×3×2×1
所以:
5! = 5×4!
這樣的思路就是把?個較大的問題，轉換為?個與原問題相似，但規模較小的問題來求解的。
n!—> n*(n-1)!
(n-1)! —> (n-1)*(n-2)!
…
直到n是1或者0時，不再拆解
再稍微分析?下，當 n<=1 的時候，n的階乘是1，其余n的階乘都是可以通過上述公式計算。 n的階乘的遞歸公式如下：
那我們就可以寫出函數Fact求n的階乘，假設Fact(n)就是求n的階乘，那么Fact(n-1)就是求n-1的階乘，函數如下：
int Fact(int n)
{if(n<=0)return 1;elsereturn n*Fact(n-1);
}
測試：
#include <stdio.h>
int Fact(int n)
{if (n <= 0)return 1;elsereturn n * Fact(n - 1);
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fact(n);printf("%d\n", ret);return 0;
}
運行結果（這里不考慮n太大的情況，n太大存在溢出）：
畫圖推演：
2. 舉例2：順序打印一個整數的每一位
輸入?個整數m，打印這個按照順序打印整數的每?位。
比如：
輸入：1234 輸出：1 2 3 4
輸入：520 輸出：5 2 0
分析和代碼實現：
這個題目，放在我們面前，首先想到的是，怎么得到這個數的每一位呢？
如果n是?位數，n的每?位就是n自己
n是超過1位數的話，就得拆分每?位
1234%10就能得到4，然后1234/10得到123，這就相當于去掉了4
然后繼續對123%10，就得到了3，再除10去掉3，以此類推
不斷的 %10 和 \10 操作，直到1234的每一位都得到；
但是這里有個問題就是得到的數字順序是倒著的
但是我們有了靈感，我們發現其實?個數字的最低位是最容易得到的，通過%10就能得到那我們假設想寫?個函數Print來打印n的每?位，如下表示：
Print(n)
如果n是1234，那表示為
Print(1234) //打印1234的每?位
其中1234中的4可以通過%10得到，那么
Print(1234)就可以拆分為兩步：
- Print(1234/10) //打印123的每?位
- printf(1234%10) //打印4
完成上述2步，那就完成了1234每?位的打印
那么Print(123)?可以拆分為Print(123/10) + printf(123%10)
以此類推下去，就有
---- Print(1234)
==>Print(123) + printf(4)
==>Print(12) + printf(3)
==>Print(1) + printf(2)
==>printf(1)
直到被打印的數字變成?位數的時候，就不需要再拆分，遞歸結束。
代碼展示：
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;
}
輸入和輸出結果：
在這個解題的過程中，我們就是使用了大事化小的思路
把Print(1234) 打印1234每?位，拆解為首先Print(123)打印123的每?位，再打印得到的4
把Print(123) 打印123每?位，拆解為首先Print(12)打印12的每?位，再打印得到的3
直到Print打印的是?位數，直接打印就行。
畫圖推演：
四、遞歸的優劣
遞歸是?種很好的編程技巧，但它也有它的優點和缺點。
在C語言中每一次函數調用，都要需要為本次函數調用在棧區申請?塊內存空間來保存函數調用期間的各種局部變量的值，這塊空間被稱為運行時堆棧，或者函數棧幀。
函數不返回，函數對應的棧幀空間就?直占用，所以如果函數調用中存在遞歸調用的話，每?次遞歸函數調用都會開辟屬于自己的棧幀空間，直到函數遞歸不再繼續，開始回歸，才逐層釋放棧幀空間。
所以如果采用函數遞歸的方式完成代碼，遞歸層次太深，就會浪費太多的棧幀空間，也可能引起棧溢出（stack overflow）的問題。
如果用不了遞歸，一般通常用迭代（循環）的方法。
事實上，我們看到的許多問題是以遞歸的形式進行解釋的，這只是因為它比非遞歸的形式更加清晰， 但是這些問題的迭代實現往往比遞歸實現效率更高。
當?個問題非常復雜，難以使用迭代的方式實現時，此時遞歸實現的簡潔性便可以補償它所帶來的運行時開銷。
往期文章：c語言如何生成隨機數以及設置隨機數的范圍。（超詳細）
總結
碼字不易，點個關注和贊吧！！！
)
