Python Forum
Please help me with this!
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Please help me with this!
#1
Consider the following recursive function:
def mystery(a, b):
    if a == b:
        return a
    else:
        myst_rest = mystery(a + 1, b - 2)
        return b + myst_rest
Trace the execution of the following call to this 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 mylen(s):
    if s == '':
        return 0
    else:
        len_rest = mylen(s[1:])
        return 1 + len_rest

test = mylen('cs111')
print('test is', test)
Reply
#2
What have you tried? We're not big on writing code for people here, but we would be happy to help you fix your code when you run into problems. When you do run into problems, please post your code in Python tags, and clearly explain the problem you are having, including the full text of any errors.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#3
This should be
if a == b:
## should be
if a >= b: 
if a = b + 1, then a+1 and b-2 will cause b to be smaller than a and they will diverge from there.
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020