[Tutor] Recursion help

[Justin Heath]

Gregor Lingl wrote:

> 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
>
>
>
>
> _______________________________________________
> Tutor maillist  -  Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor

Gregor,

I see your point. If I had chosen to print the list every time I would 
have seen the assignment when the funtioned 're-called" itself. I had 
actually added some "debugging" print statements but only within the 
if/else loops. I guess it goes to show that verbosity is a good thing.

Alos, thanks to you and everyone else for thier help. And unless I get 
my head around my next topic I may be chiming in again later. :-)

Thanks,
Justin