用Groovy进行尾递归 [英] Tail recursion with Groovy

问题描述

我编码了3个阶乘算法：

1. 首先，我预计Stack Overflow会失败。没问题。其次，我尝试 tail recusive call ，将以前的算法从递归转换为迭代。 不起作用，但我不明白为什么。


2. 第三，我使用 trampoline（）方法，并且可以按我的预期正常工作。

---

  def factorial 
 
 factorial = {BigInteger n  - > 
 if（n == 1）return 1 
n * factorial（n  -  1）
} 
析因（1000）//堆栈溢出
 
析因= {Integer n，BigInteger acc = 1  - > 
 if（n == 1）返回acc 
 factorial（n-1，n * acc）
} 
析因（1000）//堆栈溢出，为什么？ 
 
 factorial = {整数n，BigInteger acc = 1  - > 
 if（n == 1）return acc 
 factorial.trampoline（n-1，n * acc）
} .trampoline（）
 factorial（1000） 
  

解决方案

从版本2.3开始Groovy支持尾递归@方法的TailRecursive注释：
http://java.dzone.com/文章/ groovy-goodness-more-efficient

I coded 3 factorial algorithms:

1. First, I expect to fail by Stack Overflow. No problem.
2. Second, I try tail recusive call, convert previous algorithm from recursive to iterative. It doesn't work but I don't understand why.
3. Third, I use trampoline() method and works fine as I expect.

---

def factorial

factorial = { BigInteger n ->
    if (n == 1) return 1
    n * factorial(n - 1)
}
factorial(1000)  // Stack Overflow

factorial = { Integer n, BigInteger acc = 1 ->
    if (n == 1) return acc
    factorial(n - 1, n * acc)
}
factorial(1000)  // Stack Overflow, why???

factorial = { Integer n, BigInteger acc = 1 ->
     if (n == 1) return acc
     factorial.trampoline(n - 1, n * acc)
}.trampoline()
factorial(1000)  // It works

解决方案

Starting with version 2.3 Groovy supports tail recursion with the @TailRecursive annotation for methods: http://java.dzone.com/articles/groovy-goodness-more-efficient

这篇关于用Groovy进行尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！