斐波那契数列

我在本地IDE中写了两种方法实现斐波那契数列，现在进行对比

//递归法：
int Fibonacci(int n)
	{
		if (n == 0)
		{
			return 0;
		}
		else if (n == 1||n == 2)
		{
			return 1;
		}
		return Fibonacci(n - 1) + Fibonacci(n - 2);
	}

假设我们求第5个斐波那契数列 二叉树的节点数=（2^（n-1))-1，因此时间复杂度为O（2^n），递归栈的最大深度为n-1,因此空间复杂度为O（n），在计算中，n=3的时候计算了两次，因此导致递归法的时间复杂度上升。

//非递归法
int Fibonacci2(int n)
	{
		vector<int> res;
		if (n == 0)
		{
			return 0;
		}
		res.push_back(0);
		res.push_back(1);
		for (int i = 2; i <= n; ++i)
		{
			res.push_back(res[i - 1] + res[i - 2]);
		}
		return res.back();
	}

非递归法中程序循环了n-2次，因此时间复杂度为O（n）.