由斐波那契数列探究递推与递归

斐波那契数列定义：

斐波那契数列大家都非常熟悉。它的定义是：

对于给定的整数 x ，我们希望求出：$f(1)+f(2)+\dots +f(x)$ 的值。

有两种方法,分别是递推(迭代)与递归

具体解释如下图

备注：递推(迭代)的方式是利用开一个有 x 个元素的数组，表示由 x 种的状态，本质上是利用空间换时间，然后循环迭代每一个状态，其中一个新状态是由两个旧状态递推出来的，整个递推过程只需要 $O(n)$ 的时间复杂度，所以此种方法运行的时间复杂度要低于递归的方法。

递归的方法更像是一种暴搜(暴力搜索每一种状态)，所有搜索到的状态构成一颗递归搜索树，搜索的次数就是所有树上的节点的个数，可以看到递归搜索树的节点树远大于循环迭代次数，其时间复杂度大约为 $O(2^{n-2})$ 。

代码：

方法一：递推(迭代)

时间复杂度 $O(n)$

typedef long long ll;
const int N = 70;ll fib_dp(int x) //递推
{vector<ll> dp(N,0);dp[0] = 0,dp[1] = 1;for (int i = 2;i <= x;i ++ ) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[x];
}

方法二：递归

时间复杂度 $O(2^{n-2})$

typedef long long ll;
const int N = 70;ll fib_recursion(int x) //递归
{if (!x) return 0;else if (x == 1 || x == 2) return 1;else {return fib_recursion(x - 1) + fib_recursion(x - 2); //后序遍历的写法}
}