DSA Basics: Recursion

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem.

Every recursive solution needs two parts:

• a base case that stops the recursion
• a recursive case that moves toward the base case

Example: factorial

function factorial(n) {
	if (n === 0) return 1;
	return n * factorial(n - 1);
}

The base case is n === 0. Without it, the function would keep calling itself forever.

How the call stack works

When a function calls itself, JavaScript keeps each unfinished call on the call stack.

factorial(3)
3 * factorial(2)
3 * 2 * factorial(1)
3 * 2 * 1 * factorial(0)

Then the calls return back upward.

Where recursion appears

• tree traversal
• graph search
• backtracking
• divide and conquer
• dynamic programming

Complexity

Recursion does not automatically mean slow. Complexity depends on how many calls are made and how much work each call does.

Factorial makes n calls, so its time is O(n) and its call-stack space is O(n).

Common mistakes

• missing the base case
• not moving toward the base case
• doing repeated work without memoization
• forgetting that recursion uses stack space

Practice problems

1. Sum numbers from 1 to n.
2. Reverse a string recursively.
3. Compute Fibonacci.
4. Traverse a binary tree.
5. Generate all subsets of an array.

Practice links

• LeetCode Recursion problems
• NeetCode practice roadmap