使用Scala中的尾调用递归获得子问题的结果

Question

我正在尝试使用@tailrec计算每个子问题的结果类似于普通递归解决方案如何为每个子问题产生解决方案。以下是我处理的示例。

@tailrec
  def collatz(
      n: BigInt,
      acc: BigInt,
      fn: (BigInt, BigInt) => Unit
  ): BigInt = {
    fn(n, acc)
    if (n == 1) {
      acc
    } else if (n % 2 == 0) {
      collatz(n / 2, acc + 1, fn)
    } else {
      collatz(3 * n + 1, acc + 1, fn)
    }
  }

这里，我正在使用1计算数字达到Collatz Conjecture时的计数。仅作为示例，让我们假设其为数字32

val n = BigInt("32")
    val c = collatz(n, 0, (num, acc) => {
      println("Num -> " + num + " " + " " + "Acc -> " + acc)
    })

我得到以下输出。

Num -> 32  Acc -> 0
Num -> 16  Acc -> 1
Num -> 8  Acc -> 2
Num -> 4  Acc -> 3
Num -> 2  Acc -> 4
Num -> 1  Acc -> 5

普通递归解将返回每个数字的精确计数。例如，实例编号2在1步骤中达到1。因此，每个子问题都有精确的解决方案，但在tailrec方法中，只能正确计算最终结果。变量acc的行为与预期的完全一样。

如何更改经过尾调用优化的代码，同时我可以为每个子问题获得准确的价值。简而言之，我如何获得Stack变量的acc行为类型。

另外，如果不使用fn语句，则对于n的较大值，lambda函数println的开销将是多少？

我添加了一个递归解决方案，可以为子问题提供正确的解决方案。

def collatz2(
      n: BigInt,
      fn: (BigInt, BigInt) => Unit
  ): BigInt = {

    val c: BigInt = if (n == 1) {
      0
    } else if (n % 2 == 0) {
      collatz2(n / 2, fn) + 1
    } else {
      collatz2(3 * n + 1, fn) + 1
    }
    fn(n, c)
    c
  }

它产生以下输出。

Num -> 1  Acc -> 0
Num -> 2  Acc -> 1
Num -> 4  Acc -> 2
Num -> 8  Acc -> 3
Num -> 16  Acc -> 4
Num -> 32  Acc -> 5

Answer 1

使用尾递归（不使用显式堆栈）时，您不能“获得行为的堆栈类型”。 @tailrec注释表示您没有使用调用堆栈，可以对其进行优化。您必须决定是要尾递归还是要解决递归子问题。一些问题（例如二进制搜索）非常适合尾部递归，而其他一些问题（例如您的collat​​z代码）则需要更多的思考，还有一些其他问题（例如DFS）过于依赖调用堆栈而无法从尾部递归中受益。 。