尾调用优化是否适用于此功能？

Question

如果 bar 在 i 是偶数时调用 bar(i/2)，否则调用 bar(3*i + 1)，则递归函数 bar 将进行尾递归。

const int bar(const int i) 
{
  if (i < 2) return i;
  return i % 2 ? bar(i/2) : bar(3*i + 1);
}

但是，如果 bar 调用 bar 或 foo，这两者具有与 bar 完全不同的局部变量集，该怎么办？

const int bar(const int i) 
{
  if (i < 2) return i;
  return i % 2 ? bar(i/2) : foo(3*i + 1);
  // where foo is very complicated recursive call that has 
  // 11 different user-defined/primitive type of
  // local variables that can't be optimized out
}

我的理解是尾递归优化将使用调用者的堆栈。调用者在调用被调用者之前已经完成了它的局部变量。因此，被调用者可以重用它。当调用者和被调用者是相同的函数时（例如 foo 调用 foo，bar 调用 bar），我的理解听起来不错。但是，如果堆栈大小和布局完全不同，并且被调用者可能是具有不同堆栈布局的多个不同函数之一，将会发生什么？

首先，会不会是尾递归？（现在，我知道 tail "call" 优化可能适用于但不是这不是 tail "recursion."）其次，gcc、clang 等主要编译器会优化这种尾部调用吗？（答案似乎是。）

如果被调用者（第二个代码示例中的 foo）复杂得多怎么办？如果被调用者和调用者互相调用（相互递归），我的第二个代码示例中的调用是否会被尾调用优化？如果被调用者（例如 foo）是一个复杂的递归调用，绝对不是尾递归并且编译器很难将其减少到循环左右，它是否仍然是尾调用优化的？

Answer 1

词条"tail-recursive"是调用站点的本地属性。它完全不受同一方法中其他调用的影响。

粗略地说，如果在其 return 和封闭方法的 return 之间没有可执行代码需要运行，则调用是 tail-recursive。

因此，在您的示例中对 bar() 的所有调用都是 tail-recursive。

但请注意，如果您说

return i % 2 ? bar(i/2) : 1 + bar(3*i + 1);

那么第一次调用是 tail-recursive，但第二次调用不是，因为加法 1 + 必须在它之后执行 returns。

Answer 2

Is tail recursion optimization applicable to this function?

是的，尾递归优化适用于您的示例。请查看第二个示例的汇编程序 https://godbolt.org/g/cSpUZw。应用的渐进式优化越多。递归替换为循环。

bar(int):
  cmp edi, 1
  jg .L12
  jmp .L6
.L15:
  sar edi
  cmp edi, 1
  je .L14
.L12:
  test dil, 1
  jne .L15
  lea edi, [rdi+1+rdi*2]
  jmp foo(int)
.L14:
  mov eax, 1
  ret
.L6:
  mov eax, edi
  ret

尾调用优化是否适用于此功能？

Is tail call optimization applicable to this function?

c++

c

recursion

tail-recursion