Recursion in Ruby

A method that calls itself

Recursion is a method that solves a small case directly and the rest by calling itself on something smaller. The factorial is the standard example, and the base case is the line that stops it:

def fact(n) return 1 if n < 2 n * fact(n - 1) end puts fact(5)

ruby -e 'def fact(n) = n < 2 ? 1 : n * fact(n - 1); puts fact(5)'

120

The call stack holds one frame per step: fact(5) waits for fact(4), which waits for fact(3), and the multiplication happens on the way back. A recursion without a base case, or with one that is never reached, ends in the stack error from the last section.

Recursive data

Recursion is at its best when the data is already nested. An array that may contain arrays is summed by asking whether the item is an array:

ruby -e 'def total(x) = x.is_a?(Array) ? x.sum { total(_1) } : x; p total([1, [2, [3]]])'

6

_1 is the block parameter Ruby 3 provides, so the recursive call fits on one line. The same shape reads a JSON tree, a comment thread with replies, or an expression tree — any structure where a node holds nodes.

The iterative version keeps an explicit stack and is the one to write when the data can be deep. Ruby's own Array#flatten is the special case of this recursion, written in C and without a Ruby frame per level.

Walking a directory

A file tree is the everyday recursion, and Dir.children plus File.directory? (both from lesson 120, later) is all it needs:

def count_files(dir) total = 0 Dir.children(dir).each do |name| path = File.join(dir, name) total += File.directory?(path) ? count_files(path) : 1 end total end puts count_files("walk")

walk ├── a │ ├── b │ │ └── three.txt │ └── two.txt ├── c └── one.txt

ruby walk.rb

3

The folder c is empty and contributes nothing, which is the one case to remember: a directory with no children returns zero without needing a special branch.

The stack has a limit

Each call takes a frame, and the frames are finite. A hundred thousand levels is past the limit on a default Ruby:

ruby -e 'def down(n) = n.zero? ? 0 : down(n - 1); down(100_000)'

-e:1:in 'Object#down': stack level too deep (SystemStackError) from -e:1:in 'Object#down' from -e:1:in 'Object#down' ... 10908 levels... from -e:1:in 'Object#down'

Ruby prints the first frames, a count, and the last ones, because printing every frame would be useless. The limit is around ten thousand Ruby frames by default; RUBY_THREAD_VM_STACK_SIZE changes it, and a deep recursion is still better rewritten as a loop.

Ruby does not optimise a tail call, so a recursive method that returns the call directly still grows the stack. The loop version of down is while n > 0; n -= 1; end, which uses one frame.

What to watch for

Write the base case first and test it alone. A recursion that fails on the smallest input is a base case that never matches, not a problem with the recursive step.

A recursion over a structure that a user controls can be turned into a denial of service: a JSON document nested ten thousand levels deep exhausts the stack. Validate the depth, or walk it with an explicit stack.

Next: Modules and mixins

Article author: Arthur Isaev