Pythonプログラミングトレーニング1:Fibonacci

ターゲット:n番目のフィボナッチ額を返す
f i b ( n ) = { 0 , i f   n = 0 1 , i f   n = 1 f i b ( n − 1 ) + f i b ( n − 2 ) , i f   n > 1 fib(n)=\begin{cases} 0, & if\n = 0\\1, & if\n = 1\\fib(n-1) + fib(n-2), & if\n > 1\end{cases} fib(n)=⎩⎪⎨⎪⎧​0,1,fib(n−1)+fib(n−2),​if n=0if n=1if n>1​
ヒントヒント:再帰:操作の繰り返し:レイヤごとに呼び出され、操作が1回行われます.
送信形式:

def fib(n):
	...

print(fib(1))
print(fib(6))

解決策

def fib(n):
	if n==0:
		return 0
	elif n==1:
		return 1
	else:
		return fib(n-1) + fib(n-2)

>>> fib(5)
5
>>> fib(6)
8
>>> fib(2)
1
>>> fib(3)
2
>>> 

テスト結果

def testFib(f,n):
	a = []
	for i in range(n):
		a.append(f(i))
	return a

>>> testFib(fib,10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
>>>