Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 134 ยท Methods and Blocks

Recursion

Learn recursion in Ruby - base cases, tracing calls, SystemStackError and stack depth, memoization with Hash default procs, tail calls, and turning recursion into loops.

A method is recursive when it calls itself. That sounds like a trick, but you already know the idea from everyday life: to count the people in a queue, count yourself and ask the person behind you to count the rest. Each person asks the next, until someone at the back finds nobody and answers zero. The answers then travel back up the line and add up.

Recursion is the natural tool for problems that are made of smaller copies of themselves: folders inside folders, nested arrays, trees, parsing, and many puzzles. This lesson shows the two ingredients every recursive method needs, how to read what happens step by step, what the famous SystemStackError really means, how to make slow recursion fast with memoization, and when a plain loop is the better choice.

The two ingredients

Every recursive method has:

  1. A base case: an input simple enough to answer directly. It stops the recursion.
  2. A recursive case: the method calls itself with a smaller or simpler input and uses the result.
Ruby Factorial, the classic

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

factorial(5) means 5 * factorial(4), which means 5 * (4 * factorial(3)), and so on down to factorial(1), which answers 1 immediately. Then the multiplications happen on the way back: 1, then 2 * 1, then 3 * 2, then 4 * 6, then 5 * 24 = 120. Ruby's integers grow as large as memory allows (see Numbers), so factorial(25) and even the 2,568-digit factorial(1000) are exact.

The short endless form from Endless Methods and Modern Syntax suits tiny recursive definitions well:

Ruby
def gcd(a, b) = b.zero? ? a : gcd(b, a % b)

Watching the calls happen

The easiest way to understand recursion is to print what each call does. This version indents by depth so you can see the calls going down and the results coming back up.

Ruby Tracing a recursive sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

The output forms a staircase going down (the calls) and a staircase going up (the return values). Each call waits for the one below it. While it waits, Ruby remembers where to continue and what n was. Those remembered pieces live on the call stack, one frame per active call.

When recursion never stops

If the base case is missing or the input never gets closer to it, the stack grows until Ruby gives up. The error is SystemStackError with the message stack level too deep.

Ruby Missing base case (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

The program prints the multiples of 4000 it reached, then dies with stack level too deep (SystemStackError) and a backtrace that Ruby abbreviates with a line such as ... 10908 levels... (the number varies). It does not print an endless list of lines, which is kind.

SystemStackError is not a StandardError. A bare rescue or the x rescue y modifier does not catch it, and the program ends. You can rescue it explicitly with rescue SystemStackError, but that is almost always a symptom to fix, not to hide (see Exceptions).

How deep is too deep?

The limit depends on the Ruby build, the thread and how big each frame is. On a typical Ruby the limit is somewhere around ten thousand frames. Measure it, but never write code that depends on the exact number:

Ruby Measuring the stack limit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Depth around a few thousand is fine; depth of 100,000 is not. If your input can be that deep, such as a linked list with a million nodes, use a loop (shown below). Recursion over a tree is usually safe, because a balanced tree with a million items is only about twenty levels deep.

Recursion over nested data

Arrays inside arrays have no fixed depth, which makes a loop awkward and recursion pleasant:

Ruby Flattening and measuring nested arrays

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

The pattern is always the same: handle a simple item directly; for a container, call yourself on each part and combine the answers. The built-in Array#flatten is the practical choice; writing it yourself once is the best way to see how it works.

Trees of objects work the same way. Here a folder holds files and other folders, and one small method adds up every size:

Ruby Summing a folder tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Branching recursion: combinations

When a method calls itself more than once, the calls form a tree. That is how you generate all subsets or orderings:

Ruby Subsets, permutations and Towers of Hanoi

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Three items give 8 subsets and 6 permutations; moving 10 disks needs 1,023 moves. Branching recursion grows quickly, which brings us to the main performance trap.

The Fibonacci trap and memoization

The Fibonacci numbers are defined recursively: fib(n) = fib(n-1) + fib(n-2). Written naively, each call spawns two more, and the same values are recomputed again and again.

Ruby Naive versus memoized Fibonacci

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Computing fib(20) the naive way makes 21,891 calls; fib(25) makes 242,785, and the number multiplies by about 1.6 for every step. The memoized version computes each value once. A Hash with a default block is a neat Ruby idiom for this: when a key is missing the block runs, stores the answer and returns it. The next lookup of the same key is a plain hash read (see Hashes).

The same idea works inside a method with an instance variable or a hash argument:

Ruby Memoizing a method

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Memoization trades memory for speed and only helps when the same inputs repeat. It does not remove the stack-depth limit: a memoized fast_fib[20_000] still recurses 20,000 levels deep and raises SystemStackError. Fill the table bottom-up first ((0..3000).each { |i| fast_fib[i] }) or switch to a loop.

Tail calls and loops

A call is a tail call when it is the very last thing a method does, as in gcd(b, a % b). Some languages reuse the stack frame for tail calls so they never overflow. Ruby (MRI) does not do this by default, so you cannot rely on it. The reliable fix is to rewrite the recursion as a loop, which is usually easy for a single recursive call:

Ruby From recursion to a loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

The last example walks a chain 50,000 links deep, far more than the call stack allows, by keeping the pending work in an ordinary array. This "explicit stack" trick converts almost any recursion into a loop.

When to use recursion

Use it when the data is naturally recursive (trees, nested structures, grammars), when the code reads clearly as "solve the smaller problem, combine", and when the depth is bounded. Avoid it when a simple each, reduce or upto does the job, when depth depends on user input and can be huge, or when naive branching would repeat work and you have not added memoization. When you do use it, write the base case first and make sure every recursive call moves toward it.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the two essential parts of a recursive method?

    The base case stops the recursion and the recursive case calls the method on a simpler input. Without both, the method either never calls itself or never stops.
  2. 2. What happens when recursion is too deep for the call stack?

    Ruby raises SystemStackError (message: stack level too deep). It is not a StandardError, so a plain rescue does not catch it.
  3. 3. Why is the naive fib(n-1) + fib(n-2) slow?

    The two calls overlap heavily, so the number of calls grows exponentially (fib(20) makes 21,891 calls). Memoization stores each answer once.
  4. 4. Which Ruby idiom memoizes a recursive function in a few lines?

    A Hash default block runs when a key is missing, stores the computed value under that key and returns it, so each value is computed only once.
  5. 5. How can you process a structure that is 100,000 levels deep without a stack error?

    Keeping the pending items in an ordinary array uses heap memory, which is not limited by the call stack depth.

Summary

  • A recursive method needs a base case and a recursive case that makes progress toward it.
  • Each active call uses a stack frame; trace calls with indented puts to understand them.
  • Too much depth raises SystemStackError (stack level too deep), which a bare rescue does not catch. The limit is roughly ten thousand frames, but depend on it never.
  • Recursion suits nested arrays, trees, subsets and permutations.
  • Branching recursion can repeat work; memoize with a Hash default block or @memo[n] ||=.
  • MRI does not optimize tail calls by default; convert deep recursion to a loop or use an explicit stack.

Next: Endless Methods and Modern Syntax