再帰的関数についてです

Question

https://qiita.com/WestRiver/items/

上記URLより、

def fibonacci(num):
    if num <= 2:
        return 1

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


index = int(input("何番目の数値を求めますか？："))

result = fibonacci(index)

print(result)

上記コードの

    if num <= 2:
        return 1

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

がどうして、フィボナッチ数列として足されていくのかが
根本からわからないので、わかりやすく教えていただきたいです泣泣泣

宜しくお願い致します。

Answer 1

引数numに数値を与えた場合、関数に何が返すかを考えればわかりやすくなると思います。

num = 0 : fibonacci(0) = 1
num = 1 : fibonacci(1) = 1
num = 2 : fibonacci(2) = 1
num = 3 : fibonacci(3) = fibonacci(1) + fibonacci(2) = 1 + 1 = 2
num = 4 : fibonacci(4) = fibonacci(2) + fibonacci(3) = 1 + 2 = 3
num = 5 : fibonacci(5) = fibonacci(3) + fibonacci(4) = 2 + 3 = 5
num = 6 : fibonacci(6) = fibonacci(4) + fibonacci(5) = 3 + 5 = 8
num = 7 : fibonacci(7) = fibonacci(5) + fibonacci(6) = 5 + 8 = 13
num = 8 : fibonacci(8) = fibonacci(6) + fibonacci(7) = 8 + 13 = 21

※num=0時は0を返すべきだとおもいますが・・・

Answer 2

「直前2つを足していく」というフィボナッチ数列の定義をコードに起こしたものですが、最初は「直前2つ」が取れないので1に固定している、というだけです。

何が理解できないのか、もう少し具体的に書いていただけませんでしょうか。

Comments

[ttoo]

例えばnum=5だとして、そのあとのreturn の動きが分からないです。
「直前の二つが１なのでnumが１、０になれば１になる」というのはわかるのですが。
フィボナッチ数列がどういうものかは理解しているのですが、このpythoコードにおいての、流れが分からないです。泣

[maisumakun]

難しく考える必要はありません。このコードでは引数にしかアクセスしていませんので、returnに書いてあるfibonacciの呼び出しは「たまたま同じ名前のメソッドを呼び出している」と考えてください。

再帰呼び出ししても実行ごとにnumは別々な変数となりますので、再帰呼び出ししたことで思わぬ動作になることはありません。