用Groovy进行尾递归

用Groovy进行尾递归

本文介绍了用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注释:


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进行尾递归的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-01 06:50