啊我摔倒了..有没有人扶我起来学习....

前言

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”

一、递归实现斐波那契数

• 首先，我们要知道，要实现递归，就要：

  1. 把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解
  2. 其次，递归不能无限循环下去，需要结束条件
• 然后，用递归的思想去分析斐波那契数的特点，把它拆分成一个个相似的小问题，再确定结束递归的条件

• 我们发现，除了前两个数1，后面每个数都是它的前两个数之和。于是我们就可以确定出：

  1. 每一个小问题就是==用前两个数之和计算出后一个数==
  2. 停止递归的条件是当n<=2
• 所以，第n个斐波那契数肯定是，第(n-1)个斐波那契数和第(n-2)个斐波那契数之和。根据这个想法，写出代码，并加上结束条件

int fibo_num(int n)
{
    if (n > 2)
        return fibo_num(n - 1) + fibo_num(n - 2);
    else
        return 1;
}

输出结果：

二、循环实现斐波那契数

• 其实非递归方法（循环）更容易想到怎么写，刚刚也已经分析过了。只要给出前两个数1，然后每前两个数之和就是下一个数

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//斐波那契数(非递归)
int main()
{
    int n = 0;
    while (~scanf("%d", &n))
    {
        if (n <= 2)
            printf("第%d个斐波那契数是1\n", n);
        else
        {        
            int a = 1;
            int b = 1;
            int c = 0;
            for (int i = 3; i <= n; i++)
            {
                c = a + b;
                a = b;
                b = c;
            }
            printf("第%d个斐波那契数是%d\n", n, c);
        }
    }
    return 0;
}

输出结果：

三、比较递归与非递归实现斐波那契数

3.1 非递归

• 很简单的原理没啥好讲的哈哈。咱们就看计算的次数叭~

咱们加入 count来计数

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//斐波那契数(非递归)
int main()
{
    int n = 0;
    int count = 0;
    while (~scanf("%d", &n))
    {
        if (n <= 2)
            printf("第%d个斐波那契数是1\n", n);
        else
        {        
            int a = 1;
            int b = 1;
            int c = 0;
            for (int i = 3; i <= n; i++)
            {
                count++;
                c = a + b;
                a = b;
                b = c;
            }
            printf("第%d个斐波那契数是%d\n", n, c);
            printf("循环了%d次\n", count);
        }
    }
    return 0;
}

输出结果：

3.2 递归

• 假如我们求第6个斐波那契数是8，我们来看一下递归的原理图

可以看出来，貌似计算了挺多次，我们用代码算算看

#include<stdio.h>
//斐波那契数(递归)
count = 0;
int fibo_num(int n)
{  
    count++;
    if (n > 2)
        return fibo_num(n - 1) + fibo_num(n - 2);
    else
        return 1;
}

int main()
{
    int n = 0;

    while (~scanf("%d", &n))
    {
        int result = fibo_num(n);
        printf("第%d个斐波那契数是%d\n", n, result);
        printf("递归了%d次\n", count);
    }
    return 0;
}

输出结果： 居然用了这么多次！！！

• 最恐怖的还不是这，假如你要计算第40个斐波那契数？

• 假如第50个呢？反正博主的电脑没跑出来。。。

四、总结

• 总之，递归让代码变得简洁，但并不代表效率就提高了，要具体情况具体分析哦~