This time, we will create a program to find the Fibonacci sequence using the recursive method.
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.
The Fibonacci sequence can be created using a recursive function.
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
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
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
https://qiita.com/pokotyan/items/53e92a21805f651173aa
Recommended Posts