G（x）=1/√5[ 1/(1-αx)-1/(1-βx) ]=1/√5[ (α-β)x+(α^2-β^2)x++] 原因：
1/(1-t)=1+t+t^2+t^3
将t分别替换成αx和βx，对应项合并，就可推导出
非递归和递归之间
1速度。递归函数是在不断的调用本身的函数，一般函数的调用返回，是比较费时间的，尤其是在递归深度较大时。所以个人觉得非递归的速度较好。
2空间。递归函数很明显，始终是在入栈，只有在最后才出栈，大量的浪费了堆栈空间。在这一点上非递归肯定要比递归好。
总结。个人认为递归函数只是在程序书写上简单明了，但实际运行个人不看好。
一个是O(N) 一个是O(NN)
<可以自由转载，但请注明以下内容，谢谢合作！>
<作者：Enoch Wang 引用自：http://chinawangquanspaceslivecom>
所谓递归，简而言之就是应用程序自身调用自身，以实现层次数据结构的查询和访问。 递归的使用可以使代码更简洁清晰，可读性更好（对于初学者到不见得），但由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多，而且，如果递归深度太大，可能系统资源会不够用。
往往有这样的观点：能不用递归就不用递归，递归都可以用迭代来代替。
诚然，在理论上，递归和迭代在时间复杂度方面是等价的（在不考虑函数调用开销和函数调用产生的堆栈开销），但实际上递归确实效率比迭代低，既然这样，递归没有任何优势，那么是不是就，没有使用递归的必要了，那递归的存在有何意义呢？
万物的存在是需要时间的检验的，递归没有被历史所埋没，即有存在的理由。从理论上说，所有的递归函数都可以转换为迭代函数，反之亦然，然而代价通常都是比较高的。但从算法结构来说，递归声明的结构并不总能够转换为迭代结构，原因在于结构的引申本身属于递归的概念，用迭代的方法在设计初期根本无法实现，这就像动多态的东西并不总是可以用静多态的方法实现一样。这也是为什么在结构设计时，通常采用递归的方式而不是采用迭代的方式的原因，一个极典型的例子类似于链表，使用递归定义及其简单，但对于内存定义(数组方式)其定义及调用处理说明就变得很晦涩，尤其是在遇到环链、图、网格等问题时，使用迭代方式从描述到实现上都变得不现实。 因而可以从实际上说，所有的迭代可以转换为递归，但递归不一定可以转换为迭代。
采用递归算法需要的前提条件是，当且仅当一个存在预期的收敛时，才可采用递归算法，否则，就不能使用递归算法。
递归其实是方便了程序员难为了机器，递归可以通过数学公式很方便的转换为程序。其优点就是易理解，容易编程。但递归是用栈机制实现的，每深入一层，都要占去一块栈数据区域，对嵌套层数深的一些算法，递归会力不从心，空间上会以内存崩溃而告终，而且递归也带来了大量的函数调用，这也有许多额外的时间开销。所以在深度大时，它的时空性就不好了。
而迭代虽然效率高，运行时间只因循环次数增加而增加，没什么额外开销，空间上也没有什么增加，但缺点就是不容易理解，编写复杂问题时困难。
因而，“能不用递归就不用递归，递归都可以用迭代来代替”这样的理解，Enoch不敢苟同，还是辩证的来看待，不可一棍子打死。
参考资料：
Fibonacci数列
无穷数列1,1,2,3,5,8,13,21,34,55，···，称为Fibonacci数列。它可以递归的定义为
1 n=0
F(n)= 1 n=1
F(n-1)+F(n-2) n>1
第n个Fibonacci数可递归地计算如下：
int Fibonacci ( intn)
{
If(n<=1)return 1;
ReturnFibonacci(n-1)+Fibonacci(n-2);
}
1+T(n-1)+T(n-2) n>1
Tn=
0 n<=1
时间复杂度为指数时间O(kn)
非递归计算如下：
Int Fibonacci(int n)
{
If(n<2)return 1;
else{
int a=b=1;
for(int i=0;i<n+2;i++)
{
b=a+b;
a=b-a;
return a+b;
}
}
}
时间复杂度为O(n)
T(n) = n+T(n-1) =n+n-1+T(n-2)==n+(n-1)+(n-2)++1+T(0)=(1+n)n/2=O(n^2)
理论计算机研究中，衡量算法一般从两个方面分析：时间复杂度和空间复杂度。空间复杂度跟时间复杂度是类似的，下面简单解释一下时间复杂度：对于一个数据规模为n的问题，解决该问题的算法所用时间可以用含有n的函数T(n)来表示。
对于绝大多数情况，只需要了解算法的一般性能而不考虑细节，也就是说，我们只关心函数T(n)的表达式的形式，而不关心表达式的常数系数等与数据规模没有关系的量值。
对于函数T(n)，我们又进一步将它简化为O(n)，即只考虑算法平均运行时间的“瓶颈”，也就是T(n)表达式中，关于变量n增长最快的哪一项。
扩展资料：
二进制整数的基数排序是一个非常特殊的情形，因为只有两个数字 0 和 1，故每次将数据分成 2 个小组。假设所有数据属于[0，21+m-1], m 为一整数，则先根据最高位（m 位）的数字将数据分成 2 个小组，分别属于[0，2m-1]和[2m，21 + m-1]；
根据次高位（m-1 位）的数字将[0，2m-1]的数据分成 2 个小组，分别属于[0，21 - m-1]和[21 - m，2m-1]，将[2m，21 + m-1]的数据分成 2 个小组，分别属于[2m，2m+21 - m-1]和[2m+21 - m，21 + m-1]；……；这完全类似于快速排序的分治算法结构，因而可以类似于快速排序实现该算法。
-超快速排序
你这循环是线性时间复杂度O(n)，循环n次只做了n次加法。
然而你这种递归写法是指数级别的时间复杂度O(2^n)，调用fib(n)会产生2个分支fib(n-1)和fib(n-2)，fib(n-1)和fib(n-2)各自又会产生两个分支变成4个分支，各自再产生两个变成8个……
可以大概分解一下：
fib(n)=fib(n-1)+fib(n-2)
=(fib(n-2)+fib(n-3))+(fib(n-3)+fib(n-4))
=((fib(n-3)+fib(n-4))+(fib(n-4)+fib(n-5)))+((fib(n-4)+fib(n-5))+(fib(n-5)+fib(n-6)))
=……（以此类推）
可以看到仅仅分解到第三层fib(n-4)就调用了3次，函数调用3次，计算量就是3倍，又不会因为你重复调用就把上次调用的结果直接返回给你，也就是fib(n-4)被重复计算了，n稍微一大，这种重复计算量是极其巨大的。
而用循环的话，a[n-4]仅仅只算了一次。2^40是40的多少倍？时间可想而知。
#include<iostream>
using namespace std;
//递归实现，效率不高，注意绝对值的取法。算法复杂度log(n)，空间复杂度O(logn)
double GetPower(int x, int y)
{
double ret = 0;
bool small = y < 0;
y = (y^(y>>31)) - (y>>31);
if (y == 0) return 1;
if (y == 1) return x;
ret = GetPower(x, y >> 1);
ret = ret;
if (y&1) ret = x;
return small 10/ret : ret;
}
//非递归实现，高效率的方式。算法复杂度log(n)，空间复杂度O(1)
double power(int x, int y)
{
double ret = 1;
int sign = y < 0;
y = (y^(y>>31)) - (y>>31);
while (y){
if (y&1) ret = x;
x =x;
y >>=1;
}
return sign 10/ret : ret;
}
int main(void)
{
int x, y;
while (cin >> x >> y){
cout << GetPower(x, y) << endl;
cout << power(x, y) << endl;
}
return 0;
}
扩展资料：
常见递归函数
1、复合算子，设f是n元函数，g1…gn是m元函数，复合算子将f，g1…gn变换成为如下的m元函数h：
h(x1…xm)=f1g1(x1，…xm)，…gn(x1，…xm))
2、递归算子，设f是n元函数 (≥0)，g是n+2元函数，递归算子将f，g变换成满足下列条件的h+1元函数h：
h(x1，…，xn，0)=f(x1，…xn)
h(x1，…xn，y+1)=g(x1，…xn，y，h(x1，…xn))
3、μ一算子，设f是n+1元函数，如果存在y，使f(x1，…xn，y)=0，我们以μyf(x1…xny)表示这样的y中的最小者，如果使f(x1…xny)=0的y不存在，我们说μyf(x1，…xny)无定义。μ-算子将n+1元函数f变换成下面的几元函数h
h(x1，…xn)=μyf(x1…xny)
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）