Recursive

Fibonacii 費氏數列：1, 1, 2, 3, 5, 8, 13, 21,34, 55,89, 144,......

求第n項費氏數列及所需時間？

一、遞迴費時寫法：加入花費時間

import time

def fibonacci(n):

if n==0:

return 0

elif n==1 or n==2:

return 1

else:

return fibonacci(n-1)+fibonacci(n-2)

for i in range(0,101):

t1 = time.time()

print("fibonacci", i, "=", fibonacci(i))

t2 = time.time()

print("computation time =", t2-t1)

※越後面越費時※

二、迴圈省時寫法

import time

def fibDP(n):

fib = {}

fib[1] = 1

fib[2] = 1

for i in range(3,n+1,1):

fib[i] = fib[i-1] + fib[i-2]

return fib[n]

t1 = time.time()

for i in range(1,101):

print("fibonacci "+str(i)+"="+str(fibDP(i)))

t2 = time.time()

print("computation time = "+str(t2-t1))