What smallest number of stack frames required by superpowers

Assignment Help Computer Engineering

Reference no: EM131901709

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

Reference no: EM131901709

Questions Cloud

Explain the creative methods of capturing the energy : Studies have shown that the average worker utilizes only a portion of his/her abilities in their job. Many HR professionals are seeking more creative methods.

Required return exceed foley required return : By how much does Beale's required return exceed Foley's required return?

How you plan to build your professional network : Write a 500 word description of how you plan to build your professional network whilst at University, to give yourself an advantage when applying.

What is expected loss of this loan contract : What is Expected Loss of this loan contract?

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

What is the implied probability of default of alphaland : What is the implied probability of default of Alphaland for the next 12 monhts?

What does environmental safety mean : In all honesty, how do you think you might react toworkplace violence, such as being cursed at or spoken to in a loud, demeaning manner?

What is the appropriate fiscal and monetary policy mix : 1.Consider an open economy with flexible exchange rates. Suppose output is at the natural level, but there is a trade de cit.

Research about a recent human trafficking event : Compile a list of local resources that could help victims, law enforcement, and/or community members. Consider things like women's shelters.

User Account

All Pages