[Tutor] Recursion help [experimenting with a recursive function]

[Danny Yoo]

On Thu, 31 Jul 2003, Justin Heath wrote:

> 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.
>
> 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:])



Hi Justin,


A good way to test out a recursive function --- to see how it works --- is
to start on small examples, and then work ourselves up to large ones.


You tested it initially with:


> myList=[1,2,3,4,5]
>
> printList(myList)
>
> The output is as follows:
> 1
> 2
> 3
> 4
> 5


But that's too big of an example.  *grin* Try smaller ones.  Here's a
simple one:

###
printList([])
###

If we read the code, we'll see that trying to "printList()" the empty list
will cleanly exit out of the function.



Ok, so we've got that handled.  Let's build on our knowledge.  What
happens if we try something like this?

###
printList([42])
###




In this case, our "L" list will be [42].  If we look back at the code:

> 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:])


it shouldn't be too hard to see that this will hit the third case:

###
     else: #no list so just print
         print L[0]
###

and print out "42" on our screen.



Finally, it'll try to print out the rest of this list by doing a:

    printList([])

at the end of the function.  So now we have to do printList([])... but we
already know what doing printList([]) does, since we just tried it a few
minutes ago: it doesn't do anything!


Let's summarize:  printList([42]) just prints the number 42.  We're
stating the "obvious", but it's important to understand here that the
function does stop if we do printList([42]).

If you're hung up at this point, start asking more questions!  *grin*




> It "appears" that the code is running thru the else block over and over
> until it reaches the end of the list. However, I do not see how the list
> is being enumerated or how it knows to go to the next item in the list.
> Can anyone shed some light on this?


Ok, now we know what will happen if we do something like printList([]) and
printList([42]).  Let's make the example slightly larger.



Now we can be a bit more ambitious.  We can try:

###
printList([17, 42])
###


You'll notice that it does:

    print 17

followed by:

    printList([42])

But we already know what printList([42]) does: we just did it a few
minutes ago.  So this ends up printing 17 and 42 in sequence.


Try guessing what our next example will look like.  *grin*



So one effective way to understand a recursive process is to push really
simple examples on it and see what it does.  Then progressively make those
examples larger and larger.  By then, you should have a good idea of what
that recursive function does.


Hope this helps!