[Tutor] Recursion help

[Gregor Lingl]

Justin Heath schrieb:

> I am working thru some of the examples in the "Learning to Program" 
> tutorial. I am going thru the recusrion section and have gotten stumped. 

Hi Justin,
one of the keypoints to understand recursion is understanding function
calls. Let's consider a very simple NONrecursive example:

 >>> def printitem(item):
    print item
  
 >>> def myfun():
    printitem("Hello world!")
    printitem("Wow!")
  
 >>> myfun()
Hello world!
Wow!
 >>>

Here we have defined two functions. The second one, myfun calls
the first one, printitem, twice, with different arguments.

You can make this visible, by inserting print statements, which give you 
information
about entering and exiting the execution af a function:

 >>> def printitem(item):
    print "printitem(", item, ") entered."
    print item
    print "prititem(", item, ") exited."

   
 >>> printitem("Hi!")
printitem( Hi! ) entered.
Hi!
prititem( Hi! ) exited.
 >>> def myfun():
    print "Myfun entered."
    printitem("Hello world!")
    printitem("Wow!")
    print "Myfun exited."

   
 >>> myfun()
Myfun entered.
printitem( Hello world! ) entered.
Hello world!
prititem( Hello world! ) exited.
printitem( Wow! ) entered.
Wow!
prititem( Wow! ) exited.
Myfun exited.
 >>>

Observe, that here you have the original output, but additionally
some "meta"-output, giving information about what's gong on

Now, what concerns recursion, the difference is mainly that
we have a function calling not another one but itself, with new arguments.

But you can make visible what's going on in the same way, by inserting
those print-statements for tracing execution: (Please continue reading below
your code-snippet)

> Here is the code I have run below:
>
> def printList(L):
>    # if its empty do nothing
>    if not L: return
>    # if its a list call printList on 1st element
>    if type(L[0]) == type([]):
>        printList(L[0])
>    else: #no list so just print        print L[0]    # now process the 
> rest of L    printList(L[1:])
>
> myList=[1,2,3,4,5]
>
> printList(myList)
>
> The output is as follows:
> 1
> 2
> 3
> 4
> 5

Now we change your function, observing that there are two points
where the functino may be exited:

 >>> def printList(L):
    print "printList(", L, ") entered."
    # if its empty do nothing
    if not L:
                print "printList(", L, ") exited."
        return
    # if its a list call printList on 1st element
    if type(L[0]) == type([]):
        printList(L[0])
    else: #no list so just print
        print L[0]
    # now process the rest of L
    printList(L[1:])
    print "printList(", L, ") exited."
  
 >>> printList([1,2,3,4,5])
printList( [1, 2, 3, 4, 5] ) entered.
1
printList( [2, 3, 4, 5] ) entered.
2
printList( [3, 4, 5] ) entered.
3
printList( [4, 5] ) entered.
4
printList( [5] ) entered.
5
printList( [] ) entered.
printList( [] ) exited.
printList( [5] ) exited.
printList( [4, 5] ) exited.
printList( [3, 4, 5] ) exited.
printList( [2, 3, 4, 5] ) exited.
printList( [1, 2, 3, 4, 5] ) exited.

We can amend this, by using a variable calldepth, which
we increment with every new call of printList and which we
use to indent our meta-information by preceding our
output string with "   "*calldepth:

 >>> def printList(L, calldepth):
    print "   "*calldepth + "printList(", L, ") entered."
    # if its empty do nothing
    if not L:
                print "   "*calldepth + "printList(", L, ") exited."
        return
    # if its a list call printList on 1st element
    if type(L[0]) == type([]):
        printList(L[0], calldepth+1)
    else: #no list so just print
        print L[0]
    # now process the rest of L
    printList(L[1:], calldepth+1)
    print "   "*calldepth + "printList(", L, ") exited."

   
 >>> printList([1,2,3,4,5], 1)
   printList( [1, 2, 3, 4, 5] ) entered.
1
      printList( [2, 3, 4, 5] ) entered.
2
         printList( [3, 4, 5] ) entered.
3
            printList( [4, 5] ) entered.
4
               printList( [5] ) entered.
5
                  printList( [] ) entered.
                  printList( [] ) exited.
               printList( [5] ) exited.
            printList( [4, 5] ) exited.
         printList( [3, 4, 5] ) exited.
      printList( [2, 3, 4, 5] ) exited.
   printList( [1, 2, 3, 4, 5] ) exited.
 >>>

So you see, that each active instance of printList retains it's own
value of  L, as L is a local variable to the function printList

Now you may wonder and try to understand how this comes:

 >>> printList([1,[2,3,4],5], 1)
   printList( [1, [2, 3, 4], 5] ) entered.
1
      printList( [[2, 3, 4], 5] ) entered.
         printList( [2, 3, 4] ) entered.
2
            printList( [3, 4] ) entered.
3
               printList( [4] ) entered.
4
                  printList( [] ) entered.
                  printList( [] ) exited.
               printList( [4] ) exited.
            printList( [3, 4] ) exited.
         printList( [2, 3, 4] ) exited.
         printList( [5] ) entered.
5
            printList( [] ) entered.
            printList( [] ) exited.
         printList( [5] ) exited.
      printList( [[2, 3, 4], 5] ) exited.
   printList( [1, [2, 3, 4], 5] ) exited.
 >>>

Enough stuff to digest for now, I think. To that end play with it.
Regards,
Gregor