Lab: Exploring Recursion and the Stack Frame

Laboratory Activities: Recursion, the stack, and problem-solving

ACTIVITY: Recursion's stack frames

1. Download the file powers_rec.py from Moodle.

2. Run the program in PyCharm. It should display a single line of text.

3. Set a breakpoint on the first line of powers.

4. Use the debugger to Step into My Function to step through the program.

5. Observe how the stack grows with each function call, and shrinks with each return.

6. Observe how each frame has its own variable named n.

7. Watch how large the stack grows!

ACTIVITY: Questions for powers

1. When the stack is the largest, how many powers frames are there?

2. Using Big-O notation, express the number of powers frames as a function of n (the exponent).

ACTIVITY: Recursion's stack frames

1. Set a breakpoint on the first line of superpowers.

2. Use the debugger to Step into My Function to step through the program.

3. Observe how the stack grows with each function call, and shrinks with each return.

4. Observe how each frame has its own variable named n.

5. Watch how large the stack grows!

ACTIVITY: Questions for superpowers

1. When the stack is the largest, how many superpowers frames are there?

2. What's the best case? I.e., for a given n, what's the smallest number of stack frames required by superpowers?

3. What's the worst case? I.e., for a given n, what's the largest number of stack frames required by superpowers?

4. Using Big-O notation, express the number of superpowers frames as a function of n (the exponent).

ACTIVITY: Divide and conquer for max

Python has a built-in function named max, which returns the largest value of a list.

For practice, implement a recursive function called maximum that returns the maximum value of a list of numbers.

1. Implement maximum1 as a recursive function that divides the list into a problem one smaller than the original.

2. Implement maximum2 as a recursive function that divides the list into two sub-lists of roughly equal halves.

Use list slicing to obtain your sub-problems.

ACTIVITY: Divide and conquer for sum

On Slide 10, we started a derivation for a version of sum that reduces the problem of summing 1 + 2 + · · · + n into a problem that reduces n to n=2.

Continue the derivation, and implement a recursive function from it.

Name your function supersum, because Python already defines a built-in function named sum.

Your implementation should have the same time complexity as superpowers.

To check, you can modify the program timing.py.

Attachment:- Assignment Files.rar