recursion - 在Groovy中将递归闭包更改为TrampolineClosure

我需要从仅包含字符0，1和V(通配符)的字符串构造所有可能的二进制表示形式。尽管通配符的数量少于20个，但字符串可以是任何长度(超过1000个字符)。

例如，对于输入V1V，输出将为[010, 011, 110, 111]
我当前的实现工作正常，但使用少量的通配符会使堆栈溢出。代码为running here，如下所示。

def permutts
permutts =
{
  if (!it.contains('V'))
    return [it]

  def target = it
  def res = []

  ['0', '1'].each
  {
    def s = target.replaceFirst(~/V/, it)
    if (s.contains('V'))
    {
      res += permutts(s)
    }
    else
    {
      res << s
    }
  }
  res
}
println permutts('V1V')

我尝试遵循一些使用trampoline()的示例，但是我什至不确定这是否是正确的方法。 The API says，“……该功能应该执行一步的计算……”，但每一步都执行两个操作:用0和1代替V。

这是我的尝试之一，可以是run here。

def permutts

permutts =
{ it, res = [] ->
  println "entering with " + it + ", res=" + res
  if (it.contains('V'))
  {
    def s = it.replaceFirst(~/V/, '1')
    permutts.trampoline(s, res)

    s = it.replaceFirst(~/V/, '0')
    permutts.trampoline(s, res)
  }
  else
  {
    res << it
  }
}.trampoline()
println permutts('VV')

输出为:

entering with VV, res=[]
entering with 0V, res=[]
entering with 00, res=[]
[00]

至少它在做某事，但是我不明白为什么它不能持续下去。谁能解释我做错了什么，或提出其他解决此问题的方法？

最佳答案

Groovy的trampoline()提供tail call optimization，因此应将其用于在最后执行的指令(尾部)中调用自身的闭包/方法。

因此，更好的解决方案将是经典的“头/尾”处理(添加println来跟踪呼叫):

def permutts
permutts = { s, res ->
    if (s.length() == 0) {
        println "s = $s, res = $res"
        res
    } else {
        println "s = $s, res = $res"
        if (s[0] == 'V') { // s[0] ~ list.head()
            res = res.collect({ it = it + '0' }) + res.collect({ it = it + '1' })
        } else {
            res = res.collect({ it = it + s[0] })
        }

        permutts.trampoline(s.substring(1), res) // s.substring(1) ~  list.tail()
    }
}.trampoline()

例子:

permutts('VV', [''])
  s = VV, res = []
  s = V, res = [0, 1]
  s = , res = [00, 10, 01, 11]
  Result: [00, 10, 01, 11]

permutts('0V0', [''])
  s = 0V0, res = []
  s = V0, res = [0]
  s = 0, res = [00, 01]
  s = , res = [000, 010]
  Result: [000, 010]

关于您的代码，来自TrampolineClosure javadoc:

TrampolineClosure包装了需要在
功能性蹦床。致电后，TrampolineClosure将呼叫
原始关闭等待其结果。如果通话结果为
TrampolineClosure的另一个实例，可能是由于
调用TrampolineClosure.trampoline()方法，
TrampolineClosure将再次被调用。重复调用
返回的TrampolineClosure实例将持续到其他值
会返回TrampolineClosure。该价值将成为最终价值
蹦床的结果。

即，在尾部调用优化中进行的替换。在您的代码中，整个TrampolineClosure链只要其中之一不返回TrampolineClosure就会返回。

从groovy 2.3开始，您可以使用@TailRecursive AST转换进行尾部调用优化:

import groovy.transform.TailRecursive

@TailRecursive
List permutts(String s, List res = ['']) {
    if (s.length() == 0) {
        res
    } else {
        res = (s[0] == 'V') ? res.collect({ it = it + '0' }) + res.collect({ it = it + '1' }) : res.collect({ it = it + s[0] })
        permutts(s.substring(1), res)
    }
}

编辑:

只需完成我的回答，就可以用functional fold一行完成上述操作，在Groovy中，它是inject(使用集合的开头作为初始值，并在结尾处进行迭代):

assert ['000', '010'] == ['0', 'V', '0'].inject([''], { res, value -> (value == 'V') ?  res.collect({ it = it + '0' }) + res.collect({ it = it + '1' }) : res.collect({ it = it + value }) })
assert ['00', '10', '01', '11'] == ['V', 'V'].inject([''], { res, value -> (value == 'V') ?  res.collect({ it = it + '0' }) + res.collect({ it = it + '1' }) : res.collect({ it = it + value }) })