看看递归和非递归的效率，小弟我晕

看看递归和非递归的效率，我晕
地球人都知道递归算法有调用函数的开销，导致性能不如非递归算法。
我用二叉树先序遍历，将递归和非递归作比较，却得出相反的结果，递归的效率高于非递归的，忘大侠们看看……

C/C++ code

typedef  struct  node {  int  data;  struct  node  * lchild, * rchild; } * proot; void  pre_r(proot t) {     if  (t != 0 )     {               value=t->data;        pre_r(t -> lchild);         pre_r(t -> rchild);     }  }void  preorder(proot t) {      proot p;     proot S[Max+1];     int top;     if (t==NULL) return;     top=-1;     S[++top]=t;     while(top>=0)     {         p=S[top--];         while(p!=NULL)         {             value=p->data;             S[++top]=p->rchild;             p=p->lchild;             }         } }

不知什么原因非递归的多花20％左右的时间。

[解决办法]
看看汇编？也许有帮助。
[解决办法]
有些编译器会做优化,能把递归的代码转化为非递归的代码.
[解决办法]
我们所认为的“递归算法有调用函数的开销，导致性能不如非递归算法”通常意义上是指“递归算法与相应的迭代算法”的比较，也就是尾递归转迭代的情况。这里的区别在于，递归算法需要一个线性的空间开销，并且需要不断的
压栈与出栈，而在迭代中空间开销是不变的，只是一个循环就完成了所有的操作。

你的程序实际上是用代码的形式模拟了堆栈的操作，并没有改变算法执行过程的实质，而且由于使用的是ADT，从而比系统级的堆栈操作还要慢，所以程序的效率必然会更低。
[解决办法]
非递归对于复杂处理的性能贡献是有限的，递归无非多几次函数调用和入栈出栈，那才几个指令，如果你每伦递归计算少一个表达式，都可以省出这个时间来

查看更多 下一篇