斐波那契数（递归&非递归）

斐波那契数：
亦称之为斐波那契数列（意大利语： Successione di Fibonacci)，又称黄金分割数列、费波那西数列、费波拿契数、费氏数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波那契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*），用文字来说，就是斐波那契数列列由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。

非递归：

#define  _CRT_SECURE_N0_WARNINGS 1
#include<stdio.h>

int fib(int n)
{
    int a = 1;
    int b = 1;
    int ret = a;
    while (n - 2 > 0)
    {
        ret = a + b;
        a = b;
        b = ret;
        n--;
    }
    return ret;
}

int main()
{
    printf("%d\n",fib(4));
    return 0;
}

运行结果：

非递归斐波那契数.png

递归：

#define  _CRT_SECURE_N0_WARNINGS 1
#include<stdio.h>

int fib(int n)
{
    if (n <= 2)
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}
int main()
{
    printf("%d\n",fib(4));
    return 0;
}

运行结果：

递归斐波那契数.png

递归的两个必要条件：
1 存在限制条件，满足这个限制条件，递归结束
2 每次递归调用之后越来越接近这个限制条件