# Combinations and recursion, from an ASPN snippet

Mike Meyer mwm at mired.org
Thu Mar 20 15:51:17 CET 2003

```Andy Jewell <andy at wild-flower.co.uk> writes:
> I like to think of recursion as 'nesting' calls to the function, one inside
> the other:
>
> 1
>   \
>     2
>       \
>         3
>           \
>            4
>              \
>               :
>              /
>            4
>           /
>         3
>       /
>     2
>    /
> 1

[...]

> Hope this helps.  The best way to learn recursion is to play with it.  Use
> print statements liberally, and limit the recursion depth to a reasonable
> amount while you're at it - it's very hard to see what's going on when your
> program dumps 10 pages of output on the screen!

Combining these two things can be really useful. Keep a recursion
counter, and print spaces to indicate the depth of the recursion:

def recursive_add(m, n, depth = 0):
print "  " * depth, m, n
if m < 0:
elif m == 0:
return n
else:
return recursive_add(m - 1, n + 1, depth + 1)

Also, to get real headaches, look up ackerman's function. It's an
interesting demonstration of the power of recursion.

<mike
--
Mike Meyer <mwm at mired.org>			http://www.mired.org/home/mwm/