我有两个函数来计算数字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的泰勒级数。
您写递归函数应该更省时，因为它不创建新变量，而且操作更少。第一个断言毫无意义。局部变量的内存通常在进入函数时通过一个减法操作分配，这花费的时间很少(这是已知的最快的分配)。对于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。，
最好的办法是根本不显式地计算阶乘。如果您正在计算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;
}
这样，你就不必显式地计算阶乘，因为阶乘增长太快，对这个问题没有用处。
我认为这是因为函数调用在时间上比while循环更昂贵。我会使用第一个(没有递归)，如果N非常大，你会填满你的堆栈，可能会得到一个"堆栈溢出":)
这当然与数据结构有关。数据结构是很有趣的东西。其中一些在较小的数据量下表现很好，而另一些在较大的数据量下表现更好。
在递归代码中，有一个调用堆栈，当前递归的全部内容被推入堆栈，并在返回的过程中被提取。这是每次递归调用时函数调用的额外开销。这就是为什么，性能很慢。
查看更多详细信息:http://publib.boulder.ibm.com/infocenter/iadthelp/v6r0/topic/com.ibm.etools.iseries.pgmgd.doc/c0925076137.htm
函数调用在时间和空间上花费更多，因为:
- 参数需要被压入堆栈并返回值弹出。
- 每个调用消耗它自己的堆栈"帧"。
- 这不仅可以防止你有非常深的递归(堆栈大小是有限的，通常是几个MB)，
- 它也会损害你的缓存局部性(因为你每次调用都要访问RAM的不同部分)，最终也会花费时间。
顺便说一句，当你说函数调用"做更少的操作"，这实际上是不真实的。函数调用在源代码中可能看起来更短，但是在外部看起来和在内部实际做的事情是不同的。
同样，虽然在这种情况下不相关，但"更少的操作"并不总是等于更好的性能。有时候，"更多的操作"但是具有更好的局部性可以更好地利用所有现代cpu实现的缓存和预取来隐藏RAM延迟。