反復と再帰の比較と例

投稿者: Anonymous

反復と再帰の例は何ですか?繰り返しを使用するのが最善でいつ再帰を使用するのが最善かを知りた

解決

繰り返しと再帰の例

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)

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

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

ありません。

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

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

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

回答者: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *