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.

• source ~/grad_members_20f/members/batamon-427/task10.org