Skip to content
Velloreth
Programming 8 min read

Understanding Recursion With Practical Examples

How recursion actually works, when it beats a loop, how the call stack behaves, and the mistakes that turn a simple function into a crash.

By

What recursion actually is

Recursion is a function that calls itself on a smaller version of the same problem. That is the whole idea, and it is worth stating plainly because the word makes it sound harder than it is.

A recursive function needs exactly two parts:

  • A base case that returns a value without recursing. This is what stops the process.
  • A recursive case that calls the function again on input that is strictly closer to the base case.

If either part is missing or wrong, the function either crashes or never terminates. There is no third outcome.

The reason recursion is worth learning is not that it is clever. It is that some data is genuinely recursive — a directory tree, a JSON document, an arithmetic expression — and a recursive function describes those shapes far more directly than a loop does.

The call stack is the thing to understand

Every time a function is called, the runtime pushes a frame onto the call stack. That frame holds the arguments, the local variables, and the address to return to. When the function returns, the frame is popped.

Recursion is therefore not free. A recursive call that is 1,000 levels deep has 1,000 frames alive at once. This is the single most important practical fact about recursion, because it explains the failure mode you will actually hit.

LanguageTypical default limitError on overflow
JavaScript (V8)~10,000–15,000 framesRangeError: Maximum call stack size exceeded
Python1,000 framesRecursionError: maximum recursion depth exceeded
Java~10,000–20,000 framesStackOverflowError
GoGrows dynamicallyEventually fatal error: stack overflow

Those numbers are approximate and depend on frame size, but the order of magnitude is what matters. A recursion that is fine on a 100-element array will crash on a 100,000-element one.

A first example: factorial

The textbook example is factorial, and it is worth writing once because it shows the two parts clearly.

function factorial(n) {
  if (n <= 1) return 1;        // base case
  return n * factorial(n - 1); // recursive case
}

factorial(5); // 120

Trace it and you can see the stack build up: factorial(5) waits on factorial(4), which waits on factorial(3), and so on down to factorial(1), which returns immediately. Then the multiplications unwind back up the stack.

The base case is n <= 1 rather than n === 1 on purpose. That single change makes the function return 1 for 0 and for negative numbers instead of recursing forever. Defensive base cases are cheap insurance.

The two ways recursion goes wrong

Almost every recursion bug is one of two things.

No base case, or an unreachable one. The function recurses until the stack overflows. This is the error you will see most often, and the fix is to check that the base case is actually reachable from every input.

A recursive case that does not shrink the problem. This is subtler. Consider a function that calls itself with the same argument, or with an argument that oscillates between two values. It has a base case, but it never reaches it. The symptom is identical — a stack overflow — but the cause is different, so check both.

A useful habit is to state the invariant out loud: each call receives input strictly closer to the base case than the last. If you cannot state that, the function is not correct yet.

Recursion versus iteration

Any recursive function can be rewritten as a loop, and any loop can be rewritten as recursion. They are equally powerful. The choice is about clarity and memory.

RecursionIteration
State lives inThe call stackLocal variables
Memory growthOne frame per levelConstant, usually
Depth limitBounded by the stackBounded by available memory
Reads best forTrees, graphs, divide and conquerFlat sequences, counters, accumulators
Typical failureStack overflowOff-by-one, infinite loop

The practical rule: if the data is recursive, write it recursively. If the data is a flat list, write a loop. Fighting that instinct produces code that is harder to read for no benefit.

Converting recursion to iteration

When depth is the problem, you convert. The mechanical approach is to replace the call stack with an explicit one.

// Recursive
function sumTree(node) {
  if (!node) return 0;
  return node.value + sumTree(node.left) + sumTree(node.right);
}

// Iterative, with an explicit stack
function sumTreeIterative(root) {
  let total = 0;
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    if (!node) continue;
    total += node.value;
    stack.push(node.left, node.right);
  }
  return total;
}

The iterative version uses heap memory instead of stack memory, so it is bounded by how much RAM you have rather than by the call stack. For a tree a million nodes deep, that is the difference between working and crashing.

Note that the two versions are not always equally readable. The recursive one states the intent in three lines; the iterative one needs a loop and a manual stack. That trade-off is the real decision.

Tail calls and why they are not a safety net

A call is in tail position when it is the last thing the function does, with no work left afterwards. In the factorial above, the recursive call is not in tail position, because the multiplication still has to happen after it returns.

Rewrite it with an accumulator and the call moves into tail position:

function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc); // tail call
}

Some runtimes detect this and reuse the current frame instead of pushing a new one, which turns the recursion into a loop and removes the depth limit entirely. Scheme requires it. JavaScript’s strict mode once specified it but no mainstream engine implements it. Python does not do it. So treat tail-call optimisation as a bonus where it exists, never as a guarantee you rely on.

Where recursion is the right tool

Recursion earns its place in a specific set of problems:

  • Tree traversal — walking a DOM, a file system, or an abstract syntax tree.
  • Divide and conquer — merge sort, quicksort, and binary search all split the input and recurse.
  • Backtracking — solving mazes, generating permutations, and constraint problems.
  • Parsing nested structures — JSON, HTML, and arithmetic expressions are recursive by nature.
  • Graph traversal — depth-first search is naturally recursive.

In each case the shape of the code mirrors the shape of the data, which is exactly what you want. If you are working through debugging strategies that work, you will notice that recursive bugs are usually found by tracing the depth rather than the values.

Memoisation: making recursion fast

Naive recursion can be exponentially slow. The classic example is computing Fibonacci numbers, where fib(n) calls fib(n-1) and fib(n-2), and those calls overlap enormously.

function fib(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, result);
  return result;
}

Caching the results turns an exponential algorithm into a linear one. This technique is called memoisation, and it is the foundation of dynamic programming. The recursive structure stays readable while the cost collapses.

Practical habits that prevent recursion bugs

A few habits catch most recursion problems before they reach production:

  1. Write the base case first. Before the recursive case, before anything else.
  2. Assert the shrink. Confirm each call moves toward the base case.
  3. Test the boundaries. Empty input, one element, and the deepest realistic input.
  4. Know your depth limit. If the input can exceed a few thousand levels, plan the iterative version.
  5. Add a depth guard in development. A counter that throws at a sane limit turns a mysterious crash into a clear error.

That last one is worth the two lines it costs. A depth guard tells you which input was too deep, which a stack overflow never does.

How to practise recursion

Recursion is one of those skills that clicks through repetition rather than reading. The fastest route is to solve the same small problem three ways: recursively, iteratively, and with memoisation. Comparing the three versions teaches the trade-offs far better than any explanation.

Start with problems you can already solve in a loop — reversing a string, summing a list, finding the maximum — and rewrite them recursively. Then move to problems that are awkward without recursion: flattening a nested array, walking a tree, generating permutations. The second group is where the technique stops feeling like a trick and starts feeling like the obvious choice.

If you are still building fundamentals, learning programming without tutorial hell and a junior developer’s guide to reading code both pair well with this kind of deliberate practice.

Summary

Recursion is a function calling itself on a smaller input, with a base case to stop and a recursive case that provably shrinks the problem. Its cost is stack frames, which is why depth is the limit that matters. It is the clearest way to express tree, graph, and divide-and-conquer algorithms, and it converts mechanically to a loop with an explicit stack when depth becomes a problem. Learn the base case first, keep the shrink honest, and know your runtime’s depth limit — that is most of what there is to know.

Frequently asked questions

What is recursion in simple terms?
Recursion is a function that solves a problem by calling itself on a smaller version of the same problem. It stops when it reaches a base case, a version small enough to answer directly without recursing again.
What happens if a recursive function has no base case?
It recurses until the call stack runs out of space, then the program crashes with a stack overflow error. In JavaScript that is RangeError: Maximum call stack size exceeded; in Python it is RecursionError.
Is recursion slower than a loop?
Usually slightly, because each call pushes a stack frame and that has real cost. The difference is rarely the bottleneck, so choose whichever expresses the problem more clearly and only optimise after measuring.
What is the difference between recursion and iteration?
Iteration repeats a block with a loop and keeps state in variables, while recursion repeats by calling the function again and keeps state on the call stack. Both can compute the same things; they differ in clarity and in memory behaviour.
When should I avoid recursion?
Avoid it when the input can be very deep, such as a linked list of a million nodes or a deeply nested document, because the call stack will overflow. Use an explicit stack or a loop instead.
What is tail recursion?
A recursive call is in tail position when it is the very last operation the function performs, with nothing left to do afterwards. Some runtimes reuse the current stack frame for such calls, turning the recursion into a loop.