我正在尝试查找注释@tailrec
在Scala中的工作方式。以下是我处理的示例。
@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
的开销将是多少?
使用尾递归(不使用显式堆栈)时,您不能“获得行为的堆栈类型”。 @tailrec
批注意味着您不需要调用堆栈,并且可以对其进行优化。您必须决定是要尾递归还是要解决递归子问题。一些问题(例如二进制搜索)非常适合尾部递归,而其他一些问题(例如您的collatz代码)则需要更多的思考,还有一些其他问题(例如DFS)过于依赖调用堆栈而无法从尾部递归中受益。 。