經典遞歸

漢諾塔問題

背景故事

傳說印度某間寺院有三根柱子，上串64個金盤。寺院里的僧侶依照一個古老的預言，以上述規則移動這些盤子；預言說當這些盤子移動完畢，世界就會滅亡。這個傳說叫做梵天寺之塔問題(Tower of Brahma puzzle)。但不知道是盧卡斯自創的這個傳說，還是他受他人啟發。

若傳說屬實，僧侶們需要 (2的64次方 ? 1) 步才能完成這個任務；若他們每秒可完成一個盤子的移動，就需要5845億年才能完成。整個宇宙現在也不過137億年。

游戲規則:

1.借助B柱子將A柱子上面的圓盤移動到C柱子

2.小圓盤上不能放大圓盤

3.在三根柱子之間一次只能移動一個圓盤

源碼(python實現):

def hanoi(n, a, buffer, c):

if(n == 1):

print(a,"--->",c)

return

hanoi(n-1, a, c, buffer)

hanoi(1, a, buffer, c)

hanoi(n-1, buffer, a, c)

def main():

n = int(input("請輸入漢諾塔銅盤的個數:"))

hanoi(n, "a", "b", "c")

if __name__ == "__main__":

main()

求斐波那契數列

背景故事:

在西方，最先研究這個數列的人是比薩的列奧那多(意大利人斐波那契Leonardo Fibonacci)，他描述兔子生長的數目時用上了這數列:

第一個月初有一對剛誕生的兔子

第二個月之后(第三個月初)它們可以生育

每月每對可生育的兔子會誕生下一對新兔子

兔子永不死去

假設在n月有兔子總共a對，n+1月總共有b對。在n+2月必定總共有a+b對：因為在n+2月的時候，前一月(n+1月)的b對兔子可以存留至第n+2月(在當月屬于新誕生的兔子尚不能生育)。而新生育出的兔子對數等于所有在n月就已存在的a對.

游戲規則:

費波那契數列由0和1開始，之后的費波那契系數就是由之前的兩數相加而得出

源碼(python實現):

def Fibonacci(num):

if num == 1 or num == 2:

return 1

elif num == 0:

return 0

else:

return Fibonacci(num-1) + Fibonacci(num - 2)

def main():

num = int(input("請輸入斐波那契的位數:"))

result = Fibonacci(num)

print("第%d位斐波那契數的值為%d"%(num, result))

if __name__ == "__main__":

main()

求階乘

一個正整數的階乘(factorial)是所有小于及等于該數的正整數的積，并且0的階乘為1

源碼(python實現):

def factorial(num):

if num == 1 or num == 0:

return 1

else:

return num *factorial(num-1)

def main():

num = int(input("請輸入需要求階乘的整數:"))

result = factorial(num)

print("%d的階乘為%d"%(num, result))

pass

if __name__ == "__main__":

main()