##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.

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