4

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

1
  • 1
    タグに様々なプログラミング言語が列挙されていますが、これらに限定したご質問でしょうか? それとも、言語に依存しないご質問でしょうか? 「反復か再帰か」はプログラミング言語に依存します。
    – nekketsuuu
    Commented 2018年11月13日 12:38

2 件の回答 2

3

繰り返しと再帰の例

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)

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

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

ありません。

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

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

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

2

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

木を扱う場合。木はパーサや最適化問題などで登場します。

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

シーケンスを扱う場合。つまり配列、リスト、文字列などが該当します。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。