筆記
斐波那契數列
漢諾塔
有64個盤子，三根柱子（從左至右依次為x,y,z柱）。要求将這64個盤子從x移動到z上。
解決思想：
首先，将三根柱子依次分為起始柱，輔助柱和目标柱。在移動過程中，這三個柱子不是絕對不變的，而是會不斷改變的。(移動多個盤子時，先确定好是從哪個柱子移到哪個柱子，即先确定起始柱和目标柱，然後剩下的柱子作輔助柱)
把問題分為三個簡單步驟：1、将63個盤子從x借助z移動到y上（此時x:起始柱，y:目标柱，z:輔助柱）；
2、将最後一個盤子從x移動到z上；
3、将1中的63個盤子從y借助x移動到z上（此時x:輔助柱，y:起始柱，z:目标柱）。
那麼，第二個步驟顯然一步就可以完成，而第一、二步驟實際上又是兩個需要細分的問題，又可以各自分為三個簡單步驟：
問題一：将63個盤子從x（借助z）移動到y上：
1、将62個盤子從x借助y移動到z上；
2、将最後一個盤子從x移動到y上；
3、将1中的62個盤子從z借助x移動到y上。
問題二：将（1中的）63個盤子從y（借助x）移動到z上：
1、将62個盤子從y借助z移動到x上；
2、将最後一個盤子從y移動到z上；
3、将1中的62個盤子從x借助y移動到z上。
依此類推，可以不斷細分到隻移一個盤子的最簡單的情況。
代碼實作：
def hanoi(n,x,y,z):
#n為整型，x,y,z為字元(傳入的實參表示柱子的名字)(形參中的x,y,z分别對應起始，輔助，目标柱)
if n == 1:
print(x,'-->',z)
else:
hanoi(n-1,x,z,y)#将前n-1個盤子從x移動到y上
print(x,'-->',z)
hanoi(n-1,y,x,z)#将這n-1個盤子從y移動到z上
課後作業
動動手：
0. 使用遞歸編寫一個十進制轉換為二進制的函數（要求采用“取2取餘”的方式，結果與調用bin()一樣傳回字元串形式）。
def Dec2Bin(dec):
result = ''
if dec:
result = Dec2Bin(dec//2)
return result + str(dec%2)
else:
return result
1. 寫一個函數get_digits(n)，将參數n分解出每個位的數字并按順序存放到清單中。舉例：get_digits(12345) ==> [1, 2, 3, 4, 5]
def get_digits(n):
list1 = []
if n:
list1 = get_digits(n//10)
return list1.append(n%10)
else:
return list1
2. 還記得求回文字元串那道題嗎？現在讓你使用遞歸的方式來求解，親還能驕傲的說我可以嗎？
def is_palindrome(n, start, end):
if start > end:
return 1
else:
return is_palindrome(n, start+1, end-1) if n[start] == n[end] else 0
string = input('請輸入一串字元串：')
length = len(string)-1
if is_palindrome(string, 0, length):
print('\"%s\"是回文字元串!' % string)
else:
print('\"%s\"不是回文字元串!' % string)
3. 使用遞歸程式設計求解以下問題：
有5個人坐在一起，問第五個人多少歲？他說比第4個人大2歲。問第4個人歲數，他說比第3個人大2歲。問第三個人，又說比第2人大兩歲。問第2個人，說比第一個人大兩歲。最後問第一個人，他說是10歲。請問第五個人多大？
def age(n):
if n == 1:
return 10
else:
return age(n-1) + 2