def Tenako.blog () end

Leyendo el libro de Programming Erlang descubrí un concepto que no conocia: funciones tail-recursive.

En esta pagina lo explican bastante bien (entre otros tipos de recursividad), pero basicamente una función tail-recursive es aquella que no tiene ninguna operación pendiente de ejecutar tras la llamada recursiva. En estas funciones, la llamada recursiva puede ser substituida simplemente por un salto al comienzo de la función que se llama, con lo que se ahorra espacio en el stack. De esto ultimo se encarga el compilador y es lo que se conoce como Tail Call Optimization (TCO a partir de ahora).

Así que aparentemente la TCO mola, ¿No?

El problema es que Ruby no tiene implementada TCO en su maquina virtual con lo que independientemente de como estructuremos nuestras funciones recursivas, siempre estaremos limitados por el tamaño de nuestra Stack.

Pero siempre hay solución para todo y con Ruby, más. En ésta página dan dos soluciones para tener una pseudo-TCO.

Copio y pego la primera solución:

class Class
  # Sweet stuff!
  def tailcall_optimize( *methods )
    methods.each do |meth|
      org = instance_method( meth )
      define_method( meth ) do |*args|
        if Thread.current[ meth ]
          throw( :recurse, args )
        else
          Thread.current[ meth ] = org.bind( self )
          result = catch( :done ) do
            loop do
              args = catch( :recurse ) do
                throw( :done, Thread.current[ meth ].call( *args ) )
              end
            end
          end
          Thread.current[ meth ] = nil
          result
        end
      end
    end
  end
end
 
class TCOTest
  # tail-recursive factorial
  def fact( n, acc = 1 )
    if n < 2 then acc else fact( n-1, n*acc ) end
  end
 
  # length of factorial
  def fact_size( n )
    fact( n ).size
  rescue
    $!
  end   
end
 
t = TCOTest.new
 
# normal method
puts t.fact_size( 10000 )  # => stack level too deep
 
# enable tail-call optimization
class TCOTest
  tailcall_optimize :fact
end
 
# tail-call optimized method
puts t.fact_size( 10000 )  # => 14808

Esta solución consiste en jugar con catch’s,throw’s y Thread.current para relanzar el mismo método una y otra vez sin tener que crear un nuevo frame en el Stack, ya que el codigo del metodo se encuentra definido en un bloque y por tanto reutiliza el codigo.

La segunda opción:

def fib(i, n = 1, result = 0)
  if i == -1
    result
  else
    i, n, result = i - 1, n + result, n
    redo
  end
end
 
fib(10000)

Esta solución consiste en hacer uso de la palabra redo la cual reinicia la ejecución de cualquier loop o iterador. El problema con redo es que, como acabo de decir, solo se puede utilizar en loops o iteradores y el método fib anterior no es ninguno de ellos. Por lo que el autor de la página de que se extrajeron las soluciones dice:

Unfortunately, “The redo statement restarts the current iteration of a loop or iterator”, so it only throws a LocalJumpError

Gracias señor espartano.

Así es, esto es Ruby y siempre hay un workaround para todo. En este caso, consiste en crear un nuevo método cuyo cuerpo este contenido en un bloque.

define_method(:acc) do |i, n, result|
  if i == -1
    result
  else
    i, n, result = i - 1, n + result, n
    redo
  end
end
 
def fib(i)
  acc(i, 1, 0)
end
 
fib(10000)  # Yeah!

Y ya podemos utilizar redo. Fin!!

Para mas información, hay un thread en esta lista de correo en el que debaten sobre este tema: Ruby tail recursion.