Feb-16-2019, 01:44 AM
(This post was last modified: Feb-16-2019, 01:54 AM by ichabod801.)
Consider the following recursive function:
mystery(0, 9)
To do so, complete the template that we have provided in section 2-1 of ps2pr012. In particular, you should:
Include a separate “frame” for each call. We have filled in some of the components of the frames for the first two calls for you. You should replace each ... with the appropriate integer, and you should add frames for additional calls as needed, until you reach the base case.
Begin each frame with lines that explicitly state the values assigned to the parameters, as we have done for the first call.
Next, if the call is a base case, you can simply show the value that is returned (omitting the line for myst_rest). If the call is a recursive case, you should show the recursive call on the line for myst_rest.
Once you have reached the base case, you should work your way back through the frames for the previous calls. Add in both the results of the recursive call (i.e, the value assigned to myst_rest) and the value returned by the call itself.
We took a similar approach to tracing recursion in Lab 3.
What is the value returned by mystery(0, 9)?
During the execution of mystery(0, 9), stack frames are added and then removed from the stack. How many stack frames are on the stack when the base case is reached? You should assume that the initial call to mystery(0, 9) is made from the global scope, and you should include the stack frame for the global scope in your count.
Give an example of specific values of a and b that would produce infinite recursion, and explain why it would occur.
You may find it helpful to use the Python Tutor visualizer to build intuition about how recursion works, to check your answers to parts 1-3 of this problem, and to test and debug the functions that you write in the later problems. For example, to test the mylen function that we discussed in lecture, you could paste the following into the visualizer:
def mystery(a, b):
if a == b:
return a
else:
myst_rest = mystery(a + 1, b - 2)
return b + myst_restTrace the execution of the following call to this functionmystery(0, 9)
To do so, complete the template that we have provided in section 2-1 of ps2pr012. In particular, you should:
Include a separate “frame” for each call. We have filled in some of the components of the frames for the first two calls for you. You should replace each ... with the appropriate integer, and you should add frames for additional calls as needed, until you reach the base case.
Begin each frame with lines that explicitly state the values assigned to the parameters, as we have done for the first call.
Next, if the call is a base case, you can simply show the value that is returned (omitting the line for myst_rest). If the call is a recursive case, you should show the recursive call on the line for myst_rest.
Once you have reached the base case, you should work your way back through the frames for the previous calls. Add in both the results of the recursive call (i.e, the value assigned to myst_rest) and the value returned by the call itself.
We took a similar approach to tracing recursion in Lab 3.
What is the value returned by mystery(0, 9)?
During the execution of mystery(0, 9), stack frames are added and then removed from the stack. How many stack frames are on the stack when the base case is reached? You should assume that the initial call to mystery(0, 9) is made from the global scope, and you should include the stack frame for the global scope in your count.
Give an example of specific values of a and b that would produce infinite recursion, and explain why it would occur.
You may find it helpful to use the Python Tutor visualizer to build intuition about how recursion works, to check your answers to parts 1-3 of this problem, and to test and debug the functions that you write in the later problems. For example, to test the mylen function that we discussed in lecture, you could paste the following into the visualizer:
def mylen(s):
if s == '':
return 0
else:
len_rest = mylen(s[1:])
return 1 + len_rest
test = mylen('cs111')
print('test is', test)