遞歸演算法經典實例c

⑴ 1-100用c語言的遞歸法求和

C語言遞歸求和演算法是一種簡潔而優雅的方法。以1至100的整數和為例，我們可以用遞歸函數輕松實現。遞歸函數的定義如下：

#include <stdio.h>
int sum(int n) {
if (n == 1) return 1;
else return n + sum(n - 1);
}

這個函數首先檢查輸入的整數n是否為1。如果是，則直接返回1。否則，它將n與sum(n-1)的結果相加，並返回這個值。這個過程會一直遞歸下去，直到n減少到1。

在主函數中，我們設置變數i為100，並調用sum(100)函數計算1到100的和。通過printf函數輸出結果：

int main(){
int i = 100;
printf("%d\n", sum(100));
return 0;
}

這段代碼通過遞歸調用實現了累加操作，逐步將1到100的整數相加。遞歸的本質在於利用函數自身來解決問題，而這里則是利用遞歸逐步逼近問題的最基礎情況。通過這樣的方法，我們可以解決一系列復雜的數學問題，而無需復雜的循環結構。

遞歸求和的效率如何呢？對於這個問題，我們需要考慮遞歸調用的次數。在這個例子中，我們需要調用sum函數100次，每次調用都會產生一次遞歸。雖然遞歸求和的代碼簡潔明了，但它可能會導致棧溢出，特別是在處理較大范圍的數字時。因此，在實際應用中，我們可能需要考慮使用迭代方法或其他更高效的演算法。

遞歸求和演算法展示了C語言的強大功能，同時也提醒我們，在選擇演算法時應考慮其適用性和效率。對於較小的范圍，遞歸求和可能是最優解，但在某些情況下，迭代方法可能更為合適。

⑵ C語言背包問題遞歸演算法

你學過數據結構了嗎？如果學過，那就比較好理解，該演算法的思路和求二叉樹的高度的演算法的思路是十分類似的。把取這i個物體看成i個階段，則該二叉樹有i+1層。其中空背包時為根結點，左孩子則為放棄了第1個物品後的背包，右孩子為選取了第1個物品後的背包。今後在對第i個物品進行選擇時，向左表示放棄，向右表示選取。則遞歸演算法可如下：
int fun(int s, int i, int n) //s傳入的是背包容量, i是進行第i個物品的選取，n為剩餘物品的件數
{
if(s == 0) return 有解；
else if(剩餘的每件物品都裝不進|| n == 0) return 無解；
L = fun(s, i + 1, n - 1); //放棄第i個物品，則下一步的背包容量仍為s，然後看其是否有解，(遞歸調用進入左子樹)
R = fun(s - wi, i + 1, n - 1); //選取第i個物品，則下一步的背包容量為s-wi，然後看其是否有解，(遞歸調用進入右子樹)
return (l, r); //綜合考慮左右兩邊，看哪邊是正解或都無解。其實應該返回 return (L||R);
}

⑶ C語言入門——遞歸(簡要講解+遞歸練習)

遞歸是一種程序設計技巧，即函數調用自身來解決問題，其核心概念是"遞去(遞推)+歸來(回推)"。遞歸的主要目的是通過簡化代碼來表達復雜的重復計算，優點在於代碼量相對較少，但其運行效率較低，因此在選擇演算法時應盡量避免遞歸，除非在沒有其他更優解的情況下。

讓我們通過實例來深入理解遞歸。首先，考慮斐波那契數列，其遞推公式為F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)（n≥2）。遞歸實現時，可以解決求第n項的問題，如輸入3時，輸出2。再者，遞歸也可以用於計算階乘，如輸入5時，輸出120，只需要理解n!的定義，即n!=n×(n-1)!，特別是對於0的階乘，定義為1。

另一個實例是列印一個整數的每一位，例如輸入13579，輸出為1 3 5 7 9。通過遞歸，我們可以將復雜的問題拆分為更小的部分，然後逐個解決。

以上是遞歸的基本概念和應用，希望對初學者有所幫助。如果你對這些內容有任何疑問或發現錯誤，歡迎交流和指正。