Recursion and Tail Recursion

Overview

Recursion defines a function that calls itself during execution to solve problems by breaking them into smaller instances of the same problem. Each recursive call operates on a reduced version of the original input until reaching a terminating condition. The technique applies across algorithm design, data structure traversal, and mathematical computation.

A recursive function requires two components: a base case that returns without further recursion, and a recursive case that reduces the problem and calls the function again. The base case prevents infinite recursion by providing an exit condition. The recursive case transforms the problem into a simpler form, ensuring eventual termination.

def factorial(n)
  return 1 if n <= 1  # base case
  n * factorial(n - 1)  # recursive case
end

factorial(5)
# => 120

Tail recursion represents a specific form where the recursive call appears as the final operation before returning. This position allows certain optimizations that eliminate stack growth. A tail recursive function performs all computation before the recursive call, passing accumulated results as arguments rather than computing after the call returns.

def factorial_tail(n, accumulator = 1)
  return accumulator if n <= 1  # base case
  factorial_tail(n - 1, n * accumulator)  # tail call
end

factorial_tail(5)
# => 120

The distinction matters because each recursive call consumes stack space to store the return address and local variables. Standard recursion builds a stack of pending operations. Tail recursion enables optimization that reuses the current stack frame, converting recursion into iteration at the machine level.

Key Principles

Recursion Mechanics

Every recursive call creates a new stack frame containing the function's local variables, parameters, and return address. The runtime pushes this frame onto the call stack. When the function returns, the runtime pops the frame and resumes execution at the stored return address. This mechanism enables the function to maintain separate state for each invocation level.

The call stack has finite size, typically measured in megabytes. Deep recursion exhausts available stack space, triggering a stack overflow error. The maximum recursion depth depends on stack size, frame size, and available memory. Most systems support thousands of recursive calls for simple functions but fewer for functions with large local variables.

Base Case Requirements

The base case must guarantee termination for all valid inputs. Missing or incorrect base cases cause infinite recursion. Multiple base cases may exist for complex problems. Each base case returns a result directly without recursion.

def fibonacci(n)
  return n if n <= 1  # handles both 0 and 1
  fibonacci(n - 1) + fibonacci(n - 2)
end

Recursive Case Design

The recursive case must progress toward the base case with each call. This progression requirement ensures termination. The function typically reduces input size, decrements a counter, or moves toward a boundary condition. Failure to progress causes infinite recursion even with valid base cases.

def sum_array(arr)
  return 0 if arr.empty?
  arr.first + sum_array(arr.drop(1))  # reduces array size
end

Tail Call Position

A call occupies tail position when it represents the final operation before return. The calling function performs no computation with the result. This position enables tail call optimization (TCO) because the caller needs no information preserved after the call returns.

# Tail position - recursive call is last operation
def countdown(n)
  return if n <= 0
  puts n
  countdown(n - 1)  # nothing happens after this call
end

# Not tail position - multiplication happens after recursive call
def factorial_regular(n)
  return 1 if n <= 1
  n * factorial_regular(n - 1)  # multiplication after call returns
end

Tail Call Optimization

TCO replaces the current stack frame with the frame for the tail call instead of creating a new frame. This replacement works because the current function requires no information after the tail call returns. The optimization converts recursion into iteration, eliminating stack growth and enabling unlimited recursion depth.

Languages implementing TCO can execute tail recursive functions with constant stack space regardless of recursion depth. The optimization applies automatically when the compiler or interpreter detects tail position calls. Not all languages support TCO. Some require explicit configuration or specific syntax.

Accumulator Pattern

Converting standard recursion to tail recursion typically requires an accumulator parameter that carries intermediate results. The recursive case updates the accumulator and passes it forward. The base case returns the accumulator value. This pattern moves computation before the recursive call instead of after it returns.

# Standard recursion - computes after return
def sum_standard(n)
  return 0 if n <= 0
  n + sum_standard(n - 1)
end

# Tail recursion - computes before call
def sum_tail(n, acc = 0)
  return acc if n <= 0
  sum_tail(n - 1, acc + n)
end

Ruby Implementation

Ruby supports recursion with standard call stack mechanics. Each method invocation creates a new stack frame. The default stack size varies by Ruby implementation and platform but typically allows several thousand recursive calls for simple methods.

Stack Size Limitations

Ruby raises SystemStackError when recursion depth exceeds available stack space. The exact limit depends on Ruby version, platform, and method complexity.

def infinite_recursion(n)
  infinite_recursion(n + 1)
end

infinite_recursion(0)
# SystemStackError: stack level too deep

Tail Call Optimization Support

Ruby introduced TCO as an experimental feature in MRI 2.0. The optimization remains disabled by default due to compatibility concerns with debugging tools and stack traces. Enabling TCO requires setting RubyVM::InstructionSequence compile options.

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

# Define method after enabling TCO
eval <<-CODE
  def factorial_tco(n, acc = 1)
    return acc if n <= 1
    factorial_tco(n - 1, n * acc)
  end
CODE

factorial_tco(10000)  # succeeds with TCO enabled

The trace_instruction option must be disabled because instruction tracing conflicts with TCO. This requirement prevents using certain debugging tools with TCO-enabled code. Alternative Ruby implementations like TruffleRuby provide different TCO support.

Converting Standard to Tail Recursion

Standard recursive methods require conversion to tail recursive form for TCO benefits. The conversion introduces accumulator parameters and restructures computation.

# Standard recursion
def reverse_array(arr)
  return [] if arr.empty?
  reverse_array(arr.drop(1)) + [arr.first]
end

# Tail recursive version
def reverse_array_tail(arr, acc = [])
  return acc if arr.empty?
  reverse_array_tail(arr.drop(1), [arr.first] + acc)
end

Method Definition Context

TCO applies only to methods defined after enabling the optimization. Methods defined before enabling TCO or loaded from required files do not receive optimization. This behavior requires careful management of when and how methods are defined.

# TCO not applied - defined before enabling
def method_without_tco(n, acc = 1)
  return acc if n <= 1
  method_without_tco(n - 1, n * acc)
end

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

# TCO applied - defined after enabling
eval <<-CODE
  def method_with_tco(n, acc = 1)
    return acc if n <= 1
    method_with_tco(n - 1, n * acc)
  end
CODE

Recursion with Blocks and Procs

Ruby blocks and Procs support recursion through explicit naming or the call method. Anonymous recursion requires passing the Proc as an argument to itself.

# Named Proc recursion
factorial_proc = ->(n, acc = 1) {
  n <= 1 ? acc : factorial_proc.call(n - 1, n * acc)
}

factorial_proc.call(5)
# => 120

# Y combinator for anonymous recursion
y = ->(f) { ->(x) { f.call(x.call(x)) }.call(->(x) { f.call(->(v) { x.call(x).call(v) }) }) }

factorial_y = y.call(->(f) { ->(n, acc = 1) { n <= 1 ? acc : f.call(n - 1, n * acc) } })
factorial_y.call(5)
# => 120

Mutual Recursion

Multiple methods can call each other recursively. Mutual recursion requires forward declaration or careful ordering in Ruby.

def even?(n)
  return true if n == 0
  odd?(n - 1)
end

def odd?(n)
  return false if n == 0
  even?(n - 1)
end

even?(10)
# => true

Practical Examples

Tree Traversal

Recursion naturally expresses tree traversal algorithms. Each node processes itself and recursively processes children.

class TreeNode
  attr_accessor :value, :left, :right
  
  def initialize(value, left = nil, right = nil)
    @value = value
    @left = left
    @right = right
  end
end

def inorder_traversal(node, result = [])
  return result if node.nil?
  
  inorder_traversal(node.left, result)
  result << node.value
  inorder_traversal(node.right, result)
  
  result
end

# Build tree:     4
#                / \
#               2   6
#              / \ / \
#             1  3 5  7

tree = TreeNode.new(4,
  TreeNode.new(2, TreeNode.new(1), TreeNode.new(3)),
  TreeNode.new(6, TreeNode.new(5), TreeNode.new(7))
)

inorder_traversal(tree)
# => [1, 2, 3, 4, 5, 6, 7]

Directory Traversal

File system navigation demonstrates practical recursion for hierarchical structures.

require 'find'

def find_files(path, pattern, results = [])
  return results unless File.directory?(path)
  
  Dir.foreach(path) do |entry|
    next if entry == '.' || entry == '..'
    
    full_path = File.join(path, entry)
    
    if File.directory?(full_path)
      find_files(full_path, pattern, results)
    elsif entry.match?(pattern)
      results << full_path
    end
  end
  
  results
end

find_files('/usr/local', /\.rb$/)
# => ["/usr/local/lib/ruby/script.rb", ...]

Merge Sort Implementation

Divide-and-conquer algorithms use recursion to split problems and combine results.

def merge_sort(arr)
  return arr if arr.length <= 1
  
  mid = arr.length / 2
  left = merge_sort(arr[0...mid])
  right = merge_sort(arr[mid..-1])
  
  merge(left, right)
end

def merge(left, right)
  result = []
  
  until left.empty? || right.empty?
    result << (left.first <= right.first ? left.shift : right.shift)
  end
  
  result + left + right
end

merge_sort([64, 34, 25, 12, 22, 11, 90])
# => [11, 12, 22, 25, 34, 64, 90]

Permutation Generation

Recursion generates all permutations by fixing elements and permuting remainders.

def permutations(arr)
  return [arr] if arr.length <= 1
  
  result = []
  
  arr.each_with_index do |element, index|
    remaining = arr[0...index] + arr[(index + 1)..-1]
    
    permutations(remaining).each do |perm|
      result << [element] + perm
    end
  end
  
  result
end

permutations([1, 2, 3])
# => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Nested Data Structure Flattening

Recursion handles arbitrarily nested structures by processing each level.

def deep_flatten(arr)
  result = []
  
  arr.each do |element|
    if element.is_a?(Array)
      result.concat(deep_flatten(element))
    else
      result << element
    end
  end
  
  result
end

deep_flatten([1, [2, [3, [4]], 5], 6, [7, 8]])
# => [1, 2, 3, 4, 5, 6, 7, 8]

Common Patterns

Linear Recursion

Linear recursion makes one recursive call per invocation. The pattern applies to sequential processing where each step depends on the previous result.

def sum_list(list)
  return 0 if list.empty?
  list.first + sum_list(list.drop(1))
end

def string_reverse(str)
  return str if str.length <= 1
  string_reverse(str[1..-1]) + str[0]
end

Binary Recursion

Binary recursion makes two recursive calls per invocation. Common in divide-and-conquer algorithms and binary tree operations.

def fibonacci_binary(n)
  return n if n <= 1
  fibonacci_binary(n - 1) + fibonacci_binary(n - 2)
end

def binary_search(arr, target, low = 0, high = arr.length - 1)
  return -1 if low > high
  
  mid = (low + high) / 2
  
  return mid if arr[mid] == target
  return binary_search(arr, target, low, mid - 1) if arr[mid] > target
  binary_search(arr, target, mid + 1, high)
end

Multiple Recursion

Functions making more than two recursive calls handle problems with multiple subproblems.

def tower_of_hanoi(n, source, target, auxiliary)
  return if n <= 0
  
  tower_of_hanoi(n - 1, source, auxiliary, target)
  puts "Move disk #{n} from #{source} to #{target}"
  tower_of_hanoi(n - 1, auxiliary, target, source)
end

tower_of_hanoi(3, 'A', 'C', 'B')
# Move disk 1 from A to C
# Move disk 2 from A to B
# Move disk 1 from C to B
# Move disk 3 from A to C
# Move disk 1 from B to A
# Move disk 2 from B to C
# Move disk 1 from A to C

Accumulator Pattern

Accumulator parameters carry intermediate results through recursive calls, enabling tail recursion.

def product_list(list, acc = 1)
  return acc if list.empty?
  product_list(list.drop(1), acc * list.first)
end

def filter_tail(list, predicate, acc = [])
  return acc if list.empty?
  
  new_acc = predicate.call(list.first) ? acc + [list.first] : acc
  filter_tail(list.drop(1), predicate, new_acc)
end

filter_tail([1, 2, 3, 4, 5], ->(x) { x.even? })
# => [2, 4]

Continuation Pattern

Continuation-passing style passes a function representing remaining computation instead of returning values directly.

def factorial_cps(n, cont = ->(x) { x })
  return cont.call(1) if n <= 1
  factorial_cps(n - 1, ->(result) { cont.call(n * result) })
end

factorial_cps(5)
# => 120

Memoization Pattern

Caching recursive call results eliminates redundant computation in problems with overlapping subproblems.

def fibonacci_memo(n, memo = {})
  return n if n <= 1
  return memo[n] if memo.key?(n)
  
  memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
end

fibonacci_memo(50)
# => 12586269025 (computed efficiently)

Performance Considerations

Stack Space Complexity

Each recursive call consumes stack space proportional to the size of the stack frame. Frame size includes parameters, local variables, and return addresses. Deep recursion with large frames exhausts stack space faster than shallow recursion with small frames.

Linear recursion has O(n) stack space complexity where n represents recursion depth. Binary recursion typically has O(log n) space for balanced problems like binary search but O(n) for unbalanced cases. The call stack depth determines memory requirements independent of heap allocations.

Time Complexity Analysis

Recursion time complexity depends on the number of recursive calls and work per call. Linear recursion performs O(n) calls with O(1) work each, yielding O(n) total time. Binary recursion can perform exponential calls as seen in naive Fibonacci implementation.

# O(2^n) time complexity - exponential
def fibonacci_slow(n)
  return n if n <= 1
  fibonacci_slow(n - 1) + fibonacci_slow(n - 2)
end

# O(n) time complexity with memoization
def fibonacci_fast(n, memo = {})
  return n if n <= 1
  return memo[n] if memo.key?(n)
  
  memo[n] = fibonacci_fast(n - 1, memo) + fibonacci_fast(n - 2, memo)
end

Recursion vs Iteration Performance

Iteration generally outperforms recursion in languages without TCO due to lower overhead. Each recursive call requires stack frame creation, parameter copying, and return address storage. Iteration maintains state in local variables without function call overhead.

require 'benchmark'

def factorial_recursive(n)
  return 1 if n <= 1
  n * factorial_recursive(n - 1)
end

def factorial_iterative(n)
  result = 1
  (2..n).each { |i| result *= i }
  result
end

Benchmark.bm do |x|
  x.report("recursive:") { 10000.times { factorial_recursive(20) } }
  x.report("iterative:") { 10000.times { factorial_iterative(20) } }
end

# recursive: typically 2-3x slower without TCO

Tail Recursion Performance

Tail recursion with TCO performs comparably to iteration by eliminating stack frame creation. The compiler or interpreter converts tail calls into jumps, reusing the current stack frame. This optimization reduces both time and space overhead to iteration levels.

Without TCO, tail recursive functions still incur call overhead despite the tail position. Ruby's disabled-by-default TCO means tail recursion offers no performance benefit in standard configurations.

Memory Allocation Patterns

Recursive functions often create intermediate objects for partial results. These allocations accumulate across recursive calls, increasing garbage collection pressure.

# Creates many intermediate arrays
def recursive_map(arr, &block)
  return [] if arr.empty?
  [block.call(arr.first)] + recursive_map(arr.drop(1), &block)
end

# More efficient - fewer allocations
def recursive_map_optimized(arr, block, result = [])
  return result if arr.empty?
  result << block.call(arr.first)
  recursive_map_optimized(arr.drop(1), block, result)
end

Cache Performance

Deep recursion creates poor cache locality as the call stack grows beyond cache sizes. Each recursive call accesses different memory locations for stack frames. Iteration maintains better cache performance through sequential memory access patterns and smaller working sets.

Common Pitfalls

Missing Base Case

Omitting the base case or incorrectly defining termination conditions causes infinite recursion and stack overflow.

# Missing base case
def broken_countdown(n)
  puts n
  broken_countdown(n - 1)  # never terminates
end

# Incorrect base case
def broken_factorial(n)
  return 1 if n == 1  # fails for n <= 0
  n * broken_factorial(n - 1)
end

# Correct implementation
def correct_factorial(n)
  return 1 if n <= 1  # handles all base cases
  n * correct_factorial(n - 1)
end

Non-Progressing Recursion

Recursive calls that fail to reduce the problem size prevent termination.

# Does not progress toward base case
def broken_sum(n)
  return 0 if n <= 0
  n + broken_sum(n)  # n never decreases
end

# Correct progression
def correct_sum(n)
  return 0 if n <= 0
  n + correct_sum(n - 1)  # n decreases each call
end

Unhandled Edge Cases

Negative inputs, empty collections, or nil values can break recursion assumptions.

# Fails with negative input
def unsafe_factorial(n)
  return 1 if n == 0
  n * unsafe_factorial(n - 1)  # infinite recursion for n < 0
end

# Handles edge cases
def safe_factorial(n)
  return nil if n < 0  # reject invalid input
  return 1 if n <= 1
  n * safe_factorial(n - 1)
end

Excessive Memory Consumption

Creating new objects in each recursive call accumulates memory rapidly.

# Creates many intermediate strings
def inefficient_join(arr, separator = "")
  return "" if arr.empty?
  return arr.first.to_s if arr.length == 1
  arr.first.to_s + separator + inefficient_join(arr.drop(1), separator)
end

# More efficient with accumulator
def efficient_join(arr, separator = "", result = "")
  return result if arr.empty?
  new_result = result.empty? ? arr.first.to_s : result + separator + arr.first.to_s
  efficient_join(arr.drop(1), separator, new_result)
end

Naive Fibonacci Implementation

The standard recursive Fibonacci implementation recalculates values exponentially.

# Exponential time complexity
def fibonacci_naive(n)
  return n if n <= 1
  fibonacci_naive(n - 1) + fibonacci_naive(n - 2)
end

fibonacci_naive(40)  # takes several seconds

# Linear time with memoization
def fibonacci_optimized(n, memo = {})
  return n if n <= 1
  return memo[n] if memo.key?(n)
  
  memo[n] = fibonacci_optimized(n - 1, memo) + fibonacci_optimized(n - 2, memo)
end

fibonacci_optimized(40)  # returns immediately

Incorrect Tail Call Form

Operations after the recursive call prevent tail call optimization.

# Not tail recursive - multiplication after call
def factorial_not_tail(n)
  return 1 if n <= 1
  n * factorial_not_tail(n - 1)  # must save n for multiplication
end

# Tail recursive - no operations after call
def factorial_tail_correct(n, acc = 1)
  return acc if n <= 1
  factorial_tail_correct(n - 1, n * acc)  # all work done before call
end

Modifying Shared State

Recursion with mutable shared state creates difficult-to-debug issues.

# Dangerous shared state
@count = 0

def dangerous_recursion(n)
  return if n <= 0
  @count += 1  # modifies shared state
  dangerous_recursion(n - 1)
end

# Safe approach with parameters
def safe_recursion(n, count = 0)
  return count if n <= 0
  safe_recursion(n - 1, count + 1)
end

Stack Overflow from Deep Recursion

Large inputs cause stack overflow in languages without TCO or when TCO is disabled.

def sum_range(n)
  return 0 if n <= 0
  n + sum_range(n - 1)
end

sum_range(10000)
# SystemStackError: stack level too deep

# Iterative alternative
def sum_range_safe(n)
  (1..n).reduce(0, :+)
end

sum_range_safe(10000)
# => 50005000

Reference

Recursion Characteristics Comparison

Ruby TCO Configuration

Common Recursive Patterns

Base Case Design

Performance Characteristics

Conversion Checklist

Stack Overflow Prevention

Time Complexity by Pattern