1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

require 'recursive'
require 'benchmark'

# The old & slow fib
def fib(i)
  if i < 2
    1
  else
    fib(i - 1) + fib(i - 2)
  end
end

# With tail opimizing
def tail_fib_helper(i, n, result)
  if i == -1
    result
  else
    tail_fib_helper(i - 1, n + result, n)
  end
end

def tail_fib(i)
  tail_fib_helper(i, 1, 0)
end

# With real tail optimizing:
tail(:real_tail_fib_helper) do |i, n, result|  
  if i == -1
    result
  else
    recurse do
      i, n, result = i - 1, n + result, n
    end
  end
end

def real_tail_fib(i)
  real_tail_fib_helper(i, 1, 0)
end 

# Benchmarking: 
Benchmark.bm(20) do |x|
  x.report("30 - regular fib     ") { fib(30) }
  x.report("30 - tail fib        ") { tail_fib(30) }
  x.report("30 - real tail fib   ") { real_tail_fib(30) }
  x.report("30000 - tail fib     ") { tail_fib(30000) rescue puts "Stack level too deep!"}
  x.report("30000 - real tail fib") { real_tail_fib(30000) }
end

# Results:
#                           user     system      total        real
# 30 - regular fib       6.000000   0.070000   6.070000 (  6.689649)
# 30 - tail fib          0.000000   0.000000   0.000000 (  0.000085)
# 30 - real tail fib     0.000000   0.000000   0.000000 (  0.000596)
# 30000 - tail fib       Stack level too deep!
# 30000 - real tail fib  0.830000   0.060000   0.890000 (  0.913457)