##To iterate is human, to recurse divine. ~ L. Peter Deutsch## by “Manuel Vidaurre”

At April 12, Ray Hightower posted in his blog “Recursion and Memoization”. There he highlights the pitfalls of recursion and use Memoization to avoid the performance penalties of open stack recursions. Memoization is an optimization technique used primarily to speed up computer programs by keeping the results of expensive function calls and returning the cached result when the same inputs occur again.

###Before Memoization###

# Calculate the nth Fibonacci number, f(n).
def fibo (n)
  if n <= 1
    return n
  else
    value = fibo(n-1) + fibo(n-2)
    return value
  end
end

# Display the Fibonacci sequence.
(1..40).each do |number|
  puts "fibo(#{number}) = #{fibo(number)}"
end

###After Memoization###

# Fibonacci numbers WITH memoization.
# Initialize the memoization array.
@scratchpad = []
@max_fibo_size = 50
(1..@max_fibo_size).each do |i|
  @scratchpad[i] = :notcalculated
end

# Calculate the nth Fibonacci number, f(n).
def fibo (n)
  if n > @max_fibo_size
    return "n must be #{@max_fibo_size} or less."
  elsif n <= 1
    return n
  elsif @scratchpad[n] != :notcalculated
    return @scratchpad[n]
  else
    @scratchpad[n] = fibo(n-1) + fibo(n-2)
    return @scratchpad[n]
  end
end

# Display the Fibonacci sequence.
(1..50).each do |number|
  puts "fibo(#{number}) = #{fibo(number)}"
end

My comment to him was “Nice, but if you use tail-recursion with invariants the effect is not so dramatic. As is in my gist”:

###Using tail-recursion###

# Calculate the nth Fibonacci number, f(n). Using invariants
def fibo_tr(n, acc1, acc2)
  if n == 0
    0
  elsif n < 2
    acc2
  else
    return fibo_tr(n - 1, acc2, acc2 + acc1)
  end
end
 
def fibo (n)
  fibo_tr(n, 0, 1)
end 
 
# Display the Fibonacci sequence.
(1..40).each do |number|
  puts "fibo(#{number}) = #{fibo(number)}"
end

##What is different here? tail-recursion or tail call.##
In the original implementation, Ruby must “remember” the return address, so that it can return to that location with the result once the call is complete. Typically, this information is saved on the call stack, a simple list of return locations in order of the times that the call locations they describe were reached. That is the reason after some iterations the program is running slower and slower.

For the implementation using tail-recursion, I used two accumulators acc1 and acc2 for implementing the tail call. Why is this important? Because for tail calls, there is no need to remember the place we are calling from – instead, we can perform tail call elimination by leaving the stack alone, and the newly called function will return its result directly to the original caller. The accumulators are the mean for returning the result to the original caller.

I was a little amazed for the answer that Ray Hightower to my comment: “Manuel, this is good. I had never heard of tail-recursion until your post. And your code was a subject of discussion at the last ChicagoRuby meeting. Thanks!”. That give me the light that maybe other people are not using tail-recursion for their benefit. Hopefully this will help.

##Revised post##
In preparation to my talk in Ruby GDL at July, 2014. I did some refactoring to my code for being more expresive, mainly related to better arguments names.

###Using tail-recursion revised version###

# Calculate the nth Fibonacci number, f(n). Using invariants
def fibo_tr(n, next, result)
  if n == 0
    0
  elsif n < 2
    result
  else
    return fibo_tr(n - 1, next + result, next)
  end
end
 
def fibo (n)
  fibo_tr(n, 1, 0)
end 
 
# Display the Fibonacci sequence.
(1..40).each do |number|
  puts "fibo(#{number}) = #{fibo(number)}"
end

As an added bonus this is the same code in Elixir

###Using tail-recursion Elixir version###

# Calculate the nth Fibonacci number, f(n). Using invariants
defmodule Fibo do
  def of(n) when n < 1, do: IO.puts "n should be positive"
  def of(n), do: of(n, 1, 0) 
  def of(1, _, result), do: result
  def of(n, next, result), do: of(n - 1, next + result, next)
end
 
# Display the Fibonacci sequence.
Enum.each 0..40, &IO.puts "fibo(#{&1}) = #{Fibo.of(&1)}"

The Elixir code use the pattern matching in functions that is very expressive.

Creative Commons License
To iterate is human, to recurse divine! by Manuel Vidaurre. Agiltec is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
comments powered by Disqus