C語言之遞歸

1.遞歸是什麼

1. 認識遞歸
   遞歸作為一種算法在程序設計語言中廣泛應用.
2. 遞歸的定義
   遞歸是指程序調用自身的過程，在數學和計算機科學中，遞歸指由一種或多種簡單的基本情況定義的一類對象或方法，並規定其他所有情況都能被還原為基本情況.

2.遞歸的條件

1. 子問題需要和原來的問題做相同的事，並且更加簡單.
2. 不能無限制的調用本身，必須要能夠結束.

3.遞歸的用途

1. 數據的定義是按照遞歸進行定義的.
2. 問題解決的辦法是按照遞歸的算法實現.
3. 數據的結構形式是遞歸定義的.

4.遞歸的要素

1. 遞歸的結束條件
   不管是在遞歸算法，還是在遞歸的函數調用過程中，遞歸都需要有一個結束條件，也就是遞歸出口。通常，在遞歸的結束時，我們能夠直接知道遞歸的結果。
2. 遞歸的等價關係式
   用數學表達式來進行表示，常見的離散形式是：
   f(x)=n+f(x-1）
   其中，n是一個常量，x-1最終會收斂成一個常量，然後結束遞歸。在遞歸算法和遞歸函數中，遞歸表達式是程序調用遞歸的方式。
3. 遞歸傳遞的參數
   在遞歸算法中，如上式所示，x就是遞歸需要傳遞的參數。在遞歸函數中，我們通常將遞歸封裝成一種函數，通過遞歸的關係式，將函數進行返回和調用，用來實現遞歸的過程。

5.遞歸的流程圖

如圖所示，是一個遞歸的過程，由初始狀態，通過不斷遞歸，達到狀態X，最後進入結束狀態，這就是一個遞歸的過程。

6.遞歸的實戰

def fact_resursion(n):               
	# 終止條件
    if n==1:
        return 1                                 #遞歸結束條件
    else:
        return n*fact_resursion(n-1) # 循環部分

print(fact_resursion(5))

1. 上述過程是一個通過遞歸實現N的階乘的函數，函數的結束條件是當N=1時。N！表示N*（N-1）* …* (1)的一個過程，不難發現在N的變化中，N一直實現N=N-1的操作，由此可以推導出遞歸的循環。

def fun(n):
	# 終止條件
    if n <=1:
        return n
    else:
        return fun(n-1) + fun(n-2) # 循環部分
print(fun(8))

2. 斐波那契數列 ，就是一個非常典型的遞歸調用過程。其具體數列為 0 1 1 2 3 5 8 13.通過歸納總結可以得出f(0)=0,f(1)=1,f(n)=f(n-2)+f(n-1),n>0這個規律.通過這個規律，我們可以利用遞歸的方式進行實現.

7.遞歸與循環

相同點：

1. 遞歸和循環的本質都是代碼的複用。
2. 遞歸和循環在理論上具有相同的計算能力（在可計算理論中，這兩種計算模型所計算的函數類是相同的）.
3. 遞歸可以看做是一種特殊的循環.
   不同點：
4. 遞歸需要通過程序和系統一起完成，而循環可以由程序單獨完成。
5. 遞歸的規模很小，受到系統工作棧大小的限制，而循環的規模很大，機會不會受到影響.
6. 遞歸的代碼更加簡單，容易理解，可讀性強，但是，遞歸佔用的內存空間比函數大，受到限制.

8.遞歸，循環，迭代

1. 從概念上講，遞歸就是指程序調用自身的編程思想，即一個函數調用本身；迭代是利用已知的變量值，根據遞推公式不斷演進得到變量新值得編程思想。簡單地説，遞歸是重複調用函數自身實現循環。迭代是函數內某段代碼實現循環.
2. 而迭代與普通循環的區別是：循環代碼中參與運算的變量同時是保存結果的變量，當前保存的結果作為下一次循環計算的初始值.
3. 迭代與普通循環的區別是：迭代時，循環代碼中參與運算的變量同時是保存結果的變量，當前保存的結果作為下一次循環計算的初始值.
   遞歸與普通循環的區別是：循環是有去無回，而遞歸則是有去有回(因為存在終止條件).
   在循環的次數較大的時候，迭代的效率明顯高於遞歸.

遞歸
int fib(int n){  
         if(n>1) return fib(n-1) + fib(n-2);  
         else return n; // n = 0, 1時給出recursion終止條件  
    }

迭代
int fib(int n){  
    int i, temp0, temp1, temp2;        
    if(n<=1) return n;  
    temp1 = 0;  
    temp2 = 1;  
    for(i = 2; i <= n; i++){  
        temp0 = temp1 + temp2;  
        temp2 = temp1;  
        temp1 = temp0;  
    }  
    return temp0;  
}

9總結

遞歸是一種特殊的循環，通過調用自身.在使用過程中，通常將遞歸封裝成一種函數進行使用.同時，遞歸需要考慮內存空間的分配.因此，在實際使用過程中，我們需要考慮遞歸的複雜度，遞歸的表達式以及遞歸的結束條件.