[Tutor] A small (but long) introduction to recursion

[Danny Yoo]

On Wed, 25 Jul 2001, Kevin McCormick wrote:
> 
> I absolutely do not understand recursion. I took your example and tried
> to do some tracing, but I do not understand how the sum is stored or
> returned:
> 
> def addUpToNRecursive(n):
>     if n == 0: return 0
>     print n
>     return addUpToNRecursive(n-1) + n
> 
> x = addUpToNRecursive(10)
> print x


Try small cases first, not just because they are simpler to do, but
because they are a good way of understanding why the recursion works.  I
wouldn't go as far as 10 --- that's way too big of a number.  *grin*


Let's trace addUpToNRecursive(1):  n is not equal to zero, so we'll do the
inductive case:

    return addUpToNRecursive(0) + 1

Now to figure that one out, we need to know what addUpToNRecursive(0)
looks like.  However, that's our base case: we know that
addUpToNRecursive(0) is 0.  We end up with:

    return 0 + 1



Let's try the function for n == 2:  It's not the base case, so
addUpToNRecursive() will give back the value:

    return addUpToNRecursive(1) + 2

And now we're back to solving addUpToNRecursive(1).  We have a good
memory, and we know that addUpToNRecursive(1) is 1.  As it stands though,
addUpToNRecursive() needs to redo the work to compute
addUpToNRecursive(1).  The trace now looks something like this:

             addUpToNRecursive(2)
        addUpToNRecursive(1) + 2
   addUpToNRecursive(0) + 1  + 2
           0            + 1  + 2

And now it can finally start adding things up --- it couldn't do the
addition until it expands the whole sum out.
###


Recursion works because once we have a base case, the function can depend
on that case to make things work for more things.  addUpToNRecursive()  
works for 0, so it'll work for 1.  So now we know that it works for 0 and
1.  But since it works for 1, it'll work for 2.  Now we know that it works
for 0, 1, and 2.  But since it works for 2, it works for 3...


I'm not sure if that makes much sense yet: it works on a very different
principle than explicitly storing some a "sum" variable, so it's bound to
look very wacky at first.  If anything, I hope that this sort of thing
feels "magical": it really is a upside-down way of looking at something.  
I find it very neat, if impractical at times.  *grin*