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

Recommended Posts

Fibonacci sequence with (memoization) recursive function
With Kotorin ―― 7. Scoping Function
Serverless Function with Micronaut
Introduced graph function with rails
Java to play with Function
[Illustration] Factorial recursive function [Ruby]
Login function with Spring Security
Memoization recursion with lambda expression
Login function implementation with rails
Ruby study memo (recursive function)
Iterator implementation (eg Fibonacci sequence)
Implement search function with form_with
[Illustration] Finding the sum of coins with a recursive function [Ruby]