[解決済み] テールリカーシオンフィボナッチ

質問

ループのない再帰的なフィボナッチ関数を O(n) で実行するにはどうしたらいいですか？

どのように解決するのですか？

通常、私はこのような宿題の答えを掲載することに反対なのですが、これまでに掲載されたものは、物事を複雑にしすぎているようです。上のコメントで言われているように、反復して行うように再帰を使って問題を解けばいいのです。

これがその反復解法だ。

def fib(n):
  a, b = 0, 1
  while n > 0:
    a, b = b, a+b
    n -= 1
  return a

以下は、同等の再帰的な解決策です。

def fib(n):
  def fib_help(a, b, n):
    return fib_help(b, a+b, n-1) if n > 0 else a
  return fib_help(0, 1, n)

どちらの場合も、実際にはFまでしか計算していないことに注意してください。 <サブ n+1 を返しますが、F _n を結果とします。これは、あなたが与えられた"ヒント"とうまく一致します。

じっくりと2つの解答を見比べて、同等であることを納得してほしい。反復解を同等の再帰解に変換する（またはその逆）方法を理解することは、良いスキルです。