# EE資料結構#4 - Recursion & Dynamic Programming
## Recursion
Divide and Conquer 將問題往下切到基本容易的問題或降低size
可以用一樣的方式解完複雜問題
### Iterative 迭代 & Recursive 遞迴
疊代法(iterative method)是用迴圈去"循環重複程式碼的某些部分"來得到答案
遞迴法(recursive method)則是重複"呼叫自身程式碼"來得到答案
（python裡面可以直接再呼叫現在在執行的程式）
例1:加法
```
# Sum of list: Iterative version
def listsum(numList):
theSum = 0
for i in numList:
theSum = theSum + i
return theSum
print(listsum([1,3,5,7,9]))
```
```
# Sum of list: Recursive version
def listsum(numList):
if len(numList) == 1:
return numList[0] # Base case
else:
return numList[0] + listsum(numList[1:]) # Reduce problem size
print(listsum([1,3,5,7,9]))
```
例2:將10進位轉成n進位
每次做的事情都是除以n取餘數，慢慢往上疊，商繼續切，直到數比n小為止
最小的問題在最上面，類似stack frame(last in first out)
```
def toStr(n,base):
convertString = "0123456789ABCDEF"
if n < base:
return convertString[n]
else:
return toStr(n//base,base) + convertString[n%base]
print("%d (Base 10) = %s (Base %d)"%(10, toStr(10,2), 2))
print("%d (Base 10) = %s (Base %d)"%(12221, toStr(12221,16), 16))
```
10 (Base 10) = 1010 (Base 2)
12221 (Base 10) = 2FBD (Base 16)
## 遞迴經典問題
### 畫直角螺旋
畫大螺旋 = 走一段+轉直角+小一點的畫螺旋
```
import turtle
myTurtle = turtle.Turtle()
myWin = turtle.Screen()
def drawSpiral(myTurtle, lineLen):
if lineLen > 0:
myTurtle.forward(lineLen)
myTurtle.right(90)
drawSpiral(myTurtle,lineLen-5)
drawSpiral(myTurtle,100)
myWin.exitonclick()
```
turtle.Turtle()為畫圖工具
turtle.Screen()生成畫布
### Sierpinski Triangle
想法：先畫一個大三角形，中間畫一個倒三角形，然後再針對其他三角形做這件事（顏色更改）
```
import turtle
def drawTriangle(points,color,myTurtle):
myTurtle.fillcolor(color) #告知著色的顏色
myTurtle.up() #提起畫筆
myTurtle.goto(points[0][0],points[0][1])
myTurtle.down() #放下畫筆
myTurtle.begin_fill() #開始著色
myTurtle.goto(points[1][0],points[1][1])
myTurtle.goto(points[2][0],points[2][1])
myTurtle.goto(points[0][0],points[0][1])
myTurtle.end_fill()
def getMid(p1,p2):
return ( (p1[0]+p2[0]) / 2, (p1[1] + p2[1]) / 2)
def sierpinski(points,degree,myTurtle):
colormap = ['blue','red','green','white','yellow',
'violet','orange']
drawTriangle(points,colormap[degree],myTurtle)
if degree > 0:
sierpinski([points[0],
getMid(points[0], points[1]),
getMid(points[0], points[2])],
degree-1, myTurtle)
sierpinski([points[1],
getMid(points[0], points[1]),
getMid(points[1], points[2])],
degree-1, myTurtle)
sierpinski([points[2],
getMid(points[2], points[1]),
getMid(points[0], points[2])],
degree-1, myTurtle)
def main():
myTurtle = turtle.Turtle()
myTurtle.speed(1)
myWin = turtle.Screen()
myPoints = [[-100,-50],[0,100],[100,-50]]
sierpinski(myPoints,5,myTurtle)
myWin.exitonclick()
main()
```
### Draw Tree
往前走某距離
右轉20度畫一次 左轉40度畫一次(此時畫的數距離-6)
（這裡已經是遞迴，畫一次就是遞迴裡面的情況）
再右轉20度再回來
```
import turtle
def tree(branchLen,t):
if branchLen > 2:
t.forward(branchLen)
t.right(20)
tree(branchLen-6,t)
t.left(40)
tree(branchLen-6,t)
t.right(20)
t.backward(branchLen)
def main():
t = turtle.Turtle()
myWin = turtle.Screen()
t.left(90)
t.up()
t.backward(100)
t.down()
t.color("green")
tree(45,t)
myWin.exitonclick()
main()
```
### 河內塔
將n-1個盤子先從A移到B，把最下面盤子移到C，再把B的盤子移到C
其中n-1個盤子的問題就變成遞迴
```
def moveDisk(fp,tp):
print("moving disk from",fp,"to",tp)
def moveTower(height,fromPole, toPole, withPole):
if height >= 1:
moveTower(height-1,fromPole,withPole,toPole)
moveDisk(fromPole,toPole)
moveTower(height-1,withPole,toPole,fromPole)
moveTower(3,"A","B","C")
```
f(n) = 2f(n-1) +1
f(1) = 1
可解得f(n) = 2^n -1
## Dynamic Programming
Solve the small problems
Store the solutions
Use those solutions for larger problems
### 硬幣問題
給定所有幣值以及金額，找出最小幣數的方法
想法：假設是1,5,10,21,25,80湊成63
第一步可以是假設包含1或5或10或21或25
（80大於63所以不考慮）
剩下62或58或53或42或28，就變成了湊成這些金額的幣數再+1
再往下切，直到切到剛好是包含1或5或10或21或25則停止
（因為這樣就確定再多一種而已）
計算每個分支的幣數取最小值即可
```
def recMC(coinValueList,change):
minCoins = change
if change in coinValueList:
return 1
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recMC(coinValueList,change-i)
if numCoins < minCoins:
minCoins = numCoins
return minCoins
```
### 費氏數列
純遞迴的方法比較沒效率(黃金比例^n)
```
def recFB(n):
if n <= 1:
if n == 0:
return 1
elif n == 1:
return 1
elif n < 0:
return 0
return recFB(n-1) + recFB(n-2)
for k in range(10):
print("FB[%d]=%d"%(k,recFB(k)))
```
可以建表操作，以空間換取時間
不需要重算
如此的複雜度為n
```
def dpFB(FB_list,n):
FB_list[0] = 1
FB_list[1] = 1
for m in range(2,n+1):
FB_list[m] = FB_list[m-1] + FB_list[m-2]
return FB_list[n]
FB_list = [0]*10
for k in range(10):
print("FB[%d]=%d"%(k,dpFB(FB_list,k)))
```
## 複雜度分析
### 費氏
T(n) = T(n-1)+ T(n-2)+1
轉成
[T(n)+1] = [T(n-1)+1] + [T(n-2)+1]
f(n) = f(n-1)+f(n-2)
令f(n) = az1^n+bz1^n
代入f(n)遞迴式並比較係數
即可得到z1 z1為x^2-x-1=0之二根
再代入初始條件可解得a b
###### tags: `python` `資料結構`
Sign in with Wallet
Connect another wallet