Core · Module 7 · Lesson 2 of 4
Base cases and recursion trees
A recursive function needs a base case and a step that makes progress toward it. Drawing its calls as a tree tells you both its running time and its stack depth.
Pro — members onlyAbout 14 minutes
By the end you can
- Write a recursive function with a correct base case and a step that makes progress
- Draw the recursion tree of a function and read off its total work and maximum depth
- Recognize repeated subproblems that make naive recursion exponential
Builds on How a function call works.
01 · A question first
fib(n) = fib(n − 1) + fib(n − 2) fits on one line. Yet computing fib(40) this way makes more than 330 million calls, to compute an answer from just 41 distinct inputs. Where do all those calls come from?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- The anatomy of a recursive function
- Drawing the recursion tree
- Where the Fibonacci calls come from
- Halving instead of shrinking by one
- Recurrences
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Practice · easy · LeetCodeFibonacci numberCompute the nth Fibonacci number recursively, measure the calls, then fix it with memoization and with a loop.Practice · medium · LeetCodePow(x, n)Compute x to the power n with O(log n) multiplications by halving the exponent, including negative exponents.
Asked in interviews
Something wrong with this lesson? Report a problem