|Welcome to CS1315. Click on the python to add comments.|
|This page removed for FERPA compliance|
Final Exam Review Spring 2005: More Recursion
i have no clue what's wrong with the first recursion program. it looks like it should work but it doesn't. :(
the one(string) and the two(string) functions take in a string as an input. if the length of the string is greater than one, the functions would print it out, then cut out the first letter in the string and apply themselves(the functions) to the shorten version of the string until the string has a length of one. so the functions prints out the string, then they print out its components at the rate of n-1 till it reasches the last letter.
mystery(string) give you the number of letters in that input string
enigma(number): this function takes a number as an input; if the number is greater than 0 but less than 10, the function would return the number itself. if the number is greater then or equal to 10, the function would return the value of one.
puzzle(string): prints out every letter of the string one by one
baffle(string): this one prints out the string and it's components at a n-1 fashion. IE: for the string "abc", it would print out "abc bc c"
|As a hint on the first program, The function will not exceute the second line, the if statement, until it finishes running the first line, the recursive call. The recursive call in turn will not see the if statement until it finishes making another recursive call, etc on and on forever. What could you do to fix this? Try comapring the function to the other recursive functions in the problem. What is different about this one? For the one(sting) and two(string) function, you are correct that one of them will print the word and then cut out the first letter and recurse. REMOVEDwever, they do not both do the same thing. Try comparing the placement of the print statements to the earlier recursive question involving downUp. Mystery is correct. Enigma does not do what you say it does. A hint: When you % a number by 10, it will return the last digit. When you do integer division of a number by 10, it will return the number without the last digit (13435 will become 1343) Look at it again and see if this helps figure out what it is doing. And you are also incorrect about baffle. When you run it on baffle("abc"), it will return the baffle("bc") + a. Baffle of("bc"") will return baffle("c") + b. Baffle("c") will return baffle("") + c. Baffle("") will return "" Recombine these calls and see what is produced. Student1594|
first program should be
if n == 1 or n == 0:
retval = n*fact(n-1)
from looking at the codes in downUp, i would say that the two(string) function would print out the last letter of the string, then recurse itself until the entire string has printed out. so for the word JES, it would pring out S, ES, JES. my question is, i understood how did it get to the last letter of the string, but what did the function do in order to go from the every end of the string back to the beginning to print out ES and JES?
|The function that initally runs on JES recursively calls itself on ES. The function on JES did not stop running however. It is waiting for the function on ES to finish and then it will exceute the line after the recursive call which prints "JES" The function on ES in turn calls the function on S and when that finishes running it prints "ES" "ES" will get printed before "JES" becuase the function that prints "ES" must finish before the original function can print "JES" The reason it works this way, which is very similar the baffle function is that the recursive call occurs before the print statment which causes this backwards sort of behavior. Student1594|
enigma would take the out the last digit of the integer and add it to the recursions that follow. so for the number of 123, enigma will run the following: 3+enigma(12) => 3+2+enigma(1) => 3+2+1+enigma(0) => 3+2+1+0 = 6
baffle would do the following, for example, to the string "abc"
baffle("bc")+"abc" => baffle("c") + "bc" + "abc" => baffle("")+"c"+"bc"+"abc" => ""+"c"+"bc"+"abc"
|Still not quite how it works. baffle("abc") returns baffle("bc") + "a" not "abc" baffle("bc") returns baffle("c") + "b" not "bc" So baffle("abc") would then become baffle("c") + "b" + "a". "b" + "a" would become "ba" so then baffle("abc") is baffle("c") + "ab" Figure out what baffle("c") returns and you have the entire output which will show what the function does. Notice in this example, you're only adding one letter at a time to the recursive call so your output should only by as long as the number of recursive calls. The behavior you are demonstrating would result if you had a recursive call that looked REMOVED like baffle(string(1:) + string instead of baffle(string(1:) + string Student1594|
technically, baffle does nothing because you need a double = sign in the if statement
Link to this Page