Previous Lecture

Lecture 15

Next Lecture

Lecture 15, Mon 11/27

Program Stack and Recursion

Resources from lecture

• Link to all code written in lecture

• Link to lecture slides and peer instruction questions

• Guidelines for using peer instruction - thanks to Dan Zingaro

Topics

• Why does recursion feel like magic?
• Step through the evolution of the program stack with nested function calls
• Recursive thinking and design of recursive functions
• The two key properties of a correct recursive function
  • Stopping condition (also known as base case) - there may be multiple of these
  • Progress towards the base case in the recursive step
• Pitfalls in code that violate the two key properties
• Under the hood of execution of recursive functions by visualizing the program stack