为什么这个阶乘递归函数效率低下？

在"像程序员一样思考"一书中,下面的递归函数被称为"非常低效",我无法弄清楚为什么(这本书没有解释).似乎没有任何不必要的计算.是因为调用这么多函数(多次使用相同的函数)的开销,从而为每次调用函数设置环境？

int factorial(int n) {
  if (n == 1) return 1;
  else return n * factorial(n-1);
}

Jashaszun.. 6

它在两个方面效率低下,你打其中一个:

它是递归的,而不是迭代的.如果未启用尾调用优化,则效率非常低.(要了解有关尾调用优化的更多信息,请查看此处.)它可以像这样完成:

int factorial(int n)
{
    int result = 1;
    while (n > 0)
    {
        result *= n;
        n--;
    }
    return result;
}

或者,一个for循环.

但是,正如上面的评论中所指出的那样,如果一个人int甚至不能保持结果,那么它的效率并不重要.它应该是longs,long longs,甚至是big-int.

第二个低效率只是没有一个有效的算法.这个因子算法列表显示了一些通过减少数值运算的数量来计算因子的更有效方法.