フィボナッチ数列について

Question

前提

フィボナッチ数列のｎ番目の数字を計算する関数を再帰を用いずに定義したいです。
関数名：fibonacci_norec(n)

実現したいこと

非再帰のフィボナッチ数列関数を定義する。

発生している問題・エラーメッセージ

UnboundLocalError: local variable 'F_n' referenced before assignment

該当のソースコード

def fibonacci_norec(n):
    li = [1,1]
    c = 0
    if n == 1 or n == 2:
        F_n = 1
    else: 
        for i in range(2,n+1):
            k = li[c] + li[c+1]
            li.append(k)
            c += 1
            if c == n+1:
                F_n = li[n-1]
                break
    return F_n

試したこと

ローカル変数がなぜ割り当てられていないのか条件分岐の条件を変えて実行してみましたが、結局わからないです。

補足情報（FW/ツールのバージョンなど）

jupyter notebook

Comments

[Zuishin]

呼び出していないからでは？

[melian]

#if c == n+1:
if c == n-1:
　F_n = li[n-1]

[meg_]

引数に何を設定したときに質問のエラーが発生しましたか？関数を呼び出したコードも合わせて掲載してください。

Answer 1

この関数の定義だと、

            if c == n+1:
                F_n = li[n-1]
                break

この if 文が絶対に成立しません。その場合、 2より大きな値で呼んだときにF_n が未定義なのでエラーになります。
なぜ成立しないかは、5くらいの数のときに丁寧に追うとわかるでしょう。
ここは、

            if c == n-1:

とすべきです。

また、動かしてみるとわかりますが、数列の添字は1始まりで、配列の添字は0始まりで1違いますので、動かすと1つ多いのがわかるでしょう。

---

おまけ
思うに、単にインデックスを取るためにあるので、変数ｃは不要です。
代わりにインデックスとして、「i」を使います。

def fibonacci_norec(n):
    li = [1,1]
    if n == 1 or n == 2:
        F_n = 1
    else: 
        for i in range(2,n):
            k = li[i-2] + li[i-1]
            li.append(k)
            if i == n-1:
                F_n = li[n-1]
                break
    return F_n

---

おまけ2
さらに改良の余地があります。

• ループは最後まで回ると抜けるので、最後までまわった判定をするのは不要
• リストに結果をすべて残してありますが、目的の番目の値しか使わないのであれば、spoofy_dragonさんの回答のように最後の2つだけ取っておくので充分となります。 これは大きな値(百万番目とか)を計算したいときに影響あります。

Comments

[yasutin]

丁寧に回答していただき大変わかりやすかったです。ありがとうございました！

Answer 2

def fibonacci(n):
  a, b = 0, 1
  for i in range(n):
    a, b = b, a + b
  return a

上記の関数では、数列の最初の2つの数字を変数aとbに格納します。次に、for文を使って、n回繰り返します。そのとき、aとbの値を更新します。つまり、aにbの値、bにa + bの値を代入します。最後に、aの値を返します。