[Tutor] Re: Recursion....what are the best situations to use it?

[jfouhy at paradise.net.nz]

Quoting "jsoares at Safe-mail.net" <jsoares at Safe-mail.net>:

> If this is too general a question, perhaps you can tell me when NOT to
> use recursion(where it would be inappropriate or inefficient).

In my opinion ---

Some problems are naturally recursive.  A good example is traversing data
structures (particularly trees), but there are other problems where there is an
obvious solution in terms of solving the same problem on smaller subinstances,
which obviously lends itself well to a recursive function.

In terms of efficiency: You should write your program first in the most obvious,
easy-to-understand way.  This may involve recursion if you are dealing with
naturally recursive data structures.  Then run your program and see if it's
slow.  If it is, try to figure out where the slowness is, either with profiling
or with theory.  If you conclude that your recursive function is slowing the
program down, then you can look to replace it with something else.

(I guess the traditional example of when it would be inappropriate is Pascall's
triangle --- ie: computing (n, r) == n!/(n-r)!r!.  The recursive algorithm looks
like this;

def C(n, r):
    """ Compute N choose R.

    Require:
        assert((type(n), type(r)) == (int, int))
        assert(n >= r)
        assert(r >= 0)
    """
    
    if r in (0, n):
        return 1
    else:
        return C(n-1, r-1) + C(n-1, r)

But if you do this, you end up computing a lot of values multiple times.  It
works better if you use an array to build up the answers from the bottom --- a
technique called dynamic programming. )

-- 
John.