在 C 語言里，函數遞歸是一種函數調用自身的編程技術。下面開始逐一介紹。
一、什么是遞歸？
遞歸其實是?種解決問題的?法，在C語?中，遞歸就是函數??調???。
寫?個史上最簡單的C語?遞歸代碼：
#include <stdio.h>
int main()
{
?? ?printf("hehe\n");
?? ?main();//main函數中?調?了main函數
?? ?return 0;
}
int main()
{
?? ?printf("hehe\n");
?? ?main();//main函數中?調?了main函數
?? ?return 0;
}
上述就是?個簡單的遞歸程序，只不過上?的遞歸只是為了演?遞歸的基本形式，不是為了解決問
題，代碼最終也會陷?死遞歸，導致棧溢出（Stack overflow）。
1.遞歸的思想：
把?個?型復雜問題層層轉化為?個與原問題相似，但規模較?的?問題來求解；直到?問題不能再被拆分，遞歸就結束了。所以遞歸的思考?式就是把?事化?的過程。
遞歸中的遞就是遞推的意思，歸就是回歸的意思。
2.遞歸的限制條件
遞歸在書寫的時候，有2個必要條件：
遞歸存在限制條件，當滿?這個限制條件的時候，遞歸便不再繼續。
每次遞歸調?之后越來越接近這個限制條件。
二、遞歸舉例
1.求n的階乘
?個正整數的階乘（factorial）是所有?于及等于該數的正整數的積，并且0的階乘為1。
?然數n的階乘寫作 n!。
題?：計算n的階乘（不考慮溢出），n的階乘就是1~n的數字累積相乘。
1.1代碼的分析和實現
n的階乘的公式： n！ = n ? (n ? 1)!
舉例：
5!= 5 * 4 * 3 * 2 * 1
4!= 4 * 3 * 2 * 1
所以:5!= 5 * 4!
5!= 5 * 4 * 3 * 2 * 1
4!= 4 * 3 * 2 * 1
所以:5!= 5 * 4!
從這個公式不難看出：如何把?個較?的問題，轉換為?個與原問題相似，但規模較?的問題來求解的。
n的階乘和n-1的階乘是相似的問題，但是規模要少了n。有?種有特殊情況是：當 n==0 的時候，n的階乘是1，?其余n的階乘都是可以通過上?的公式計算。
這樣就可以寫出n的階乘的遞歸公式：
那我們就可以寫出函數Fact求n的階乘，假設Fact(n)就是求n的階乘，那么Fact(n-1)就是求n-1的階
乘，函數如下：
int Fact(int n)
{
?? ?if (n == 0)
?? ??? ?return 1;
?? ?else
?? ??? ?return n * Fact(n - 1);
}
{
?? ?if (n == 0)
?? ??? ?return 1;
?? ?else
?? ??? ?return n * Fact(n - 1);
}
測試：
#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;
}
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;
}
結果：
(這里不考慮n太大的情況，n太大容易溢出）
2.畫圖演練
2.1舉例
順序打印?個整數的每?位
輸??個整數m，按照順序打印整數的每?位。
?如：
輸?：1234 輸出：1 2 3 4
輸?：125 輸出：1 2 5
2.2代碼的分析和實現
拿到這個題目，我們需要想的第一件事就是如何得到每一位數。
如果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)就可以拆分為兩步：
1. Print(1234 / 10) //打印123的每?位
2. 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打印的是?位數，直接打印就?。
2.3畫圖演練
以1234每一位的打印來推演一下
三、遞歸與迭代
遞歸是?種很好的編程技巧，但是和很多技巧?樣，也是可能被誤?的，就像舉例1?樣，看到推導的公式，很容易就被寫成遞歸的形式：
int Fact(int n)
{
?? ?if (n == 0)
?? ??? ?return 1;
?? ?else
?? ??? ?return n * Fact(n - 1);
}
{
?? ?if (n == 0)
?? ??? ?return 1;
?? ?else
?? ??? ?return n * Fact(n - 1);
}
Fact函數是可以產?正確的結果，但是在遞歸函數調?的過程中涉及?些運?時的開銷。
在C語?中每?次函數調?，都需要為本次函數調?在內存的棧區，申請?塊內存空間來保存函數調?期間的各種局部變量的值，這塊空間被稱為運?時堆棧，或者函數棧幀。
函數不返回，函數對應的棧幀空間就?直占?，所以如果函數調?中存在遞歸調?的話，每?次遞歸函數調?都會開辟屬于??的棧幀空間，直到函數遞歸不再繼續，開始回歸，才逐層釋放棧幀空間。
所以如果采?函數遞歸的?式完成代碼，遞歸層次太深，就會浪費太多的棧幀空間，也可能引起棧溢出的問題。
所以如果不想使?遞歸，就得想其他的辦法，通常就是迭代的?式（通常就是循環的?式）。
?如：計算 n 的階乘，也是可以產?1~n的數字累計乘在?起的。
1.舉例
求第n個斐波那契數
以計算 factorial(5) 為例，執行過程如下：
factorial(5) 調用 5 * factorial(4)。
factorial(4) 調用 4 * factorial(3)。
factorial(3) 調用 3 * factorial(2)。
factorial(2) 調用 2 * factorial(1)。
factorial(1) 滿足基本情況，返回 1。
然后逐步回溯計算：
factorial(2) 返回 2 * 1 = 2。
factorial(3) 返回 3 * 2 = 6。
factorial(4) 返回 4 * 6 = 24。
factorial(5) 返回 5 * 24 = 120。
factorial(5) 調用 5 * factorial(4)。
factorial(4) 調用 4 * factorial(3)。
factorial(3) 調用 3 * factorial(2)。
factorial(2) 調用 2 * factorial(1)。
factorial(1) 滿足基本情況，返回 1。
然后逐步回溯計算：
factorial(2) 返回 2 * 1 = 2。
factorial(3) 返回 3 * 2 = 6。
factorial(4) 返回 4 * 6 = 24。
factorial(5) 返回 5 * 24 = 120。
由此可以看出，這里不適合使用遞歸，用迭代的方式效率更高。
遞歸的優缺點
優點：
代碼簡潔：遞歸可以讓代碼更加簡潔、易讀，尤其是處理一些具有遞歸結構的問題，如樹的遍歷、分治算法等。
易于理解：對于某些問題，遞歸的思路更貼合人類的思維方式，更容易設計和實現。
缺點：
性能問題：遞歸調用會頻繁地進行函數調用和返回操作，帶來額外的開銷，可能會導致性能下降。
棧溢出風險：如果遞歸深度過大，會導致棧空間耗盡，引發棧溢出錯誤。
注意事項
要確保遞歸函數包含基本情況，防止無限遞歸。
注意遞歸深度，避免棧溢出。在必要時，可以考慮使用迭代（循環）來替代遞歸。
優點：
代碼簡潔：遞歸可以讓代碼更加簡潔、易讀，尤其是處理一些具有遞歸結構的問題，如樹的遍歷、分治算法等。
易于理解：對于某些問題，遞歸的思路更貼合人類的思維方式，更容易設計和實現。
缺點：
性能問題：遞歸調用會頻繁地進行函數調用和返回操作，帶來額外的開銷，可能會導致性能下降。
棧溢出風險：如果遞歸深度過大，會導致棧空間耗盡，引發棧溢出錯誤。
注意事項
要確保遞歸函數包含基本情況，防止無限遞歸。
注意遞歸深度，避免棧溢出。在必要時，可以考慮使用迭代（循環）來替代遞歸。
迭代是指基于一個初始值，按照特定的規則反復執行一系列操作，每一次執行都會對前一次的結果進行更新，直到滿足某個終止條件為止。這個過程可以看作是對一個狀態不斷進行修改和演進的循環過程。
遞歸和迭代對比
執行效率：
迭代：通常情況下，迭代的執行效率相對較高，因為它避免了函數調用棧的頻繁操作，只是在循環結構內進行簡單的指令重復執行，減少了額外的開銷。
遞歸：遞歸由于不斷地進行函數調用和返回，會有一定的時間和空間開銷，尤其是在遞歸深度較大時，可能會出現棧溢出等性能問題。
代碼可讀性：
迭代：對于一些簡單邏輯，迭代代碼的結構清晰，易于理解和調試，直接通過循環條件和循環體就能明白代碼的執行流程。
遞歸：遞歸代碼在處理具有遞歸結構的問題（如樹的遍歷、分治算法等）時，代碼可能更簡潔，更符合人們對問題的分解式思考方式，但對于初學者或者復雜邏輯，理解起來可能有一定難度。
迭代：通常情況下，迭代的執行效率相對較高，因為它避免了函數調用棧的頻繁操作，只是在循環結構內進行簡單的指令重復執行，減少了額外的開銷。
遞歸：遞歸由于不斷地進行函數調用和返回，會有一定的時間和空間開銷，尤其是在遞歸深度較大時，可能會出現棧溢出等性能問題。
代碼可讀性：
迭代：對于一些簡單邏輯，迭代代碼的結構清晰，易于理解和調試，直接通過循環條件和循環體就能明白代碼的執行流程。
遞歸：遞歸代碼在處理具有遞歸結構的問題（如樹的遍歷、分治算法等）時，代碼可能更簡潔，更符合人們對問題的分解式思考方式，但對于初學者或者復雜邏輯，理解起來可能有一定難度。
迭代和遞歸各有優缺點，在實際編程中，需要根據問題的特點、性能要求和代碼的可讀性來選擇合適的方法。有時候，迭代和遞歸可以相互轉換，通過合理的設計和優化，可以提高代碼的性能和可維護性。
![[計算機網絡]數據鏈路層](http://pic.xiahunao.cn/[計算機網絡]數據鏈路層)
![[特殊字符]算法次元突破：螺旋矩陣的“能量解碼術” vs 超立方體的“維度折疊指南”](http://pic.xiahunao.cn/[特殊字符]算法次元突破：螺旋矩陣的“能量解碼術” vs 超立方體的“維度折疊指南”)
