不容易系列 递归求解

解题思路:

本人在写时，发现可以用递归来写。

什么是递归：（忙人请略过）

程序调用自身的编程技巧称为递归。递归做为一种算法在程序设计语言中广泛应用。递归，就是在运行的过程中调用自己。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

下面是递归方程：

int f(int n)
{
	if(n==1)return 1;
	return 2*f(n-1)+1;
}

个人觉得代码算短的，递归一般思维复杂度不高，但时间复杂度就不好说了

注意事项:

递归要有终止条件：即n=1时返回1，在输出时，别忘了加3

参考代码:

#include<bits/stdc++.h>
using namespace std;
int f(int n)
{
	if(n==1)return 1;
	return 2*f(n-1)+1;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1,x;i<=n;++i)
	{
	        cin>>x;
	    cout<<3+f(x)<<endl;	
	}	
    return 0;
}

看到这里，点个赞再走吧！