[Tutor] very elementary help ... for total analphabet [recursion!]

[Danny Yoo]

On Sun, 13 Jan 2002 mikalzet@libero.it wrote:

> The following code is taken from "Learning to think like a Computer
> Scientist with Python":

Hi mikalzet, nice to meet you.  Ok, let's take a look:


> class Node:
> 	def __init__(self, cargo=None, next=None):
> 		self.cargo=cargo
> 		self.next = next
> 	def __str__(self):
> 		return str(self.cargo)


Ah, I see, so this is a Node for a linked list.


> def printBackward(list):
>     if list == None: return
>     head = list
>     tail = list.next
>     printBackward(tail)
>     print head,

Ah, a recursive definition!  This stuff is actually not "elementary".  
That is, it's not particularly "hard", but it is demented and strange
enough that you may need to see some concrete examples of it in action
before it starts making some sense.


> Now for the question: I have tried to look at the stack diagram and
> I've tried adding print head and print tail commands in various points
> of printBackward to see how it works. It seems that:
> 
> head = 1 tail = 2
> then head = 2 tail = 3
> then head = 3 tail = None.
> now the 'return' makes the loop exit and "print head" is executed.
> 
> (And this already puzzles me, I would have thought return to cause the
> whole printBackward() to terminate - therefore no output at all).
>
> This granted, I would expect as output
> 3
> 
> What happens here ?
> 


printBackward() is a 'recursive' definition, so it'll feel a little
backwards at first.  Let's detail the trace a little more, and it might
make more sense:


###
In evaluating printBackward([node1, node2, node3]):
    head = node1, tail = node2
    We need to evaluate printBackward([node2, node3]).

    In evaluating printBackward([node2, node3]):
        head = node2, tail = node3
        We need to evaluate printBackward([node3]).

        In evaluating printBackward([node3]):
            head = node3, tail = None
            We need to evaluate printBackward(None)

            In evaluating printBackward(None):
                We hit the base case, so we return without doing anything.

            Print head, which is node3.  Return.

        Print head, which is node2.  Return.

    Print head, which is node1.  Return.
###

I'm using indentation here to emphasize the fact that printBackward() is
calling other helper functions, and can continue on only after the helper
is done.  The strange part is that printBackward() is using itself to help
itself.  *grin*

Let's take a look at the definition again:

###
> def printBackward(list):
>     if list == None: return
>     head = list
>     tail = list.next
>     printBackward(tail)
>     print head,
###


Tracing recursive functions can be a little tedious.  It might be easier
to think of it this way:

    Recursion depends on the fact that the function works on small
    things, and can use itself on smaller things to do the right thing.  
    *grin*

Pretend for the moment that printBackward() works --- that is, let's
imagine that if we give it a list like [2, 3], it will go off and print:

###
3
2
###

If this works, then to printBackward() of [1, 2, 3], what we can do is say
"Ok, we can pretend that printBackward() will work on a smaller chunk of
this list.  Let's tell printBackward() to do its work on the tail of our
list, and then print out the head.  If we do that, then we end up printing
the list in backwards order."




Here's another example of a recursive function: let's say that we had a
linked list of numbers, and we wanted to add them all together to get
their sum.  How can we do this?

###
def getSum(list):
    ## Base case --- if we're given no numbers, then their sum
    ## must be zero.

    if list == None:
        return 0

    first, rest = list, list.next

    ## Otherwise, we can getSum() of the rest of the numbers, and add
    ## the first number to that.
    return first + getSum(rest)
###



> "print head" seems to be executed several times ( why ?) printing the
> succession of values attributed to head in a first-in-last-out manner, as
> if it were a stack .... ?

There is a stack involved, and it's one that Python maintains to keep 
track of function calls.  When functions call other functions, the called
function needs to "return" back to its caller.  In a concrete example:

###
def square(x):
    return x * x

def hypotenuse(a, b):
    return math.sqrt(square(x) + square(y))
###

The hypotenuse function calls on square(x) to do it's work.  square()
itself does its thing, and then passes that result back to its caller.  
And that's where a stack is involved.


We can break down square() like this:

###
def square(x):
    return multiply(x, x)

def multiply(a, b):
    if b == 0: return 0
    return a + multiply(a, b-1)
###

Hey look!  The multiply() function here is itself "recursive", and it's
probably something you've seen in elementary school:

    a * b = a * 1 + a * (b-1)

The big thing about recursion is that you probably already have some
experience with it in the real world, but you just need to recognize it as
"recursion".  Think about russian dolls, and how they are layered within
each other.  Or the poster of the movie "Memento", with photo images
embedded within photo images.


Please feel free to ask more questions on this; recursion is a lot of fun
to talk about.  Anyway, hope this helps!