[C language] Fibonacci sequence [recursion and iteration]

One 、 Background introduction

Fibonacci sequence （Fibonacci sequence）, also called The golden section The sequence , Leonardo the mathematician · Fibonacci （Leonardo Fibonacci） Take rabbit breeding as an example , It is also called “ Rabbit Series ”.

【 Rabbit breeding problem 】

generally speaking , Two months after the rabbit was born , It has the ability to reproduce , A pair of rabbits can give birth to a pair of little rabbits every month . If all the rabbits don't die , How many pairs of rabbits can we breed in a year ？

The following table can be listed by analogy ：

Months elapsed	0	1	2	3	4	5	6	7	8	9	10	11	…
Number of pups	1	0	1	1	2	3	5	8	13	21	34	55	…
The number of Rabbits	0	1	1	2	3	5	8	13	21	34	55	89
Population logarithm	1	1	2	3	5	8	13	21	34	55	89	144

Number of pups = The number of adult rabbits in the previous month

The number of Rabbits = The number of adult rabbits in the previous month + The number of cubs in the previous month

Population logarithm = The number of adult rabbits this month + The number of cubs this month

You can see the number of cubs 、 The number of Rabbits 、 The total logarithms form a sequence . This sequence has very obvious characteristics , That is ： The sum of the preceding two adjacent items , Constitutes the latter item .

in short , Here are five points ：

（1） Chinese name ： Fibonacci sequence

（2） Alias ： Golden section series 、 Rabbit Series

（3） English name :Fibonacci sequence

（4） The proposer ： leonardo · Fibonacci

（5） expression ：F[n]=F[n-1]+Fn-2

Two 、 Thought analysis

3、 ... and 、 Code implementation

// Recursive method to solve Fibonacci sequence problem 
#include<stdio.h>
int fib(int n)
{
    
	if (n <= 2)
	{
    
		return 1;
	}
	return fib(n - 1) + fib(n - 2);
}
int main()
{
    
	int n;
	scanf("%d", &n);
	int ret = fib(n);
	printf("%d\n", ret);
	return 0;
}

Four 、 Expanding reading

【 explain ： At present, it is enough to ask for understanding , Just know how to check when you use it . however , At present, in my opinion , It should not be used ...】

1. characteristic

1. Square and antecedents

【 In particular ： Odd and even terms refer to the odd and even number of terms , It's not Index The parity of the numbers of the column itself 】

2. Sum of odd terms

3. Sum even terms

4. Sum of squares

5. Binomial relationship

6. Other formulas

2. application

1. The golden section

As the number of items in a sequence increases , The ratio of the former to the latter is getting closer The golden section The numerical 0.6180339887……

2. Yang hui triangle

3. Rectangular area

The sum of the squares of the first several items of the Fibonacci sequence can be regarded as squares of different sizes , Because of Fibonacci's recurrence formula , They can be assembled into a large rectangle . So the sum of the areas of all the small squares is equal to the area of the large rectangle . Then we can get the following identity ：

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-t6iut1ud-1651491444176)(https://bkimg.cdn.bcebos.com/formula/4e3acee4042a4f988211432f74909cf6.svg)]

4. In nature “ coincidence ”

Two French scientists conducted computer simulation experiments on the process of petal formation , It is proved that when the system keeps the lowest energy , Flowers will grow petals in Fibonacci sequence .

3. Related issues

① There is a flight of stairs with 10 Stepped steps , Stipulate that each step can only span one or two levels , To get on the 10 There are several different steps ?

This is a Fibonacci sequence ： There is a way to climb the first step ; Climb two steps , There are two ways to register ; Climb three steps , There are three ways to register ; Climb four steps , There are five ways to register ……

1,2,3,5,8,13…… therefore , Climb level 10 , Yes 89 Seed walking method .

【 explain ： Because the problem of jumping steps occurs frequently , So I wrote a separate blog to analyze this problem , Interested partners can move my 【C/C++ Summary of special exercises 】 to glance at 】

② Find the of recursive sequence General formula

from Mathematical induction You can get ：

, Substitute the general term of Fibonacci sequence into , Simplification results in .

Reference resources ：
Baidu Encyclopedia

5、 ... and 、 Iterative implementation of Fibonacci number solution code demonstration

// The iterative method realizes the n Fibonacci number solution 
#include<stdio.h>
int fib(int n)
{
    
	if (n <= 2)
		return 1;
	int a = 1, b = 1,ret=0;
	int i;
	for (i = 3;i <= n;i++)
	{
    
		ret = a + b;
		a = b;
		b = ret;
	}
	return ret;
}
int main()
{
    
	int n;
	scanf("%d", &n);
	int ret = fib(n);
	printf("%d\n", ret);
	return 0;
}