再帰的な処理のトレースができずコードの理解ができない
以下のようにリストを使った再帰的定義のフィボナッチ数列のコードを理解しようとしています。
def fib(n):
if n < 1:
return [0]
if n == 1:
return [0,1]
A = fib(n-1)
print(A)
return A + [A[-1] + A[-2]] #リストの最後尾は-1、最後尾の前-2
例えばfib(2)
の時は、A = fib (2-1)
となって再帰的にfib(1)
が呼び出されて[0,1]が返されるのは理解できるのですが、fib(3)
以降にどうやって配列の要素が増えているのかわからないです。
コード上には返り値として[0,1]か[0]しかなく、returnの部分の動作もリストの要素の足し算なのか連結なのかわからないです。
可視化してみても、以下の状態での[0,1]から[0,1,1]になる処理がどのように行われているのか理解できません。
fib(8)の時の結果
[0, 1]
[0, 1, 1]
[0, 1, 1, 2]
[0, 1, 1, 2, 3]
[0, 1, 1, 2, 3, 5]
[0, 1, 1, 2, 3, 5, 8]
[0, 1, 1, 2, 3, 5, 8, 13]
[0, 1, 1, 2, 3, 5, 8, 13, 21]