scala - 试图巩固对 Scala 中尾递归的理解

Question

我正在复习 Scala 考试，并试图找出我错过的这个测验问题。我将尾递归理解为“最后一次调用本身”，但我对其中一些代码片段之间的区别感到困惑。为什么这被认为是尾递归，

def f(x: Int): Int = {
    if (x % 2 == 0) {1} 
    else {f(x + 1)}

但这，不是吗？

def f(x: Int): Int = {
    if (x % 2 == 0) {1} 
    else {1 + f(x + 1)}

向函数中加 1 到底有什么限制它不能尾递归的？如果这是一个愚蠢的问题，我很抱歉，我没有看到数字的影响并且想巩固我的理解。任何其他完全能够识别尾递归的指针也会很棒!

Answer 1

你的理解不太对。尾递归并不意味着“最后一次调用是它自己”，而是“调用它自己是最后一次”。也就是说，尾递归调用必须是函数执行的最后一个 Action 。它必须是函数在该代码路径上执行的操作列表的“尾部”。 (当然，必须有一个不包含递归调用的代码路径)。

考虑表达式中值的计算方式而不是它们在代码中出现的顺序也很重要。这个表达式

1 + f(x + 1)

按以下顺序执行:

tmp1 = x + 1
tmp2 = f(tmp1)
res = 1 + tmp2

或者，

add(1, f(add(x, 1))

这样写你可以看到调用f之后是另一个 Action ，最后的+/add。由于递归调用不是最后一个 Action ，所以不是尾递归。