Change Contents of the Bubble
Welcome to CS1315. Click on the python to add comments.

Looking for the book? They have it at the Engineer's Bookstore at 748 Marietta St NW. Here is there website: http://www.engrbookstore.com/ - Monica

Hotspots: Slides and Code • TA Corner • Comments? • Announcements • FAQ • Static Webspace
View this PageEdit this PageUploads to this PageHistory of this PageHomeRecent ChangesSearchHelp Guide

downUp

def downUp(word): 
  if len(word) == 1: 
    print word # Print one-letter word
    return 
  else:
    print word # First printing of multiple-letter word
    downUp(word[1:]) 
    print word # Second printing of multiple-letter word


Here is how to think about recursion in the downUp() function.

Suppose we call downUp("abc")

Q: What does downUp("abc") print first of all?
A: "abc"

Q: What does it do next?
A: It calls itself with a shorter string, specifically downUp("bc")

Q: OK. Forget that calling of itself for a moment. Having printed "abc" AND done downUp("bc"), what would downUp("abc") do last of all?
A: It would print "abc" again.

So we know that downUp("abc") prints the following:

abc
...
abc

Where the dots represent whatever it is that downUp("bc") prints between the two "abc"'s, provided that downUp("bc") doesn't go off into an infinite recursion and never come back (in other words, provided that it has a base case for the special case of a one-letter word).

Q: OK. So what DOES downUp("bc") print? And does it go on forever?
A: By extension from what downUp("abc") prints, it has to print the following:

bc
...
bc

Where the dots again represent the call to itself – this time a call of downUp("c")

Q: And what do we know is printed so far?
A: Combining our two invocations of downUp() we know that the output looks like this:

abc
bc
...
bc
abc

Q: So all we need to know is what downUp("c") prints and then we will be able to fill in the dots?
A: Right.

Q: And that would be...?
A: Since "c" is only one letter long, downUp("c") executes the base case and just prints "c". It DOESN'T call downUp() recursively, which means that the previous calls to downUp() WILL do their second print statements and will finish.

Q: So filling in the gap gives us....
A:

abc
bc
c
bc
abc

The execution path of the program is a tree, just like the turtle tree-drawing program. The tree of downUp("abc") isn't drawn by a turtle, but you can draw it yourself. It has three branches. At each level, the left branch is whatever downUp() prints at that level, so it's just a "leaf". The right branch is an identical leaf. The central branch between them is whatever downUp() gives you with the string that is one letter shorter than the word on the level below. You get to the top of the tree when you have a word that is only one letter long, and that too is a leaf. If you start at the lower left corner of the tree and write out all the leaf strings in a clockwise order, you have the strings that the program will print in the order that it prints them.

Link to this Page