这个一道递归优化问题

递归优化

题目表述
优化一下代码：

#include <iostream>
using namespace std;
int f(int n)
{
	if (n < 0) return 0;
	if (n == 0) return 1;
	return f(n - 1) + f(n - 2);
}
int main()
{    
	int n;
	cin >> n;
	cout << f(n);
	return 0;
}

输入
一个小于50的正整数n。
输出
f(n)，不要换行。
样例输入
3
样例输出
3

分析

  这个题目看起来没有什么意思，但是我们通过分析计算我们会发现。
  1. 递归50次后$int$是否够存，
  2. 递归50次后会不会爆栈。
  3. 我们应该如何优化。
  我们将代码复制到编辑器里面后编译会发现在输入49后$int$会溢出说明这49的递归后是一个超过21亿的数，所以我们应该使用$long$ $long$来储存这个庞大的数值。然后就是爆栈的问题，在使用$long$ $long$之后还是能计算出来的说明还没有爆栈，还能计算。然后就是递归的优化问题了。

什么是递归优化？

  递归优化是由于递归多次后递归深度过大，导致爆栈。或者是由于递归深度过深之后时间过长，导致之间效率低下。所以我们常见的递归优化有两种。

1. 尾递归。
2. 将递归改循环。
   两种方法，我们在记忆化之后我们发现这些数列之间的插值满足斐波拉切数列。所以我们就可以把这个递归函数改成一个循环函数。就可以实现对递归的优化。

答案

#include <iostream>
using namespace std;
/*int f(int n)
{
	if (n < 0) return 0;
	if (n == 0) return 1;
	return f(n - 1) + f(n - 2);
}*/


long long  fibo(int n)
{
    long long nFirst = 0;
    long long nSecond = 1;
    long long  nThird = 0;
    for(int i = 2 ; i <= n; i++){
        nThird = nFirst + nSecond;
        nFirst = nSecond;
        nSecond = nThird;
    }
    return nThird;
}

long long f(int n){
    long long count = 1;
    if(n == 1){
        return 1;
    }
    for (int i = 1; i < n; i++)
    {
        count += fibo(i);
    }
    return count+1;
}

int main()
{    
	int n;
	cin >> n;
	cout << f(n);
	return 0;
}