Skip to main content
4 / 4
Fix code
PicoSushi
  • 4,959
  • 1
  • 10
  • 28

繰り返しと再帰の例

pythonのタグがあったのでpythonでフィボナッチを書きます。

繰り返しの場合

append を使うと性能が良くないですが、わかりやすさのために使っています)

def fib_l(n):
    lst = []
    for i in range(n):
        if i==0:
            lst.append(0)
        elif i==1:
            lst.append(1)
        else:
            lst.append(lst[i-1]+lst[i-2])
    print(lst)
    return lst[n-1]+lst[n-2]

if __name__ == "__main__":
    fib_l(10)

再帰の場合

def fib_r(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib_r(n-1) + fib_r(n-2)

if __name__ == "__main__":
    fib_r(10)

繰り返しと再帰の使い分け

再帰を使うべきタイミング

ありません。

理由として、再帰の呼び出し階層が深くなった場合にスタック・オーバーフロー(このサイトではありません)が発生する可能性があるからです。実行系によっては末尾再帰の形にすると最適化により回避される可能性が有りますが、それに依存すべきではないと考えます。

繰り返しを使うべきタイミング

再帰の方が実装しやすい場合があるので、再帰でしか実装出来なかった場合以外全て。

PicoSushi
  • 4,959
  • 1
  • 10
  • 28