algorithmpro
Recursion: factorial
A function that calls itself on a smaller input, until it reaches a case it can answer directly.
- time
- O(n)
- space
- O(n)
// step through it
step 1 / 11
1function factorial(n) {2 if (n <= 1) return 1;3 return n * factorial(n - 1);4}- depth
- = 1
- factorial(4)
Call factorial(4).
// pro lesson
Unlock the full walkthrough
This lesson is part of Pro. Pro unlocks every step of every lesson, plus pattern drills and mastery insights.
See pricingHow it works
factorial(4) can't answer right away, so it asks factorial(3), which asks factorial(2), and so on. Each waiting call sits on the call stack. When factorial(1) hits the base case and returns 1, the answers flow back up and each waiting call finishes its multiplication. Every recursive function needs a base case and a step that makes the input smaller. O(n) time, and O(n) space for the call stack.
Practice spotting this pattern →