Preface

Blogger homepage: Aaaafeng's homepage_CSDN

Niuke.com is a very useful tool for brushing questions. I recommend it to everyone:

Website link: Niuke.com

This series of blog posts is used as a notebook for writing questions, recording the thinking process of individuals facing some programming problems.If you have any questions, welcome to discuss and correct!Hope to work hard with you and grow together!

Problem description

Original title link: Fibonacci sequence

Solution ideas

Looking at the expression of fib(x), it is easy to see that this problem is very suitable for using the function's recursion to solve.Because its expression itself is also a recursive form.

如果对斐波拉契数列还不熟悉，可以试着将一些项列出来：1，1，2，3，5，8，13，21，34，55，89······

刚开始接触递归的时候，可能会莫名德就感觉它非常的难以理解，但其实没关系，多做一些题，自己多用几次，自然慢慢得就熟了。

Algorithm process:

For an x ​​passed in by the function fib(n):
1) Determine whether n is 1 or 2, if so, return 1 directly
2) If not, then进入递归，先计算第n 项的前两项（第n-1 和第n-2 ​​项），然后将它们的和作为值返回

在第二步When calculating the first two items, it is a two-step process of 1) and 2), which constitutes recursion

Core code implementation:

Note: This is just the implementation of the core code. As a function to complete the main algorithm task, it is not a complete runnable code.Call this function in the main function to complete the corresponding algorithm task.

int Fibonacci(int n ) {// write code hereif(n == 1 || n == 2)return 1;return Fibonacci(n - 1) + Fibonacci(n - 2);}

Summary

The implementation of this algorithm is still very simple. When we encounter some more complex recursive tasks, we can actually refer to the previous simple programs in turn, which may make our thinking clearer.

Let's work together!