7

我有两个函数可以计算数字 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：我需要使用 double 来计算 e^x 的泰勒级数。

4

5 回答 5

6

您写道，递归函数“应该不那么耗时，因为它不会创建新变量，并且它执行的操作更少”。第一个断言毫无意义。局部变量的内存通常在进入函数时由单个减法运算分配，这花费的时间微不足道（这是人类已知的最快分配）。对于您的 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.，

于 2011-10-09T12:28:00.967 回答
4

我会说这是因为函数调用在时间上比 while 循环更昂贵。我会使用第一个（无递归），就好像N它非常大，你会填满你的堆栈并且可能会得到一个“堆栈溢出”:)

于 2011-10-09T11:51:30.047 回答
4

你最好的选择是根本不计算阶乘。如果您正在计算 Taylor (Maclaurin) 级数exp(x)：

   exp(x) = 1 + x/1! + x^2/2! + x^3/3! + x^4/4! + ...

您最好的选择是执行以下操作：

   double y = 1.0;
   int i = 1;
   double curTerm = 1.0;
   double eps = 1e-10;  // whatever's desired
   while( fabs(curTerm) > eps)
   {
        curTerm *= x / (double)i;
        y += curTerm;
        ++i;
   }

这样，您就不必显式计算增长太快而无法解决此问题的阶乘。

于 2011-10-09T12:20:56.440 回答
1

这当然与数据结构有关。数据结构是有趣的东西。其中一些对于较小的数据大小表现出色，而另一些对于较大的数据大小表现更好。

在递归代码中，有一个调用堆栈，当前递归的全部内容被推入堆栈并在返回的路上被提取。这是每次递归调用的函数调用的额外开销。这就是为什么，性能很慢。

有关更多详细信息，请参见：http: //publib.boulder.ibm.com/infocenter/iadthelp/v6r0/topic/com.ibm.etools.iseries.pgmgd.doc/c0925076137.htm

于 2011-10-09T11:52:59.377 回答
0

函数调用在时间和空间上的成本更高，因为：

  • 需要将参数压入堆栈并弹出返回值。这需要时间。
  • 每个调用都会消耗它自己的堆栈“帧”。
    • 这不仅会阻止您进行非常深的递归（堆栈大小有限，通常为几 MB），
    • 它还会损害您的缓存位置（因为每次调用都会触及 RAM 的不同部分）并最终也会花费时间。

顺便说一句，当您说函数调用“执行较少的操作”时，这实际上是不正确的。函数调用在源代码中可能看起来更短，但是在外部看起来和内部实际执行的情况之间存在差异。

此外，虽然在这种情况下不相关，但“更少的操作”并不总是等于更好的性能。有时，“更多操作”但具有更好的局部性可以更好地利用所有现代 CPU 实现的缓存和预取来隐藏 RAM 延迟。

于 2011-10-09T12:18:27.903 回答