Recursion and trees · Lesson 14 of 23
Recursion without fear
The base case, the call stack, and how to trust a function that calls itself.
A recursive function solves a problem by calling itself on a smaller version of it. Every recursive function needs two things:
1. A base case: a problem small enough to answer directly. 2. A shrinking step: every call moves closer to the base case.
Forget the base case and it calls itself forever, until "Maximum call stack size exceeded".
function factorial(n) {
if (n <= 1) return 1 // base case
return n * factorial(n - 1) // a smaller version of the same problem
}
// Sum of digits: 4096 → 4 + 0 + 9 + 6
function digitSum(n) {
if (n < 10) return n
return (n % 10) + digitSum(Math.floor(n / 10))
}
console.log(factorial(5), digitSum(4096))- 1function f(n) {
- 2 if (n <= 1) return 1
- 3 return n * f(n - 1)
- 4}
- ▶console.log(f(3))
Variables
| stack | f(3) |
Output
f(3) needs f(2).
Each call waits for the one below it to finish: that's the call stack.
Trust: "if it works on the smaller one…"
Don't try to trace every call in your head. Think like proof by induction: assume the function returns the right answer for the smaller problem, and only ask: "how do I use that answer to solve this one?". That's exactly how you'll handle trees.
// Recursion that repeats work: fib(40) makes over 300 million calls
// Memoization stores each answer the first time, so every n is computed once
function fib(n, memo = new Map()) {
if (n <= 1) return n
if (memo.has(n)) return memo.get(n)
const value = fib(n - 1, memo) + fib(n - 2, memo)
memo.set(n, value)
return value
}
console.log(fib(10), fib(50))What's the output?
function count(n) {
if (n === 0) return ""
return count(n - 1) + n
}
console.log(count(4))What will this code print?
Exercise
Write a fast recursive power(x, n): x^n = (x^(n/2))², with one more multiplication by x when n is odd (n ≥ 0). It must print 1024 1 243.
Expected output: 1024 1 243
function power(x, n) {
}
console.log(power(2, 10), power(7, 0), power(3, 5))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 2 games
Sign in to save your progress and earn XP.