试图巩固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

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

考虑如何评估表达式中的值而不是它们在代码中出现的顺序也很重要。这个表达

1 + f(x + 1)

按此顺序执行：

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

或者，

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

像这样写出你可以看到对f的调用之后是另一个动作，即最终的+ / add。由于递归调用不是最后一个操作，因此它不是尾递归。

Answer 2

在第二个片段中，最后一个调用不是“本身”，而是+。你必须首先从f(x+1)获得结果，然后在返回之前加1。所以当前帧必须保持在堆栈上以进行f(x+1)调用。

相反，在第一个片段中，在调用f(x+1)之后没有什么可做的，因为它的结果变成了返回值。因此，编译器可以在进行调用之前从堆栈中删除当前帧，以便f(x+1)调用的结果将直接返回给f(x)的调用者。

Answer 3

在函数调用表示法中明确地写下所有内容通常会有所帮助：

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)))

你现在可以发现为什么在第二个例子中最后一次调用不是为了f？