递归比迭代更差吗？

Question

几天前有人对我说,递归会比迭代更好,如果可能的话,应该总是使用.

所以,我进入递归并尝试编写一个简单的程序来获得一个数字的阶乘.这是递归:

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

虽然这样可以正常工作,但RuntimeError: maximum recursion depth exceeded只要n达到997以上就会得到.

所以我写了一个简单的函数,完全相同,但有一个for loop.

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

而n < 10000它在150毫秒内给出答案.

所以,我虽然可能递归速度较快,但数字较少,但不是.这需要更长时间:

所以我的问题是:
在Python中编写程序时是否有任何理由使用递归？
并且:
有任何问题只能通过递归来解决吗？

Answer 1

没有问题需要通过显式递归来解决; 并且没有任何问题需要通过显式迭代来解决 - Church和Turing已经证明它们是可以互换的.

但是,如果使用递归,则存在具有更简洁代码的问题,并且更容易推理.实际上,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实现递归.