3

以下のようにリストを使った再帰的定義のフィボナッチ数列のコードを理解しようとしています。

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]
5
  • returnがコメントアウトされているので、実行例のような結果は出ないはずです。質問の意図としては、コメントアウトされてる状態が正しい(この状態でなぜ動かないのかが知りたい)のか、コメントアウトされていない状態が正しい(実行例のような結果になる理由がわからない)のかどちらでしょうか。
    – suzukis
    Commented 2019年3月21日 8:36
  • ご指摘いただきましてありがとうございます。 コメントアウトを修正いたしました。 コメントアウトを実行できるような形にしてもコードを可視化できるページでは可視化することができず、依然としてfib(3)以降の遷移がわからないです。
    – user32568
    Commented 2019年3月21日 8:54
  • > 可視化することができず、依然としてfib(3)以降の遷移がわからない というのは、どのような意味でしょうか? 記載された内容でコードを可視化してみました が、最後まで正常に実行可能でした。
    – PicoSushi
    Commented 2019年3月21日 9:20
  • また、確認ですが、この質問はコード遷移を可視化するサイトが上手く動かないという質問でしょうか。それとも、記載されたコードの内容に分からない点があるという質問でしょうか。
    – PicoSushi
    Commented 2019年3月21日 9:22
  • 掲載いただいたURLからは可視化することができました。ありがとうございます。質問内容を修正いたします。 記載したコードの内容にわからない点があるという質問です。 その理解を補助するために可視化するサイトを記載しました。
    – user32568
    Commented 2019年3月21日 9:24

1 件の回答 1

1

以下の状態での[0,1]から[0,1,1]になる処理がどのように行われているのか理解できません。

この関数はフィボナッチ数列のリストを返すものであるようです。
フィボナッチ数 - Wikipedia

フィボナッチ数列では、F(n) 番目の値が F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n>=2) と定義された数列であり、この関数ではその要素までのリストを返すものになっています。このため、

  • F(1) では [0, 1]
    • F(0) から F(1) までの要素
  • F(2) では [0, 1, 1]
    • F(0) から F(1) までの要素に、 F(2) = F(0)+F(1) = 0+1 を追加したもの
  • F(3) では [0, 1, 1, 2]
    • F(0) から F(2) までの要素に、 F(2) = F(1)+F(2) = 1+1 を追加したもの

になっています。

また、 Pythonのコードの動作についてですが、

return A + [A[-1] + A[-2]] #リストの最後尾は-1、最後尾の前-2

これは、リストAとリスト[A[-1] + A[-2]]を連結する操作になっており、 A.append(A[-1] + A[-2]) と等価です。

追記 2019-03-21T21:26:20+09:00

F(0) から F(1) までの要素に、 F(2) = F(0)+F(1) = 0+1 を追加したもの とありますが、どこで足し算をしているのでしょうか。

return A + [A[-1] + A[-2]]

の部分になります。これは、前述した通り「リストAリスト[A[-1] + A[-2]] を連結する操作」ですが、リスト[A[-1] + A[-2]]とは「リストAの一番最後の要素(A[-1])とリストAの後ろから2番めの要素(A[-2])と足したもの」です。

A[-1] + A[-2]は連結ということは承知しましたが、そうなるとさらに、return [0]と[0,1]しか返り値がないのに、F(2)がどのように生成されたのかわかりません。

これは上記と関連して、 A[-1] + A[-2] は整数と整数を加算した結果、すなわち整数です。そして、これを[]で囲ったもの、すなわち[A[-1] + A[-2]]はリストになり、同じくリストであるAと加算したA + [A[-1] + A[-2]] もリストになります。

まとめると、以下のようになります。

  • A はリスト
  • A[-1]A[-2]A[-1] + A[-2]は整数
  • [A[-1] + A[-2]]A + [A[-1] + A[-2]] はリスト

さて、F(2)の場合ですが、fib(2)の場合はreturn A + [A[-1] + A[-2]]に渡されるA[0, 1]であり、以下のように処理されます。

return [0, 1] + [[0, 1][-1] + [0, 1][-2]] # A = [0, 1]を代入した
return [0, 1] + [1 + 0] # リストにアクセスした
return [0, 1] + [1] # 足し算が行われた
return [0, 1, 1] # リストの連結が行われた

というように、fib(2)では [0, 1, 1]が返されます。

3
  • ご回答いただきましてありがとうございます。F(0) から F(1) までの要素に、 F(2) = F(0)+F(1) = 0+1 を追加したもの とありますが、どこで足し算をしているのでしょうか。 A[-1] + A[-2]は連結ということは承知しましたが、そうなるとさらに、return [0]と[0,1]しか返り値がないのに、F(2)がどのように生成されたのかわかりません。
    – user32568
    Commented 2019年3月21日 12:27
  • @Nao 追記致しましたので、その部分をご確認ください。
    – PicoSushi
    Commented 2019年3月21日 12:55
  • 追記いただきましてありがとうございます。リストの連結と整数の足し算の部分が理解できておりませんでした。ご丁寧に解説いただきましてありがとうございました。
    – user32568
    Commented 2019年3月22日 0:30

この質問に回答するには、ログインする必要があります。