遞迴 VS 迭代

遞迴跟迭代常被拿來一起比較
以生物學的角度來舉例，
遞迴就像自己的細胞DNA複製自己、生成自己，再複製自己、生成自己；
而迭代則是一代一代衍進的，如阿公生老爸、老爸生兒子、兒子生孫子

遞迴 (Recursive)

一開始學遞迴真的爆炸抽象

遞迴是自己call自己，自己執行完之後再執行自己
效率較差，但程式碼簡潔 可讀性佳

遞迴就是function函式

def abc():
    ...
    return abc()

以function來看，定義了一個結構或設計一套機制，
然後重複的使用這套機制或結構，以達成目的、解決問題。

迭代(Iteration)

效率較快，但可讀性、可改性較遞迴差

迭代就是for迴圈、list陣列

for i in range(1,5):
   ...

以for來看，定義了開始跟結束的條件，
程式在這樣的條件中執行。

以費氏數列來舉例

F(0) = 1
F(1) = 1
F(2) = F(1) + F(0)
F(3) = F(2) + F(1)
F(4) = F(3) + F(2)
…

遞迴寫法

def Fibonacc(i):
    if i == 0 or i == 1:
        return 1
    return Fibonacc(i-1) + Fibonacc(i-2)

因為每次都會call自己兩次(每執行一次就多開一個分支出去)
效率差到爆

以遞迴方式來算算F(36)所花費的時間，幾乎快要是算兩次F(35)的時間
快兩倍啊！ 兩倍

import time
start = time.time()
print("F(35):", Fibonacc(35))
end = time.time()
print("計算F(35) 程式花費:", end - start, "秒")

start = time.time()
print("F(36):", Fibonacc(36))
end = time.time()
print("計算F(36) 程式花費:", end - start, "秒")

迭代寫法

num1 = 1
num2 = 1

for i in range(1, 40):
    temp = num1 + num2
    num2 = num1
    num1 = temp

以迭代方式來算F(36)的時間則比F(35)再多上一咪咪 微不足道的時間而已

import time
start = time.time()

num1 = 1
num2 = 1

for i in range(1, 40):
    temp = num1 + num2
    num2 = num1
    num1 = temp
    print(temp)

end = time.time()
print("程式花費:", end - start, "秒")

遞迴VS迭代 可讀性與可改性

如果今天將費氏數列改為前三項相加

F(0) = 1
F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) + F(0)
F(4) = F(3) + F(2) + F(1)
…

遞迴

以遞回來看，只需更改兩個小地方

def Fibonacc(i):
    if i == 0 or i == 1 or i == 2:
        return 1
    return Fibonacc(i-1) + Fibonacc(i-2) + Fibonacc(i-3)

迭代

迭代要改動的程式碼則較多，
改完後多了一個變數、程式碼變長

num1 = 1
num2 = 1
num3 = 1

for i in range(1, 40):
    temp = num1 + num2 + num3
    num3 = num2
    num2 = num1
    num1 = temp