递归算法与⾮递归算法⽐较
⾮递归效率⾼；递归代码写出来思路清晰，可读性强。
⽣成可执⾏⽂件⼤⼩应该和编译器有关吧。。。。
递归的话函数调⽤是有开销的，⽽且递归的次数受堆栈⼤⼩的限制。
以⼆叉树搜索为例：
bool search(btree* p, int v)
{
if (null == p)
return false;
if (v == p->v)
return true
else
{
if (v < p->v)
return search(p->left, v);
else
return search(p->right, v);
}
}
如果这个⼆叉树很庞⼤，反复递归函数调⽤开销就很⼤，万⼀堆栈溢出怎么办？
现在我们⽤循环改写：
bool search(btree* p, int v)
{
while (p)
{
if (v == p->v)
return true;
else
{
if (v < p->v)
p = p->left;
else
p = p->right;
}
}
return false;
}
递归好处：代码更简洁清晰，可读性更好
递归可读性好这⼀点，对于初学者可能会反对。实际上递归的代码更清晰，但是从学习的⾓度要理解递归真正发⽣的什么，是如何调⽤的，调⽤层次和路线，调⽤堆栈中保存了什么，可能是不容易。但是不可否认递归的代码更简洁。⼀般来说，⼀个⼈可能很容易的写出前中后序的⼆叉树遍历的递归算法，要写出相应的⾮递归算法就⽐较考验⽔平了，恐怕⾄少⼀半的⼈搞不定。所以说递归代码更简洁明了。
递归坏处：由于递归需要系统堆栈，所以空间消耗要⽐⾮递归代码要⼤很多。⽽且，如果递归深度太⼤，可能系统撑不住。
楼上的有⼈说：
⼩的简单的⽤循环,,
太复杂了就递归吧,，免得循环看不懂
话虽然简单，其实⾮常有道理：对于⼩东西，能⽤循环⼲嘛要折腾？如果⽐较复杂，在系统撑的住的情况下，写递归有利于代码的维护（可读性好）。
另：⼀般尾递归（即最后⼀句话进⾏递归）和单向递归（函数中只有⼀个递归调⽤地⽅）都可以⽤循环来避免递归，更复杂的情况则要引⼊栈来进⾏压栈出栈来改造成⾮递归，这个栈不⼀定要严格引⼊栈数据结构，只需要有这样的思路，⽤数组什么的就可以。
⾄于教科书上喜欢n!的⽰例，我想只是便于递归思路的引进和建⽴。真正做代码不可能的。
循环⽅法⽐递归⽅法快, 因为循环避免了⼀系列函数调⽤和返回中所涉及到的参数传递和返回值的额外开销。
递归和循环之间的选择。⼀般情况下, 当循环⽅法⽐较容易到时, 你应该避免使⽤递归。这在问题可以按照⼀个递推关系式来描述时, 是时常遇到的, ⽐如阶乘问题就是这种情况。反过来, 当很难建⽴⼀个循环⽅法时, 递归就是很好的⽅法。实际上, 在某些情形下, 递归⽅法总是显⽽易见的, ⽽循环⽅法却相当难到。当某些问题的底层数据结构本⾝就是递归时, 则递归也就是最好的⽅法了。
递归其实是⽅便了程序员难为了机器。它只要得到数学公式就能很⽅便的写出程序。优点就是易理解，容易编程。但递归是⽤栈机制实现的（c++），每深⼊⼀层，都要占去⼀块栈数据区域，对嵌套层数深的⼀些算法，递归会⼒不从⼼，空间上会以内存崩溃⽽告终，⽽且递归也带来了⼤量的函数调⽤，这也有许多额外的时间开销。所以在深度⼤时，它的时空性就不好了。
循环其缺点就是不容易理解，编写复杂问题时困难。优点是效率⾼。运⾏时间只因循环次数增加⽽增加，没什么额外开销。空间上没有什么增加。
递归算法与迭代算法的设计思路区别在于：函数或算法是否具备收敛性，当且仅当⼀个算法存在预期的收敛效果时，采⽤递归算法才是可⾏的，否则，就不能使⽤递归算法。
当然，从理论上说，所有的递归函数都可以转换为迭代函数，反之亦然，然⽽代价通常都是⽐较⾼的。
但从算法结构来说，递归声明的结构并不总能够转换为迭代结构，原因在于结构的引申本⾝属于递归的概念，⽤迭代的⽅法在设计初期根本⽆法实现，这就像动多态的东西并不总是可以⽤静多态的⽅法实现⼀样。这也是为什么在结构设计时，通常采⽤递归的⽅式⽽不是采⽤迭代的⽅式的原因，⼀个极典型的例⼦类似于链表，使⽤递归定义及其简单，但对于内存定义(数组⽅式)其定义及调⽤处理说明就变得很晦涩，尤其是在遇到环链、图、⽹格等问题时，使⽤迭代⽅式从描述到实现上都变得很不现实。
把递归算法转化为⾮递归算法有如下三种基本⽅法：
(1). 通过分析，跳过分解过程，直接⽤循环结构的算法实现求解过程。
(2). ⾃⼰⽤栈模拟系统的运⾏时栈，通过分析只保存必须保存的信息，从⽽⽤⾮递归算法替代递归算法。
(3). 利⽤栈保存参数，由于栈的后进先出特性吻合递归算法的执⾏过程，因⽽可以⽤⾮递归算法替代递归算法。
●      递归函数的原理
⽤栈保存未完成的⼯作，在适当的时候从栈中取出并执⾏。系统保存了⼯作的数据和状态，数据就是函数的局部变量，
状态就是程序指针。
●      ⾮递归程序原理
1. 和递归函数的原理相同，只不过是把由系统负责保存⼯作信息变为程序⾃⼰保存，这样能减少保存
数据的冗余(主要是
节省了局部变量的空间)，提⾼存储效率。
2. 把程序要完成的⼯作分成两类：⼿头⼯作和保存在栈中的待完成的⼯作。⼿头⼯作指程序正在做的⼯作。由于某些⼯作
不能⼀步完成，必须暂缓完成，于是可把它保存在栈中，这就是待完成的⼯作。
3. ⼿头⼯作必须有其结束条件，不能永远做下去；保存的待完成⼯作必须含有完成该项⼯作的所有必要信息。
4. 程序必须有秩序地完成各项⼯作。如，可把⼿头⼯作恰当处理（直接处理或暂时保存）后，才能继续接⼿下⼀步的⼯作。
5. 待完成⼯作必须转换成⼿头⼯作才能处理。
●      栈的⼤⼩
所有递归问题，其递归过程可以展开成⼀棵树，叶⼦节点是可解的，按照问题的要求，处理所有叶⼦节点，就可解决
问题本⾝。可能需要保存(Data, Status)，Data是⼯作数据，Status是⼯作状态；（Data, Status）决定了整个⼯作。
栈的⼤⼩等于树的⾼度-1，-1是因为根节点不需保存。
●      举例
例1.    汉诺塔问题
递归函数：
void Hanoi(UINT x, UINT y, UINT n)
// x    Source
// y    Destination
// n    Number of plates
{
if (n == 0) return;
Hanoi(x, x^y, n-1);
Move(x, y);
Hanoi(x^y, y, n-1);
}
说明：x、y可取1、2、3三数之⼀，并且x≠y，x^y表⽰x、y按位异或，得到除x、y之外的第三个数。1^2=3, 1^3=2, 2^3=1 ⾮递归程序：
#define N 5
tyepdef struct _HANOIDATA
{
UINT x;
UINT y;
UINT n;
}HANOIDATA;
void Hanoi(HANOIDATA hanoiData)
{
HANOIDATA  stack[N];
int        top = -1;      //stack pointer
while (hanoiData.n || top != -1)    // 存在⼿头⼯作或待完成⼯作
{
while (hanoiData.n)    // 处理⼿头⼯作直到⽆现成的⼿头⼯作，
// 即下次的⼿头⼯作必须从栈中取得
{
hanoiData.n --;
stack[++top] = hanoiData;  // 保存待完成⼯作
hanoiData.y ^= hanoiData.x; // 新的⼿头⼯作
}
if (top != -1)  // 存在待完成⼯作
{
hanoiData = stack[top--];  // 从栈中取出
Move(hanoiData.x, hanoiData.y);  // 直接处理
hanoiData.x ^= hanoiData.y; // 未处理完的转换成⼿头⼯作
}
}
}
例2． 后根序遍历⼆叉树
递归函数：
void PostTraverse(BINARYTREE root)
{
if (root == NULL) return;
PostTraverse(root->LChild);
PostTraverse(root->RChild);
Visit(root);
}
⾮递归程序：
void PostTraverse(BINARYTREE p)
{
while ( p != NULL || !Stack.IsEmpty() )// 存在⼯作(⼿头或待完成)    {
while (p != NULL)    // 处理⼿头⼯作，直到⽆现成⼿头⼯作
{
Stack.Push(p, RCHILD_AND_ITSELF);
p = p->LChild;
}
if (!Stack.IsEmpty())  // 是否存在待完成⼯作
{
Stack.Pop(p, Tag);
if (Tag == RCHILD_AND_ITSELF)  // 情况⼀: RChild &Itself            {
Stack.Push(p,ONLY_ITSELF)  // 保存待完成⼯作
p = p->RChild; // 新的⼿头⼯作
}
else        //tag == ONLY_ITSELF,  情况⼆: Only Itself
{
visit(p);
p = NULL;    // 已⽆现成的⼿头⼯作
}
}
}
}
●      总结
⾮递归程序的设计应注意：
1.      保存暂缓执⾏的⼯作
2.      ⽆现成⼿头⼯作的条件
3.      ⽆待完成⼯作的条件
程序模式
编程递归函数void NonRecursiveFunction(DATATYPE Data)
{
while ( ExistHandyWork() || ExistSavedWork() )
{
while ( ExistHandyWork() )
{
Process(Work, Status)  //Probably push work onto stack
NewHandyWork();
}
if ( ExistSavedWork() )
{
Pop(Work, Status);
Process(Work, Status);  //Probably generate new handy work
}
}
}
递归算法向⾮递归算法转换
递归算法实际上是⼀种分⽽治之的⽅法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是⼀种⾃然且合乎逻辑的解决问题的⽅式，但是递归算法的执⾏效率通常⽐较差。因此，在求解某些问题时，常采⽤递归算法来分析问题，⽤⾮递归算法来求解问题；另外，有些程序设计语⾔不⽀持递归，这就需要把递归算法转换为⾮递归算法。
将递归算法转换为⾮递归算法有两种⽅法，⼀种是直接求值，不需要回溯；另⼀种是不能直接求值，需要回溯。前者使⽤⼀些变量保存中间结果，称为直接转换法；后者使⽤栈保存中间结果，称为间接转换法，下⾯分别讨论这两种⽅法。
1. 直接转换法
直接转换法通常⽤来消除尾递归和单向递归，将递归结构⽤循环结构来替代。
尾递归是指在递归算法中，递归调⽤语句只有⼀个，⽽且是处在算法的最后。例如求阶乘的递归算法：
long fact(int n)
{
if(n==0)
return 1;
else
return n*fact(n-1);
}
当递归调⽤返回时，是返回到上⼀层递归调⽤的下⼀条语句，⽽这个返回位置正好是算法的结束处，所以，不必利⽤栈来保存返回信息。对于尾递归形式的递归算法，可以利⽤循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的⾮递归算法：
long fact(int n)
{
  int s=0;
  for(int i=1; i<=n;i++)
      s=s*i;//⽤s保存中间结果
  return s;
}
单向递归是指递归算法中虽然有多处递归调⽤语句，但各递归调⽤语句的参数之间没有关系，并且这些递归调⽤语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。