Sign in to watch this lesson
Algorithms - Foundations · 4:13
Recursion Basics
A function that solves a problem by calling itself on a smaller copy of it: the Tower of Hanoi replayed move by move beside its call stack, what each stack frame costs and how a million-deep DFS crashes an 8 MB stack on a Mac while the explicit-stack version sails through. Then the fib(5) recursion tree and its repeated work (fib(40) needs over 331 million calls, 79 with memoization), and how to read running times off recursion trees with recurrences and the master theorem.
You will learn
- Write a recursive function with a base case and guaranteed progress, and trace its call stack
- Estimate how deep recursion can go from the stack size and frame size, and convert deep recursion to an explicit stack
- Count calls with a recursion tree and spot repeated subproblems that memoization removes
- Solve common recurrences such as 2T(n/2)+n, T(n/2)+1 and 2T(n-1)+1 by summing work per level