 | |
 |
 |  |  |
 | Welcome to CS1315. Click on the python to add comments.
|  |
 |  |  |
|
This page removed for FERPA compliance
|
        |
Final Exam Review Spring 2003: Recursion
Questions, answers, comments?
(Back to Sp2003 Final Exam Review)
a. Print #3 prints the on the way down words. Print REMOVED prints the on the way up words. Print #1 prints the single letter in the middle.
b. 8 ?????
c.
def downUp(word):
if len(word)==1:
print word #Print #1
return
print word #Print REMOVED
downUp(word[:len(word)-1])
print word #Print #3
Lauren Biddle
I think that b. is 7, but I am not really sure why. I think it is because it moves up and down 7 times total without the first "hello". Prof, any suggestions? Kelly Farrell
| Think about our running it on stage. How many people were on stage at most? Mark Guzdial |
for question C., wouldn't it be def UpDown(word):???
5 time for b
| C in Lauren's answer looks like upDown(word). 5 is right – anyone want to trace it and explain it? Mark Guzdial |
Is it 5 because you only count the ever-shortening letters : Hello, Hell, Hel, He, H and then don't count when it returns the longer-growing letters?
| It's not that you "don't count" them – they're the same function! Think about how each person on stage wrote their "word" twice – once when they first got on stage, and once just before they left. Mark Guzdial |
(This may not make much sense, but this is how I understand it, so does this work?) There are 5 different versions of the word printed to begin with that are returned in the function. Then when the function reaches the point where it has been told to stop (ie. on the word with one letter–the 5th word) it returns that word and then the four other original printed words. Thus, during the executuion of each phase downUp (which there are two of) there are 5 copies running at once when using the input "Hello".
Student117
Lauren, are you sure that the 3rd print statement prints the shortening word? I thought it was the 2nd print statement that printed the way down, and the 3rd that printed the word as it built back up. I could be wrong, so let me know.
Brittany Selden
| You're right, Brittany. REMOVEDmmer, what do you mean by a "each phase downUp"? Mark Guzdial |
During the second and third print statements, the "phase" where the word is being shortened and the one where it is being lengthened. (It was supposed to be each phase of downUp().)
| Thinking about it that way, isn't there a third "phase" – where the middle character is printed? For that one (when we get down to downUp("o")), only the third phase occurs, not the first or second. Mark Guzdial |
I suppose I'm considering the middle character as being part of the first and the second phase (the seond and third loops) even though it occurs in its own loop and thus is printed only once, the fact that it occurs is what causes the second loop to end and the third to begin.
| Note: None of the phases is in a loop – at least, not a FOR or a WHILE. Recursion is another way of GENERATING looping, without looping commands. Mark Guzdial |
Sorry I should have said print statements in place of everywhere I said loop...
The reason it's 5 copies is because there are five letters in Hello. It turns each letter of Hello into a new word, so to speak.
Basically, if the input had been "welcome", there would be 7 copies running at most.
Just to make sure I understand the concept, consider this example:
def downUp(word):
if len(word)==2:
print word
return word
print word
downUp(word[1:])
print word
With an input of "welcome", there are at most 6 copies running. It goes until the if statement make the word length equal to two. Then, you return it to prevent the StackOverflow error. The second print prints "me" (the last two letters because the length equals two). Now the program starts with the new word and recalls the function to print again until the word equals all the given characters. I'm not quite sure I understand how the last part works.
| Great example, and great explanation...up to the last part :-). There is no new word. The tricky part is that the computer remembers where it left off in each of the earlier functions. downUp("welcome") remembers that it called downUp("elcome"), and when downUp("elcome") is done, downUp("welcome") finishes up by printing the "welcome" in the very last line. We can tell a similar story about downUp("elcome") and downUp("lcome") and so on. Nice bit about having it end at two characters! Mark Guzdial |
Out of curiosity, since we didn't do anyREMOVED recursion outside of the downUp's primarily, will we be writing any complex recursion functions? Meaning, if we're given a function, will we be asked to rewrite it with recursion (outside of the simple examples above given)?????
| I wouldn't be too cruel, but very similar functions are fair game. Mark Guzdial |
In the example just above, wouldn't the first print print "me" instead of the second?
| Yes, it's the first print that would print "me" and then the downUp("me") would end (with the return), letting downUp("ome") continue by printing "ome" and then ending. Mark Guzdial |
Here's some fun examples. I ran the first one after having run the previous downUp function. So here, it's actually calling up the downUp function I'd already written. It gives a really interesting answer. As you notice, it doesn't actually call up the upDown.
def upDown(word):
if len(word)==1:
print word
return word
print word
downUp(word[:len(word)-2])
print word
def upDown(word):
if len(word)==1:
print word
return word
print word
upDown(word[2:])
print word
| I think it's so cool that you're playing with recursion! Mark Guzdial |
For clarification, the first print prints the "me" copy because it's inside the "if" statement which says to only print if the word is equal to 2 characters. My one question is on the "return". I know that it prevents the StackOverflowError, but how does it? I mean, it's only inside the "if" statement. The only thing that I can think of is that the computer hasn't figured out what you want done with the copies and basically puts them in order when you tell it to return the "me" copy.
| The return statement stops the execution. Without it, you'd end the IF and just keep going into the Print and the next recursive call. You'd never stop because none of the recursive calls would ever stop. Mark Guzdial |
Oh, so it would attempt to continually print? Is that what you mean?
The other thing. When I was playing with recursion, I noticed that if my code contained two 2's instead of a 1 and a 2, it would give me a StackOverflowError. I'm not sure I understand why it did this. Can the computer not go down to zero copies? Is that what would have happened if I had had 2 in both places in the examples above?
| Yes, it would continually try to print. Two 2's? In both places? Which places? I'm sorry, I don't understand. Can you post the code that was causing a StackOverflowError? Mark Guzdial |
def upDown(word):
if len(word)==2:
print word
return word
print word
upDown(word[2:])
print word
That's the code. The two places there are numbers, if you have 2's in both places I get the error.
| How long is the word you're giving it? If it's an odd number of characters, then there'll be one call with three letters, and the next one with 1 letter, and there's never a function call with exactly two letters. Mark Guzdial |
Link to this Page