# Iterative vs. Recursive coding

Steven D'Aprano steve at REMOVE-THIS-cybersource.com.au
Sat Aug 21 11:03:42 CEST 2010

```On Fri, 20 Aug 2010 16:42:26 -0700, Baba wrote:

> For future readers of this post who want to learn to programm (just like
> myself) let me re-state the basics i have learned now:

I would disagree in part with nearly all of these.

> - a procedure is said to be recursive when it contains a statement that
> calls itself

Not necessarily.

A function can be indirectly recursive -- function f can call function g
which calls function h which calls function f. This is still recursion,
even though f doesn't contain a statement which calls itself.

> - there must be a condition where the recursion has to stop otherwise
> the routine will continue to call itself infinitely.
>   This is called the Base Case

I agree with this, although I've never heard the name "Base Case" before.

> - every time the procedure calls itself the memory gradually fills up
> with the copies until the whole thing winds down again
> as the "return" statements start being executed.

That's so vague as to be almost meaningless. I think what you are talking
about is one specific part of memory, the calling stack, which fills up
with arguments needed to call the function, and then empties as the
recursive calls return.

However, there is an import class of recursive calls where a sufficiently
smart compiler can avoid this cost, essentially turning recursion into
iteration automatically, speeding up recursion drastically.

> - the above point means that a recursive approach is expensive on
> resources so in the practical world it should be avoided.

True-ish for the first part of the sentence, absolutely false for the
second.

Recursion can be slower and more memory consuming than iteration under
some circumstances, although this depends on the specific way that
recursion is used, not the mere fact that recursion happens. A single
recursive call is no more expensive than any other function call.

Also, as mentioned, some compilers can optimize tail-call recursion to
make it as fast and efficient as iteration. (However, Python doesn't do
this.)

In the real world, avoiding recursion also has costs. Your function may
be bigger, more complicated, need more memory, possibly manage its own
stack. None of these things happen for free. Whether a specific recursive
function is better than a specific iterative function depends on the
details of what that function does and what arguments you call it with.

If your recursive function is likely to use only a few recursive calls,
there is no need to complicate matters by re-writing it iteratively.
There's no need to avoid recursion just because it is recursive.

Also, recursion together with memoisation can be extremely fast and
efficient, at some cost of memory. For example, the typical recursive
version of factorisation:

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

can be made much, much faster by giving it a simple cache:

def fact(n):
try:
cache = fact.cache
except AttributeError:
cache = fact.cache = {}
try:
return cache[n]
except KeyError:
pass
if n <= 1:
result = 1
else:
result = n*fact(n-1)
# Don't let the cache grow indefinitely large.
if len(cache) >= 100:
cache.popitem()  # Discard some arbitrary item.
cache[n] = result
return result

--
Steven

```