Iterative vs. Recursive coding

[Steven D'Aprano]

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