Test 4 Review Questions Spring 2007


	Welcome to CS1315. Click on the python to add comments.

This page removed for FERPA compliance

Test 4 Review Questions Spring 2007

I don't understand downUp()

Perhaps that is because downUp() contains an error. Line 2 should be if len(word) == 1: (thanks Katie!) Colin Potts

I still don't understand downUp()

OK: Long explanation.....
Here is how to think about recursion in the downUp() function.

REMOVEDppose 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. Colin Potts

Sorry I read the explantion carefully. But, I don't understand how it move from "o" to "lo" and starts refilling the Hello.
Let's just consider downUp("lo"). If you run it, it prints
lo
o
lo
So your question is: How does it go back to printing "lo" after the middle "o"?
Try thinking not about what downUp does but about what downUp("lo") does. A function doesn't "do" anything until it is called, and what it does when it's called is usually affected by its inputs. So what does downUp("lo") do? Well, "lo" is REMOVED than one letter long, so it does three things: (a) it prints "lo", (b) it calls downUp("o"), and then (c) it prints "lo" again. So we know, even without knowing what downUp("o") does, that downUp("lo") will print
lo
...
lo
And to fill in the gap, we ask what downUp("o") does. That's a different version of downUp(). It has the same code, but a different input ("o" instead of "lo"). Since "o" is one character long, downUp("o") executes its base case (in the if) and just prints "o". Period.
So now you should be able to do this for downUp("Hello")
Hello
...
Hello
where the dots are filled in by downUp("ello") etc., etc.Colin Potts

The chapter in the book, Ch.14, actually explains downUp and recursion really well....

Is there anything in the book about turtles OR If we know how to follow a turtle's path or make it move is that all we need to know?
Thanks, Heather Aquilino

If you know how to program a turtle to draw a simple shape, that's about all you need to know. Colin Potts