大前端

斐波那契数列数列，又叫做兔子数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入。描述的是这样的一个数列，0，1，1，2，3，5，8…有两种写法，一种是递归法，一种是动态规划法。
一，递归法
递归需要用到栈，一般需要一个递推的公式，还需要一个递归的终止条件，这里的终止条件就是当n等于0，或者当n等于1的时候。

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

二，动态规划法
第一种方法有一个缺点就是需要重复计算，比如fin[1],fin[0]就重复计算了好多次，如果可以把这些计算保存下来，就可以节约计算成本。这样就需要申请一个数组，保存计算的值。

#include <iostream>
using namespace std;
int vec[100] = { 0 };
int fib2(int n)
{
	int res;//接收结果。
	res = vec[n];
	if (res == 0)
	{
		if (n == 0)
		{
			return 0;
		}
		else if (n == 1)
		{
			return 1;
		}
		else
		{
			return fib2(n - 1) + fib2(n - 2);
		}
		vec[n] = res;
	}
	return res;
}