为什么阶乘递归函数的效率低于正常的阶乘函数？

Question

我有两个函数来计算数n的阶乘.我不明白为什么'正常'函数需要更少的时间来计算数n的阶乘.这是正常的功能:

double factorial(int n) {
    double s = 1;
    while (n > 1) {
        s *= n;
        --n;        
    }

    return s;
}

这是递归函数:

double factorial(int n) {
    if (n < 2) return 1;
    return n * factorial(n-1);
}

这应该不那么耗时,因为它不会创建一个新变量,并且它可以减少操作.虽然普通函数确实使用了更多的内存,但速度更快.

我应该使用哪一个？为什么？

PS:我正在使用双,因为我需要它来计算e ^ x的泰勒级数.

Answer 1

你写的是递归函数"应该不那么耗时,因为它不会创建一个新的变量,并且它会减少操作".第一个断言是毫无意义的.局部变量的内存通常在进入函数时由单个减法操作分配,这需要不显着的时间(这是人类已知的最快分配).第二个断言对于C++实现来说是完全错误的.既然你已经用编译器测量了递归函数的速度较慢,那么它会做得更多,而不是更少.

现在,为什么.

好吧,每次调用都必须复制一个返回地址和堆栈上的实际参数.这需要时间.此外,为了支持调试和异常,每个函数调用通常会做一些额外的工作来建立一个很好的堆栈帧,实质上存储有关堆栈在调用之前的信息.

递归变种也不过不是必须要慢一些.但几乎矛盾的是,实际上可以像迭代一样快的变体看起来会做得更多......想法是编写它以便编译器可以将其转换为迭代版本,也就是说,编译器可以用简单的循环替换递归调用(这需要时间).

唯一的问题是,据我所知,如果有任何C++编译器进行这种优化,则很少.:-(

但是,为了完整性,我们的想法是确保只有一个递归调用,并且它是最后发生的事情.这叫做尾递归.您当前的递归代码,

double factorial( int n )
{
    if( n < 2 ) { return 1; }
    return n*factorial( n-1 );
}

不是尾递归的,因为在递归调用之后会有乘法n.

为了使它具有尾递归性,你可以在这里作为参数传递完成应该在最后完成的事情所需的信息*n.所需要的信息是它的价值n,以及它应该完成的事实.这意味着引入一个带有适当形式参数的辅助函数:

double factorialScaledBy( double m, int n )
{
    if( n < 2 ) { return m*1; }

    // Same as "n*factorialScaledBy( m, n-1 )", but tail-recursive:
    return factorialScaledBy( n*m, n-1 );  
}

double factorial( int n )
{
    return factorialScaledBy( 1, n );
}

现在一个足够聪明的编译器可以注意到在递归调用之后在函数执行中不再发生任何事情,因此不使用局部变量,因此它们可以仅用于递归调用,因此可以实现为模拟参数传递加上跳回函数的顶部,即循环.

干杯&hth.,