r - R 中使用递归函数吗？

Question

演示递归的规范函数是 Factorial() 函数。我自己尝试了一个简单的实现并想出了这个:

factorial <- function(x){

if(x==1)
    return( 1)
else
    return(x*factorial(x-1))

}

根据我对该主题的调查，似乎存在一些关于使用递归还是简单迭代更好的争论。我想看看R是如何实现它的，并在gregmisc包中找到了一个factorial()函数。我想我会找到类似我的实现的东西，或者替代常规迭代。我发现了什么:

> factorial
function (x) 
gamma(x + 1)
<environment: namespace:base>

所以我的问题“R 更喜欢递归还是迭代”的答案是“都不”。至少在这个实现中。 R 中避免使用递归函数有充分的理由吗？

更新:

gregmisc 版本:

>ptm <- proc.time()
> factorial(144)
[1] 5.550294e+249
> proc.time() - ptm
   user  system elapsed 
  0.001   0.000   0.001 

我的版本:

> factorial(144)
[1] 5.550294e+249
> proc.time() - ptm
  user  system elapsed 
  0.002   0.001   0.006 

Answer 1

对于整数阶乘的计算，递归实现速度较慢且较复杂。生产代码中总是使用迭代。

您引用的factorial函数位于基础包中。它对实数值而不是整数进行操作，因此是这样的实现。其文档指出:

factorial(x) (x! for non-negative integer x) is defined to be gamma(x+1)

一个更有趣的例子是实现斐波那契数列的代码，当使用简单的递归实现时，这是非常浪费的。递归方法可以通过内存来提高效率，但如果性能受到威胁，简单的迭代始终是首选。

另一种以递归方式自然表达的常见算法是快速排序。与所有算法一样，这可以在没有递归的情况下实现，但这样做相当复杂。使用非递归快速排序几乎没有什么好处，因此通常使用简单的递归实现。

递归是一个很好的实现选择:

• 如果性能不受影响，并且
• 递归实现是否更自然(因此更容易验证和维护)。