#遞回
是指函數/過程/子程式在執行過程式中直接或間接呼叫自身而產生的重入現象。在計算機程式設計裡，遞回指的是一個過程：函數不斷參照自身，直到參照的物件已知。使用遞回解決問題，思路清晰，程式碼少。但是在主流高階語言中（如C語言、Pascal語言等）使用遞回演算法要耗用更多的棧空間，所以在堆疊尺寸受限制時（如嵌入式系統或者內核態程式設計），應避免採用。所有的遞回演算法都可以改寫成與之等價的非遞回演算法。
（來源於百度，看不懂正常，術語就是不說人話）
###菲波那契數列：
斐波那契數列指的是這樣一個數列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368…數列從第3項開始，每一項都等於前兩項之和。
先上程式碼：
import datetime
def fib(n):
if n <2:
return n
else:
return fib(n -1) + fib(n -2)
if __name__ == '__main__':
n = int(input("請輸入一個正整數："))
time1 = datetime.datetime.now()
print(str(n)+"序列上數位爲：",fib(n))
time2 = datetime.datetime.now()
print("計算菲波那契數列鎖需要花費的時間。",time2-time1)
輸出：
請輸入一個正整數：3
3序列上數位爲： 2
計算菲波那契數列鎖需要花費的時間。 0:00:02.062182
明天繼續更新，加油！！！
遲到的更新
理解遞回思路，直接上程式碼
import datetime
def fib(n):
if n < 2:
print("f(" + str(n) + ")" + "=" + str(n),"遞回")
return n
else:
print("f(" + str(n) + ")=" + "f(" + str(n - 1) + ")" + " + f(" + str(n - 2) + ")");
r = fib(n -1) + fib(n -2)
print("f(" + str(n) + ")" + "=" + str(r))
return r
if __name__ == '__main__':
n = int(input("請輸入一個正整數："))
time1 = datetime.datetime.now()
print(str(n)+"序列上數位爲：",fib(n))
time2 = datetime.datetime.now()
print("計算菲波那契數列鎖需要花費的時間。",time2-time1)
輸出：
請輸入一個正整數：5
f(5)=f(4) + f(3)
f(4)=f(3) + f(2)
f(3)=f(2) + f(1)
f(2)=f(1) + f(0)
f(1)=1 s
f(0)=0 s
f(2)=1
f(1)=1 s
f(3)=2
f(2)=f(1) + f(0)
f(1)=1 s
f(0)=0 s
f(2)=1
f(4)=3
f(3)=f(2) + f(1)
f(2)=f(1) + f(0)
f(1)=1 s
f(0)=0 s
f(2)=1
f(1)=1 s
f(3)=2
f(5)=5
5序列上數位爲： 5
計算菲波那契數列鎖需要花費的時間。 0:00:00.000294
從上面的步驟我們可以清晰的看到遞回演算法的第一步是分治，把複雜的大的問題，給拆分成一個一個小問題，直到不能再拆解，通過退出條件retrun，然後再從最小的問題開始解決，只到所有的子問題解決完畢，那麼最終的大問題就迎刃而解。上面的列印資訊，符合棧數據結構的定義，先進後出，通過把所有的子問題壓棧之後，然後再一個個出棧，從最簡單的步驟計算，最終解決大問題，非常形象。
f(5) = f(4) + f(3)
f(4)=f(3) + f(2)
f(3)=f(2) + f(1)
f(2)=f(1) + f(0)
f(1)返回值自身爲１
f(0)返回值自身爲０
f(2) = f(1) + f(0) = 1
f(3)= f(2) + f(1)
f(1)返回值自身爲１
f(3) = 2
f(4)=f(3) + f(2)
f(2)=f(1) + f(0)
f(1)返回值自身爲１
f(0)返回值自身爲０
f(2) = 1
f(4) = 3
以此類推下去最終得到結果f(n)