Fibonacci sequence with (memoization) recursive function

!macOS-11.1!ruby-2.7.2p137

Preface (Introduction)

Output the Fibonacci sequence using a recursive function.

Fibonacci

The fib function, which returns the Fibonacci number, has the following relationship.

fib(n) = fib(n-1)+fib(n-2)
0 1 1 2 3 5 8 13 21 ...

fib(0) = 0

Since the first term fib (0) of the Fibonacci sequence is defined as 0

fibonacci.rb

def fib(n)
  if n==0
    return 0
  end
end

will do.

Use the previously created assert \ _equal for this test.

fibonacci.rb

require './assert_equal'
puts assert_equal(0, fib(0))

The output is

> ruby fibonacci.rb

expected :: 0
result   :: 0
succeeded in assert_equal.

It worked as expected.

fib(1) = 1

The second term fib (1) of the Fibonacci sequence is defined as 1, so add to the above code.

fibonacci.rb

require './assert_equal'

def fib(n)
  if n==0
    return 0
  elsif n==1
    return 1
  end
end

puts assert_equal(0, fib(0))
puts assert_equal(1, fib(1))

The output is

expected :: 0
result   :: 0
succeeded in assert_equal.

expected :: 1
result   :: 1
succeeded in assert_equal.

This is also as expected.

fib(n) = fib(n-1) + fib(n-2)

Even if n becomes larger from here, I will return the Fibonacci number properly. Before that, it was messed up so I will refresh it once.

fibonacci.rb

def fib(n)
  return 0 if n==0
  return 1 if n==2
end

Furthermore, the processing of fib (n) = fib (n-1) + fib (n-2) is added.

fibonacci.rb

def fib(n)
  return 0 if n==0
  return 1 if n==1
  return fib(n-1) + fib(n-2)
end

Use Array.each to clean the test for confirmation.

fibonacci.rb

[[0,0], [1,1],[2,1],[3,2],[4,3],[5,5],[6,8],[7,13],[8,21],[9,34]].each do |index, expected|
  puts assert_equal(expected, fib(index))
end

The output is

expected :: 0
result   :: 0
succeeded in assert_equal.

expected :: 1
result   :: 1
succeeded in assert_equal.

expected :: 1
result   :: 1
succeeded in assert_equal.

expected :: 2
result   :: 2
succeeded in assert_equal.

expected :: 3
result   :: 3
succeeded in assert_equal.

expected :: 5
result   :: 5
succeeded in assert_equal.

expected :: 8
result   :: 8
succeeded in assert_equal.

expected :: 13
result   :: 13
succeeded in assert_equal.

expected :: 21
result   :: 21
succeeded in assert_equal.

expected :: 34
result   :: 34
succeeded in assert_equal.

This also worked fine.

bonus

At this rate, as n increases, the processing becomes exponentially heavy. The reason is that fib (n-1) and fib (n-2) are calculated separately to obtain fib (n).

Therefore, let's lighten the process by using a technique called memoization recursion.

fibonacci_opt.rb

@memo = {}

def fib(n)
  return @memo[n] if @memo.has_key?(n)
  return 0 if n == 0
  return 1 if n == 1
  return @memo[n] = fib(n-1) + fib(n-2)
end

puts fib(100)

The output is

> ruby fibonacci_opt.rb
-> 354224848179261915075

This result was correct.

Reference material

-Chart type ruby-V (Recursive Fibonacci) -Story of speed improvement by memoization -Fibonacci sequence up to 100th