[RUBY] Visually understand Fibonacci numbers and recursive functions

Introduction

When I was trying to write the code to find the Fibonacci number, a recursive function came out and my head seemed to be punk, so I will write it as an article to organize it. The main is a recursive function, but I also explained about Fibonacci number and memoization, so please have a look.

What is the Fibonacci sequence?

Since it is not the main subject, I will omit a detailed explanation, but it is a sequence that starts with 0, 1 or 1, 1 and becomes the next number when the numbers before the previous two are added. Like this.

Recurrence formula

"Wow, some difficult characters came out. Go back." If you are a liberal arts student who went home thinking that, please get along with me a little more. I'm a stubborn writer, but I managed to understand and chew it, so it's okay. Maybe.

In the image of the previous item, the sequence ends with 21, but what is the next number? Each number that makes up a sequence is called a "term" in the sequence, but let's number this term. It is an image to give a sequence number. I want to find the number next to 21, that is, the 9th number. Considering the property that "adding the previous two numbers gives the next number", it is 7th + 8th . 13 + 21 = 34 . What happens if you recreate the formula by paying attention to the "numbers" in the sequence? 7th + 8th = 9th Let's play with the above formula a little more. No. 7 is two before No. 9, and No. 8 is one before No. 9. (9-2nd) + (9-1st) = 9th , isn't it?

3 points

――The 0th number is 0 ――The first number is 1 ――The second and subsequent numbers are the next number when the previous two numbers are added together.

Then, how to find the nth number in the Fibonacci sequence (F)?

　\large{F_{0} = 0,}\\
　\large{F_{1} = 1,}\\
　\large{F_{n} = F_{n-2} + F_{n-1}}　\small{(n ≥ 2)}

It is said that the formula created by utilizing the relationship between the terms of the sequence is called the recurrence formula. This recurrence formula has a recursive definition, so you can easily write a program using recursive calls.

Recursive function

Before explaining what a recursive function is, let's first look at what kind of program is applied using the above recurrence formula.

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

As I wrote above, the 0th number = 0, the 1st number = 1, so if these two choices are true, return n is returned. After that, you can write the program in the same way as the recurrence formula. There is another fibonacci function in the function called fibonacci, and such a function that calls itself is called a recursive function .

Process flow

So what is the processing flow? Recursive call Process by entering yourself in the function → Further process by entering yourself in it ... Repeat the loop until it gets caught in return. For example, when n = 6, the second line is skipped due to a condition mismatch and proceeds to the third line. In the third line, fibonacci (4) + fibonacci (5), and the processing of fibonacci (4) starts.

It's hard to understand if it's a sentence, so let's make a diagram.

It loops until it hits a return like this. By adding 0 or 1 which is the return value of the loop in order, the nth number is finally obtained.

Weaknesses of recursive functions

As some of you may have noticed, there is also a weakness in the simple and convenient recursive call. That is calculating the same term over and over again ! It is not a big loop to find the 6th number as above, but when finding the 100th number, it takes a long time to finish the process because the same calculation is repeated many times. It will take. Memoization makes up for this shortcoming.

Memoization

If you look at the figure above, there is a part where exactly the same processing as A, B, C is performed again. Therefore, it is a memoization that literally makes a memo (cache) of the calculated contents once and then only glances at the memo from the second time onward. Click here for the program rewritten using memoization

def fibonacci(n)
  @memo ||= []
  return n if n == 0 || n == 1
  @memo[n] ||= fibonacci(n - 2) + fibonacci(n - 1)
end

||=Is "||The self-assignment operator of the operator. If the left side is false or undefined, it means that the right side is assigned to the left side. In the second line, prepare a memo pad called memo, and in the fourth line, if the value has not been calculated yet, make a note of it.

Now you can find the 100th number in an instant. Thank you for your hard work!

in conclusion

Thank you for visiting our website. There seem to be other ways to find the Fibonacci number, so I would like to try various things.