请大家指教一下：分别使用递归和栈遍历树，性能会差多少？

Question

请大家指教一下：分别使用递归和栈遍历树，性能会差多少？

Answer 1

答：“数据量不是非常大时, 递归取得胜利,”我的观点是：恰恰相反。我不知道你是怎么测试的。
理由：
１）我在５楼已讲得很清楚，“精心设计与优化的栈算法会比递归的内部栈，性能可能会好一些。至少在进栈、出栈的数据量上，精心设计有会少很多。”这是栈算法是的优化，比编译器对递归代码层次上的优化要好的多。
２）事实说话：我们就用著名的阿克曼递归函数来说明，是因为：除了递归，该函数只能用栈算法来做。
代码见下：public class TestRc { /*
 * 阿克曼函数定义如下：   
               akm（m，n）=   n+1           if   m=0   
                            akm（m-1，1）   if   m！=0&&n=0   
                            akm   (m-1,akm(m,n-1))     if   m!=0&&n!=0  */
　　　　　//这是递归算法
public static  int akm(int m,int n)
{  
if(m==0) return n+1;
if(m!=0 && n==0) return akm(m-1,1);
return akm(m-1,akm(m,n-1));

}

//这是设计的栈式算法（还没有进行精心的算法代码呢，只是一般的写写而已）。
static int[] s=new int[10000];//这是栈
static int top=-1;//栈指针
public static int akm1(int m,int n)
{
while(true)
{
if(m==0)
{
if(top<0){return n+1;}
else{ m=s[top--] ;n=n+1;}//出栈
}
else if(n==0){
m=m-1;n=1;
}else{
s[++top]=m-1;//进栈
n=n-1;
}

}//while

}
//仅仅从栈算法的代码上，就已经明显感到，进栈与出栈的次数明显少于递归，而且一次进栈的数据也少

public static void main(String[] args) {
// TODO Auto-generated method stub
long l1=System.currentTimeMillis();
for(int i=1;i<=100;i++)　//才重复做了１００次
{
akm(3,6);　//这是递归
}
long l2=System.currentTimeMillis();
      System.out.println("递归时间："+(l2-l1));
     long l3=System.currentTimeMillis();
for(int i=1;i<=100;i++)　//才重复做了１００次
{
akm1(3,6); //这是栈算法
}
long l4=System.currentTimeMillis();
  System.out.println("栈算法时间："+(l4-l3));    
}}
运行结果：
递归时间：220
栈算法时间：120
结果说明：仅仅才运行了１００次，栈算法（而且还不是精心设计与优化过的栈算法）就已经比递归快了近一倍。３）用著名有递归函数来比较，事实数据还不够吗？

Answer 2

答：说明：akm(3,6)与akm1(3,6)计算结果都是509

Answer 3

说说我的看法。递归是进行的栈（数据结构）操作，并且是在栈（内存）上进行的，所以压栈出栈是很快的（指针偏移）；
而用迭代取代递归就会使用栈（数据结构）。要比较性能的话，就要看迭代时使用的栈是怎样实现的，如果单纯的用int[] stack这样来模拟LIFO行为，其实和递归没太大区别，以为基本类型也是直接在栈（内存）上进行；要是用new Stack(),比如类库中的Stack来实现，那么显然直接使用递归效率更高。…………………………………………………………………………………………………………
上面说的这些都是假设在一样的设计前提下。然而设计的优劣对效率的影响比前面说的系统层面上的效率要大的多，所以“云上飞翔”的阿克曼展示的效率问题其实不在于递归和使用栈（数据结构）的不同，而在于设计上。阿克曼函数如果直接用递归实现，那么它的算法复杂度是以2^n级别增长的。如果画一棵递归树就会发现，递归时，有很多分支具有完全一样的调用。而使用迭代来计算阿克曼函数，就可以避免这个庞大的递归树。
但是也可以用递归+备忘录(一种设计方法，第一次递归，再次调用直接读取)来达到和迭代一样的进出栈次数。…………………………………………………………………………………………………………
还有一点，编译器会对递归做出优化，比如尾部递归会被优化为使用迭代。这是编译器行为。
递归有个致命的缺点所以不建议使用，由于使用的是栈内存，如果压栈很深，一次一次的进栈最终会消耗完栈内存。…………………………………………………………………………………………………………
一家之言，有不对的地方多包涵。