Is recursion worse than iteration?

Question

A few days ago someone said to me that recursion would be better then iteration and should, if possible, always be used.

So, I dove into recursion and tried writing a simple program to get the factorial of a number. This is the recursion:

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

and although this works fine, it gets a RuntimeError: maximum recursion depth exceeded as soon as n gets above 997.

So I wrote a simple function that does exactly the same, but with a for loop.

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

while n < 10000 it gives the answer within 150ms.

So, I though maybe recursion is faster with low numbers, but nope. It takes longer:

So my question is:
Is there any reason at all to use recursion when writing programs in Python?
and:
Are there any problems that can only be solved with recursion?

Answer 1

There are no problems that need to be solved by explicit recursion; and there are no problems that need to be solved by explicit iteration - Church and Turing have proved that they're interchangeable.

However there are problems that have a neater code, and are easier to reason about if you use recursion. Indeed, Python standard library and even the C code itself uses recursion internally in many places and so is prone to hitting the dreaded recursion limit in many places, for example printing the repr of nested tuples:

>>> 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

---

You can always convert a recursive algorithm to an iteration with a state machine and stack of intermediate arguments, because after all that's pretty what a CPU does to implement recursion.

Answer 2

I can't tell which is faster, but recursion definitely has its place in programming. For example, consider the following function, which is supposed to "flatten" nested lists, into one great big list:

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

(E.g. expand_list([1,2,3,[4,5,[6,7]]]) evaluates to [1,2,3,4,5,6,7])

Iteration wouldn't be able to handle this very well.

(Side note: there are functions in Python to do the same as above function - this was just an example.)

Answer 3

Iteration is generally (and also in this case) more effective (performance wise, assuming you're performing similar operations). Recursion has more overhead since you have to make a new function call every time which costs resources.

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

"The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement"

but the use case would have to be very specific for recursion to be the better choice.

About the error, Python has a built in function which returns what the maximum recursion depth is, should you find this useful: https://docs.python.org/2/library/sys.html#sys.getrecursionlimit