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!表示非负整数x)定义为gamma(x + 1)

一个更有趣的例子是实现Fibonnaci系列的代码,当用简单的递归实现时,它非常浪费.通过memoization可以使递归方法变得高效,但如果性能受到威胁,则总是首选简单的迭代.

另一种以递归方式自然表达的常见算法是Quicksort.这可以像所有算法一样在没有递归的情况下实现,但这样做非常复杂.使用非递归Quicksort没什么好处,因此使用朴素递归实现很常见.

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

• 如果性能没有受到影响,
• 如果更自然(因此更容易验证和维护)以递归方式实现.

Answer 2

我认为在R中表达数学计算的最自然的方式是通过数学/统计表示法.语言的全部意义在于以自然的方式表达统计计算变得容易.

您拥有factorial使用gamma此视图很好地实现的示例.我不知道如何gamma实现,但我们不需要知道为了使用R.作为用户,最重要的是通常得到正确的答案.如果代码被证明非常慢,那就是优化时.第一个开始的地方将是数学和算法的选择,而不是实现细节.

David Heffernan是正确的,递归通常比迭代慢,但他似乎没有考虑的是它很少重要.使用他自己的例子,Fibonacci数字,真正重要的是避免重新计算数字,这可以通过记忆来完成.这使得计算以线性时间而不是指数时间运行 - 这是一个巨大的进步.一旦你完成了这个,你仍然可以通过使用循环实现算法得到一个小的改进,但它可能无关紧要.此外,还有一个封闭的形式.

阶乘函数和斐波纳契数也都很快增长.这意味着每个算术运算(加法,乘法等)将开始花费很长时间,而递归不会变得更加昂贵或者至少不会那么快.再次,数学考虑因素胜过实施细节.

TL; DR

我的建议是:

1. 以最简单的方式编写算法.
2. 确保它是正确的.
3. 如果且仅当该算法是对现实的输入速度太慢:
   1. 找出算法的哪个部分花费时间/时间复杂度.
   2. 修复该部分,仅修复该部分.
   3. 如有必要,请重复此过程.