反復は繰り返しよりも悪いですか？

Question

数日前、誰かが私に、再帰は繰り返しより優れていると言いました。可能であれば、常に使用するべきです。

私は再帰を経験し、簡単なプログラムを書いて数の階乗を得ることを試みました。

def fact(n): 
    if n == 1: 
     return 1 
    return n * fact(n - 1) 

と、これは正常に動作しますが、それはすぐにnは、だから私は正確に同じことを簡単な関数を書きましたが、for loopで997

上になるようRuntimeError: maximum recursion depth exceededを取得します。これは再帰です。

def fact(n): 
    a = 1 
    for x in range (0, n, 1): 
     a = a * (n - x) 
    return a 

それは150msの中に答えを与えるn < 10000ながら。

だから、おそらく再帰は少ない数値で速くなるが、そうではない。それは長い時間がかかる：

だから私の質問は次のとおりです。
Pythonでプログラムを書くときに、再帰を使用するには、まったく理由がありますか？
と：
再帰でしか解決できない問題はありますか？

Answer 1

明示的な再帰が解決しようとする必要は問題はありません。明示的な反復で解決する必要がある問題はありません。Church and Turing have provedは互換性があります。

しかし、コードがきれいで問題があり、再帰を使用すると推論しやすくなります。実際、Pythonの標準ライブラリ、さらにはCコード自体は、多くの場所で内部的に再帰を使用していますので、ネストされたタプルのreprを印刷例えば、多くの場所で恐ろしい再帰制限を打つの傾向がある：

>>> from functools import reduce 
>>> x = reduce(lambda x, y: (x,), range(10000)) 
>>> x # recursion limit hit in C code 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
RuntimeError: maximum recursion depth exceeded while getting the repr of a tuple 
>>> import pprint 
>>> pprint.pprint(x) # recursion limit hit in Python standard library code. 
Traceback (most recent call last): 
... 
    File "/usr/lib/python3.4/pprint.py", line 390, in _safe_repr 
    orepr, oreadable, orecur = _safe_repr(o, context, maxlevels, level) 
    File "/usr/lib/python3.4/pprint.py", line 340, in _safe_repr 
    if issubclass(typ, dict) and r is dict.__repr__: 
RuntimeError: maximum recursion depth exceeded while calling a Python object 

---

ステートマシンと中間引数のスタックを使用して、反復アルゴリズムを反復に変換することができます。なぜなら、それはCPUが再帰を実装するために行うものであるからです。

Answer 2

反復は一般的に（そしてこの場合も）より効果的です（同様の操作を実行していると仮定すると、パフォーマンスは向上します）。再帰には、リソースを必要とするたびに新しい関数呼び出しを行う必要があるため、オーバーヘッドが大きくなります。

https://en.wikipedia.org/wiki/Recursion_(computer_science)は

は、「再帰の力が明らかに有限の文でオブジェクトの無限集合 を定義する可能性にある」

が、ユースケースは非常にでなければならないであろうと言います再帰に特有のものがより良い選択となる。エラーについて

、Pythonのは、最大の再帰の深さが何であるかを返す関数が組み込まれています、あなたはこれが役立つはずです：https://docs.python.org/2/library/sys.html#sys.getrecursionlimit

Answer 3

私は速くなる伝えることはできませんが、再帰は間違いなくその場所にしていますプログラミング。例えば、一つの大きな大きなリストの中に、ネストされたリストを「フラット化」することになっている次の関数、考えてみます。

def expand_list(lst): 
    result = [] 
    for element in lst: 
     if isinstance(element, list): 
      result += expand_list(element) 
     else: 
      result.append(element) 
    return result 

を

反復を処理することができません（例：expand_list([1,2,3,[4,5,[6,7]]])が[1,2,3,4,5,6,7]に評価されます）これは非常にうまい。

（サイドノート：機能上記と同じことを行うにはPythonでの関数があります - これは単なる例であった）