Skip to content
Back to AlgorithmsAll lessons

Algorithms

Recursion

This depends on the problem. But each call still waiting to finish uses stack space (memory that tracks paused calls) — O(depth) space.

The idea, in plain English

Recursion is when a function calls itself to solve a smaller version of the same problem. Think of Russian nesting dolls. To open the biggest one, you open the next, then the next, until you reach the tiniest doll that opens no further. That last step is called the 'base case'.

How it works

  1. 1Define the base case: the smallest input where you stop and return a direct answer.
  2. 2Otherwise, call the function again with a smaller input.
  3. 3Combine that smaller answer with the current step to build the full result.

When you'd use it

Use it for problems that naturally break into smaller copies of themselves: walking a tree or folder structure, divide-and-conquer sorts, and many math definitions.

Common beginner mistakes

  • Forgetting the base case, so the function calls itself forever and crashes with a 'stack overflow'.
  • Not making the input smaller on each call, which also never ends.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
5! = 120
0! = 1

See it in motion

Watch the call stackfactorial(5)This depends on the problem. But each call still waiting to finish uses stack space (memory that tracks paused calls) — O(depth) space.

Press play. We compute factorial(5) by calling a smaller copy of itself each time.

0
Stack depth
0
Calls made
—
Result
0/10
Step
Current callWaiting on the stackReturned a value

Not sure this is the right topic? See the learning paths → or where this leads →