50291


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


CC BY-SA 4.0
2018-11-13T10:15:20.807
50289
2019-01-13T01:16:59.013
30795
question
javascript python c++ c
反復と再帰の比較と例


# 繰り返しと再帰の例

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

## 繰り返しの場合

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

[code]

    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)
    
[/code]

## 再帰の場合

[code]

    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)
    
[/code]

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

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

ありません。

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

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

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


CC BY-SA 4.0
2018-11-13T10:38:32.883
50291
2018-11-25T04:50:27.480
2018-11-25T04:50:27.480
29826
29826
50289
answer


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

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

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

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


CC BY-SA 4.0
2019-01-13T01:16:59.013
51929
2019-01-13T01:16:59.013
31654
50289
answer