preface

A new series, “Easy to Understand Data Structures and Algorithms by Looking at Pictures”, is launched, mainly using pictures to describe common data structures and algorithms, easy to read and understand. This series includes dozens of examples of heaps, queues, lists, trees, graphs, sorts, and more.

Fibonacci

Leonardo Pisano (Fibonacci, 1175 — 1250), also known as Leonardo Bigollo, was an Italian mathematician. He was the first person in the West to study the Fibonacci sequence and introduced the modern system of positional representation of written numbers and multipliers to Europe. His major works include The Book of Calculation, The Practice of Geometry, and the Book of Square Numbers.

Fibonacci numbers

Fibonacci sequence, also known as the Golden section sequence or rabbit sequence, is listed as 0, 1, 1, 2, 3, 5, 8, 13, 21, 34… And you can see that it has the property that the sum of the first two terms equals the last term.

The rabbit problem

The Fibonacci sequence can be used to describe the problem of rabbit reproduction. Generally speaking, rabbits are fertile after two months of birth, and a pair of rabbits can give birth to one pair of rabbits per month. If all rabbits died, how many pairs of rabbits could be bred in a year? And the actual result is, the first month and the second month, the rabbits haven’t been able to reproduce, so they only have one pair. The first pair is born in the third month, so there are two pairs. The fourth lunar rabbit went on to give birth to one pair, and another pair was not fertile yet, making a total of three pairs. Similarly, the logarithms of rabbits from month 5 to month 12 correspond as follows.
months 1 2 3 4 5 6 7 8 9 10 11 12
logarithmic 1 1 2 3 5 8 13 21 34 55 89 144

expression


The recursive implementation

int fib(int n){
    if (n == 0)
       return 0;
    if (n == 1)
       return 1;
    return fib(n - 1) + fib(n - 2);
}
Copy the code

If n=4, look at the stack of recursive procedures.

(1) Call the fib function and pass in the parameter value 4.

② fib(4)=fib(3)+fib(2), need to continue to call fib(3), and fib(2) does not enter the execution stack.

③ fib(3)=fib(2)+fib(1), fib(2) needs to be called, and fib(1) does not enter the execution stack.

④ FIB (2)=fib(1)+fib(0). You need to call fib(1), and fib(0) does not enter the execution stack.

⑤ fib(1) returns 1, stops calling down, and then fib(0) of the previous step enters the stack.

If fib(0) returns 0, fib(2)=fib(1)+fib(0)=1

And then, the stack goes back to ③, and since fib of 3 is equal to fib of 2 plus fib of 1, we’re pushing fib of 1.

If fib(1) returns 1, fib(3)=fib(2)+fib(1)=1+1=2.

And then, we’re going to go back into ②, because fib of 4 is fib of 3 plus fib of 2, so we’re going to push fib of 2. Fib of 2 is fib of 1 plus fib of 0, so I’m pushing fib of 1. So fib of 1 returns 1, and then fib of 0 continues to be pushed. So fib of 2 is fib of 1 plus fib of 0 is 1, and then fib of 4 is fib of 3 plus fib of 2 is 3.

————- Recommended reading ————

Summary of my open Source projects (Machine & Deep Learning, NLP, Network IO, AIML, mysql protocol, Chatbot)

Why to write “Analysis of Tomcat Kernel Design”

2018 summary data structure algorithms

2018 Summary machine learning

2018 Summary Java in Depth

2018 Summary of natural language processing

2018 Summary of deep learning

2018 summary JDK source code

2018 Summary Java concurrency Core

2018 summary reading passage

Talk to me, ask me questions:

Welcome to: