Factorial

Factorial函數

• 此函數內部會呼叫自己

def factorial(x):
    if x == 1:
        return 1
    else:
        return (x * factorial(x-1))
factorial(5)        //5*4*3*2*1 = 120

動態規劃

• 在遞迴的時候,子問題常常被重複計算,造成時間浪費
• 動態規劃儲存子問題的結果於記憶體,不需要重複計算

//費氏數列Fibonacci(沒有用動態規劃)
def fibonacci(i):
    if i == 0 or i==1:
        return 1
    else
        return fibonacci((i-2) + fibonacci(i-1))
print(fibonacci(8))

//費氏數列Fibonacci(有用動態規劃)
def fibonacci(n):
    memo = [None] * (n+1)
    memo[0], memo[1] = 0,1
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n]
print(fibonacci(8))