讨论递归问题 迷惑中

Question

印象中 递归会比非递归速度慢（当然是指栈操作）
结果上网搜索一把 发现我的印象属于严重错误的情况
号称用栈只能省下栈空间 而不能提高速度
我不信  所以做了一个测试  
发现自信完全受了打击 
用栈居然比递归足足慢了10倍！
我用那个什么数列 就是 f(n)=f(n-1)+f(n-2) 来实现  得到以下的评价时间
fun 1 need time:43.66
fun 2 need time:472.78
请按任意键继续 . . .
#include <iostream>
#include <stdlib.h>
#include <stack>
using namespace std;int fun1(int n)
{
    if(n==1||n==2)
    {
        return 1;
    }
    else
    {
        return fun1(n-1)+fun1(n-2);
    }
}
int fun2(int n)
{
    stack <int> my;
    int temp;
    int all=0;
    my.push(n);
    while(!my.empty())
    {
        temp=my.top();
        my.pop();
        if(temp==1||temp==2)
        {
                ++all;
        }
        else
        {
                my.push(temp-2);
                my.push(temp-1);
        }
    }
    return all;
}
int main(int argc, char *argv[])
{
    char string[256];
    long start;
    long end;
    int i=0;
    int j=10;
    double all1=0;
    double all2=0;
    for(i=0;i<j;i++)
    {
        start=GetTickCount();
        fun1(30);
        end=GetTickCount();
        all1+=end-start;
        start=GetTickCount();
        fun2(30);
        end=GetTickCount();
        all2+=end-start;
    }
    cout<<"fun 1 need time:"<<all1/j<<endl;
    cout<<"fun 2 need time:"<<all2/j<<endl;
    system("PAUSE");    
    return 0;
}
不要提代码习惯的问题  下午用在公司想用java写  那个stack不好用 受了一肚子气 回来就不顾一切的写了这个  看看是不是什么地方用的不好导致数量级不同了

Answer 1

请问GetTickCount();这是个什么函数啊？怎么找不到，你自己写的？

Answer 2

GetTickCount是win api   用于获得开机到现在的毫秒数  
是个精确值  其他的函数不放心使用

Answer 3

因为担心自己写stack会在这个地方造成性能的瓶颈 ，所以才采用stl的stack

Answer 4

不管有否用递归其实两个算法都用了栈只不过递归的话用的是机器级的栈另一个方法用的是高级语言级的栈当然机器级的栈效率要高很多尤其你用的 stack<int> 是动态改变大小的所以 push pop 涉及很多空间分配和空间释放所以和递归相比效率判若云泥就不足为怪了

Answer 5

ross33123() ：
   我知道递归是调用物理栈，只是没想到物理栈的速度会快那么多
而且由于递归调用 ，所以有很多保存现场的工作要做，所以认为其效率应该大打折扣。
难道说唯一的解释是机器太快了吗？ 
另外以此看来，想用数据结构stack来替代递归调用 由于效率差那么多 好像不是很切合实际！
而且有个很严峻的问题是物理栈大小限制太大  ，我曾尝试过编写用递归的方式进行图像的填充算法，但是很快发现失败（栈不够用啊）虽然是很小的一块区域但是马上 程序非法操作了
所以不得已用了stack来替代 但是只是觉得慢 没从效率上考虑。
那么最好的替代方式是什么？ 
我现在就去写个专名的stack  看看性能是否能有所提高。

Answer 6

你使用了stl的stack，造成了大量的空间分配和释放，当然也就浪费了大量的时间。

Answer 7

回 kingofvc(什么都是幻觉) 1. "而且由于递归调用 ，所以有很多保存现场的工作要做"   所谓保存现场，无非是函数调用的现场，并不因为递归调用而需要保存额外的现场。你用 stl 的 stack， 每次push和pop都变成了函数调用，所以反而比递归调用涉及更多的函数调用（也就是有更多的现场需要保存）2. "有个很严峻的问题是物理栈大小限制太大"
  这是可以调的，在 project settings / link / output 里

Answer 8

关于f(n)=f(n-1)+f(n-2)函数，用递归是比较慢的
它的栈的用量和计算时间根据n成指数增长还是用循环的方法快！

Answer 9

现在不是要求速度快  仅仅是观察直接用调用 跟用数据结构stack比较效率

Answer 10

感谢各位 发现自己写的stack效率更差  
暂且这样吧