10th

This time, we will create a program to find the Fibonacci sequence using the recursive method.

What is the Fibonacci sequence?

The Fibonacci sequence is "a sequence in which the first and second numbers are 1, and the third and subsequent numbers are the sum of the immediately preceding two numbers", and is defined by the following recurrence formula.

F_{0} = 0
F_{1} = 1
F_{2} = 1
F_{n+2} = F_{n+1} + F_{n} (n \geq 0)

The Fibonacci sequence can be created using a recursive function.

What is a recursive method?

Recursion is to call it again in the program. For example, there are the following programs.


def sum(array)
 return 0 if array.empty?
 top=array.shift
 top+sum(array)
end

p sum([1,2,3,4,5]) # =>15

program

Let's start by implementing the 0th, 1st and 2nd terms.


def fib(n)
 #In the case of item 0
 if n==0 then
  return 0

 #In the case of paragraph 1
 else n<=2 and n!=0 then
  return 1  
 end
end

Next, we implement the nth term. Term n is

F_{n}=F_{n-1}+F_{n-2}

Because you can ask at

def fib(n)
  #In the case of item 0
  if n==0 then
   return 0

  #In the case of paragraph 1
  else n<=2 and n!=0 then
   return 1

  #Item n( n>2 )in the case of
  else
   return fib(n-2)+fib(n-1)
  end
end

for n in 0..10 do
 print 'n=',"#{n} ",' fib=',"#{fib(n)}", "\n" 
end

Just write. Here, in order to verify whether the execution result is correct, the program assert \ _equal \ _fin created last time is used. Just in case, the source code of the program is shown below.

assert_equal_fin.rb



require 'colorize'

def puts_vals(expected, result)
  puts "expected :: #{expected}"
  puts "result   :: #{result}"
end
def assert_not_equal(expected, result)
  puts_vals(expected, result)
  print expected != result ?
	  "succeeded in #{__method__}.\n".green :
	  "failed in #{__method__}.\n".red
end
def assert_equal(expected, result)
  puts_vals(expected, result)
  print  case expected == result
	 when true  ; "succeeded in #{__method__}.\n".green
	 when false ; "failed in #{__method__}.\n".red
	 end
end

if $PROGRAM_NAME == __FILE__
  assert_equal(1, 1)
  assert_equal(1, 2)
  assert_not_equal(1, 2)
  assert_not_equal(1, 1)
end


Even so, the verification part of the output result is as follows.

test=[[0,0],[1,1],[10,55],[30,832040]]
test.each do |index, expected|
  puts assert_equal(expected, fib(index))
end

From the above, the final form of the program is as follows. As the contents, the 0th to 10th terms of the Fibonacci sequence are output, and it is verified by assert \ _equal whether there are some terms.

fibonacci.rb


require './assert_equal_fin'

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

  elsif n <=2 and n!=0 then
    return 1

  else
    return fib(n-2)+fib(n-1)
  end
end

for n in 0..10 do
  print 'n=',"#{n} ",' fib=',"#{fib(n)}", "\n"
end

test=[[0,0],[1,1],[10,55],[30,832040]]
test.each do |index, expected|
  puts assert_equal(expected, fib(index))
end

References

https://qiita.com/pokotyan/items/53e92a21805f651173aa


Recommended Posts

5th
6th
6th
9th
7th
11th
9th
7th
10th
10th
11th class: Class
9th class: assert_equal
10th class: Recursion
8th class: rake
13th (thor, rubocop)
5th class: Output
TDD study # 2 (July 13th, 2020)
7th class: if, else
TDD study # 5 (July 18th, 2020)
TDD study # 4 (July 16th, 2020)
11th :: ruby_VI (hello class)
6th class: Variables, method
11th, Classification with Ruby
TDD study # 3 (July 15th, 2020)