[RUBY] 10th class: Recursion

Reference site

Chart type ruby-V (Recursive Fibonacci)

What is Recursive?

Of the behavior in a function, the process of calling itself.

Theme: Fibonacci sequence

The Fibonacci number is defined based on the following formula. Reference: wikipedia: Fibonacci number

Let fib (n) represent the nth Fibonacci number ・ Fib (0) = 0 ・ Fib (1) = 1 ・ Fib (n) = fib (n-1) + fib (n-2)

When the n = 0 to 10th Fibonacci numbers are arranged, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Find the Fibonacci sequence created in this way by recursive processing

Implementation example

Let's find it from n = 0,1 which is not found by the rule of fib (n) = fib (n-1) + fib (n-2)

require './assert_equal.rb'

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

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

9th assert \ _equal reappears. The declaration on the first line makes it callable. The job of assert \ _equal this time is to test whether the function fib is working properly.

I'm worried about duplicate assert \ _equal, so I make it an array. (Refactoring)

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

Make the part of fib (n) = fib (n-1) + fib (n-2) while cleaning the description.

require './assert_equal.rb'

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

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

The output result looks like this

["expected", 0]
["result", 0]
true

["expected", 1]
["result", 1]
true

["expected", 1]
["result", 1]
true

["expected", 2]
["result", 2]
true

["expected", 3]
["result", 3]
true

["expected", 5]
["result", 5]
true

["expected", 8]
["result", 8]
true

["expected", 13]
["result", 13]
true

["expected", 21]
["result", 21]
true

["expected", 34]
["result", 34]
true

note

・ If you restart too much, the processing will be heavy and an infinite loop will occur, so be careful.


Recommended Posts

10th class: Recursion
11th class: Class
9th class: assert_equal
8th class: rake
5th class: Output
7th class: if, else
11th :: ruby_VI (hello class)
6th class: Variables, method
5th
6th
6th
9th
7th
11th
9th
7th
11th
10th
10th
Anonymous class (anonymous class)
Special Lecture on Multi-Scale Simulation: 11th (class)
Class method
ObjectMapper class
ArrayList class