Ruby and recursion…

A recent discussion on the ruby-talk mailing list explored the theme of recursive methods in Ruby. Recursive functions are quite the norm in functional programming, and all implementations are optimized for this form of code. However Ruby being this entirely dynamic object-oriented language, it has always been said that you must avoid recursion in your code at all cost. It is very good advice, but it should not prevent your inner-hacker to play with the language. :)

Matz is said to be sympathetic to TCO, but does not want to force the feature on the various implementations of Ruby. To a certain extend you can write (tail-)recursive methods in Ruby MRI-1.9 without shooting yourself in the foot, but you should know that you’d lose in portability, and iterative code may still run faster.

MRI’s compile time options…

To activate the TCO in MRI-1.9, the simplest way is to do:

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

Throw it in your IRB if you want to test.

Some code

Enough with the chit-chat, let’s see some code.

For some reason, one of the most used example of recursive code is the factorial function. It looks like this:

def factorial(n, result=1)
  n == 0 ? result : factorial(n - 1, result * n)
end

MRI 1.8 will end up with a “stack too deep” error like this:

ruby-1.8.7-p334 :004 > factorial(5000)
SystemStackError: stack level too deep
from (irb):2:in `factorial'
from (irb):2:in `factorial'
from (irb):4

MRI 1.9 simply yields the appropriate result (although it does the same without activating TCO, so it’s not that interesting :p).

ruby 1.9.2p180 :004> factorial(5000)
422857792660554352220... # and roughly 16k more numbers.

If you’re only targeting MRI’s implementation of Ruby, this is probably good news since sometimes, recursion is really more readable than the equivalent non-recursive code (that’s my opinion). It does not make ruby a functional programming language, but it certainly opens a few doors, which is what programming is about.

Chase the tail

If you read carefully the various articles about tail-recursion, you should also understand why this code does not trigger MRI’s TCO code.

# Recursive Fibonacci
def fib(n)
  if n > 1
    fib(n - 1) + fib(n - 2)
  else
    n
  end
end

As opposed to say:

# Recursive Fibonacci
def fib(n, a=0, b=1)
  if n == 1
    b
  else
    a, b = b, a + b
    fib(n - 1, a, b)
  end
end

The important part in Tail-Call-Optimization is Tail: the first form is not tail-recursive and won’t be optimized.

Yes, but is it fast?

The following bench compares tail_fib which can be TCO-ed by the interpreter, and fib which is the more idiomatic, iterative, approach with ruby.

require 'benchmark'

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

def tail_fib(n, a=0, b=1)
  if n == 1
    b
  else
    a, b = b, a + b
    tail_fib(n - 1, a, b)
  end
end

def fib(n)
  a, b = 0, 1
  2.upto(n) { a, b = b, a + b }
  b
end

Benchmark.bm 10 do |x|
  5.times do |i|
    x.report("fib")      { fib      5000 }
    x.report("tail_fib") { tail_fib 5000 }
  end
end

With MRI 1.9, on my valiant X200, I get:

$ ruby rec_bench.rb
            user     system      total        real
fib         0.010000   0.000000   0.010000 (  0.004647)
tail_fib    0.000000   0.000000   0.000000 (  0.004969)
fib         0.000000   0.000000   0.000000 (  0.005121)
tail_fib    0.000000   0.000000   0.000000 (  0.002703)
fib         0.000000   0.000000   0.000000 (  0.004191)
tail_fib    0.010000   0.000000   0.010000 (  0.002886)
fib         0.000000   0.000000   0.000000 (  0.004903)
tail_fib    0.010000   0.000000   0.010000 (  0.002975)
fib         0.000000   0.000000   0.000000 (  0.004280)
tail_fib    0.000000   0.000000   0.000000 (  0.002568)

The TCO optimized version is faster than the iterative, how cool is that!?

Of course, MRI-1.8 will just die. :p

$ ruby-1.8 rec_bench.rb
                user     system      total        real
fib         0.000000   0.000000   0.000000 (  0.004272)
tail_fib  rec.rb:9:in `tail_fib': stack level too deep (SystemStackError)
# ...

Keep in mind that benchmarks are lies, and do your own homework.

Further reading

If I somehow managed to kindle your curiosity, you may want to read:

• The original discussion on ruby-talk
• Tailin' Ruby (read at least this one, please!)
• Does Ruby perform Tail Call Optimization?
• Can continuations be used as a replacement for recursion?

Did you know that readline is in the standard Ruby library? Did you know that it’s the simplest thing you probably never use?

As a matter of fact, if you sometimes write things like:

loop {
  puts '> '
  buf = $stdin.gets.chomp
  # do things with buf...
}

You should know that you can use the simpler, and much more feature-full:

require 'readline'
while buf = Readline.readline('> ', true)
  # do things with buf...
end

By the way, yes it works just as well for these days when you’re using ruby in a more Unix-y way than just-for-rails:

$ cat whatever.txt | ruby myscript_with_readline.rb

Think about that, the next time you’re writing a command-line interface, or admin tool.