53619


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

[code]

    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
    
[/code]

例えば`fib(2)`の時は、`A = fib
(2-1)`となって再帰的に`fib(1)`が呼び出されて[0,1]が返されるのは理解できるのですが、`fib(3)`以降にどうやって配列の要素が増えているのかわからないです。

コード上には返り値として[0,1]か[0]しかなく、returnの部分の動作もリストの要素の足し算なのか連結なのかわからないです。

[可視化](http://www.pythontutor.com/visualize.html#mode=display)してみても、以下の状態での[0,1]から[0,1,1]になる処理がどのように行われているのか理解できません。  
[![画像の説明をここに入力](https://i.stack.imgur.com/kzTgS.png)](https://i.stack.imgur.com/kzTgS.png)

fib(8)の時の結果

[code]

    [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]
    
[/code]


CC BY-SA 4.0
2019-03-21T07:52:49.280
53616
2019-03-21T14:58:09.120
2019-03-21T14:58:09.120
29826
question
python python3 アルゴリズム
再帰的な処理のトレースができずコードの理解ができない


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

この関数はフィボナッチ数列のリストを返すものであるようです。  
[フィボナッチ数 -
Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0)

フィボナッチ数列では、`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のコードの動作についてですが、

[code]

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

これは、リスト`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 を追加したもの
> とありますが、どこで足し算をしているのでしょうか。
[code]

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

の部分になります。これは、前述した通り「リスト`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]`であり、以下のように処理されます。

[code]

    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] # リストの連結が行われた
    
[/code]

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


CC BY-SA 4.0
2019-03-21T10:28:44.033
53619
2019-03-21T12:54:36.347
2019-03-21T12:54:36.347
29826
29826
53616
answer