目錄
1，什麼是遞歸
1.1，遞歸與循環的差別
2，遞歸函數執行個體
2.1，Fibonacci sequence（斐波那契數列）
2.2，Collatz sequence
1，什麼是遞歸
遞歸最初給我的感覺就是循環嵌套調用（并不準确），對于遞歸這種思想，可以從遞歸函數來了解。先來看看遞歸函數的定義：
程式設計語言中，函數Func(Type a,……)直接或間接調用函數本身，則該函數稱為遞歸函數。
在數學上，關于遞歸函數的定義如下：對于某一函數f(x)，其定義域是集合A，那麼若對于A集合中的某一個值X0，其函數值f(x0)由f(f(x0))決定，那麼就稱f(x)為遞歸函數。
1.1，遞歸與循環，疊代的差別
注意上文紅字【調用函數本身】，遞歸思想也有循環，但與循環有所差別，兩種的差別我個人了解如下：
【遞歸】：需要求一個遞歸函數的值，就要調用這個遞歸函數，調用遞歸函數後又要調用遞歸函數......直到最後的遞歸函數得到一個确定的值。這時候就需要逆序，可以得到倒數第二個遞歸函數的值，然後得到倒數第三個遞歸函數的值......最後就能得到你最初始想要求的遞歸函數的值。
【循環】：循環得到一個值時(比如1+2+...+10)，這樣需要慢慢兩個數相加，但加到最後時就可以直接得到結果了（死循環例外），就結束了循環。
【疊代】：重複回報過程的活動，其目的通常是為了接近或達到所學的目标或結果
2，遞歸函數執行個體
下面通過兩個遞歸執行個體來更好的了解遞歸的思想。
2.1，Fibonacci sequence（斐波那契數列）
斐波那契數列（Fibonacci sequence），又稱黃金分割數列、因數學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……
在數學上，斐波那契數列以如下被以遞推的方法定義：F(1)=1，F(2)=1, F(n)=F(n-1) + F(n-2)（n>=3，n∈N*）
【遞歸實作】
def fib(x):
if x <2:
return 0 if x==0 else 1
else:
return fib(x - 1) + fib(x - 2)
print(fib(6))
上面的函數表明了一個數列：a0=0, a1=1, a2=1, a3= 2, a4=3, a5=5, a6=8......
執行後得到的結果如下:
【疊代實作】
def fib(x):
n1 = 1
n2 = 1
n3 = 1
while x-2 > 0:
n3 = n2 + n1
n1 = n2
n2 = n3
x -= 1
return n3
num = int(input('請輸入一個正整數：'))
print(fib(num))
結果如下：
疊代像在通過數列的遞推公式一步步計算，在資料很小的情況沒什麼影響，若是第50位，疊代很快給出結果，遞歸方式計算時間更長。通常來說，大量資料情況下，遞推方式更費時，占用記憶體。要合理使用疊代與遞歸。
2.2，Collatz sequence
編寫一個名為collatz()的函數，它有一個名為number 的參數。如果參數是偶數，那麼collatz()就列印出number// 2，并傳回該值。如果number 是奇數，collatz()就列印并傳回3 * number + 1。然後編寫一個程式，讓使用者輸入一個正整數，并不斷對這個數調用collatz()，直到函數傳回值１
def collatz(num):
if num == 1:
return 0
elif num%2 == 0:
print(num//2)
return collatz(num//2)
elif num%2 == 1:
print(3*num+1)
return collatz(3*num+1)
print('Enter number')
a=int(input())
print('The Collatz ')
collatz(a)
執行結果如下：