Lesson 055
Recursion Examples
Base Case · Call Stack · Tree · Hanoi
1:00Concrete worked examples of recursion — factorial call stack, Fibonacci tree, binary-tree traversal, and Tower of Hanoi — plus the pitfalls and a three-step recipe for writing recursive functions.
By the end, you can
- Identify the base case and recursive step in a given recursive function.
- Trace the call stack for `factorial(n)` and state the return values in unwind order.
- Compute `fib(n)` by hand and explain why naive Fibonacci is O(2ⁿ).
- Explain how memoization eliminates redundant subproblem computation, reducing Fibonacci to O(n).
- Perform an in-order traversal of a binary tree and explain why the node is visited between the two recursive calls.
- Apply the formula 2ⁿ − 1 to compute the minimum move count for Tower of Hanoi.
- Diagnose a missing-base-case bug and describe the resulting stack overflow behavior.
- Apply the three-step Recursion Recipe to design a new recursive function.
- Name four application domains where recursion appears naturally in real software.
Up next in Recursion, Paradigms & Algorithm Analysis
