尾recursion如何工作？
我几乎了解尾recursion如何工作，以及它与正常recursion之间的差异。 我只是不明白为什么它不需要堆栈来记住它的返回地址。
// tail recursion int fac_times (int n, int acc) { if (n == 0) return acc; else return fac_times(n - 1, acc * n); } int factorial (int n) { return fac_times (n, 1); } // normal recursion int factorial (int n) { if (n == 0) return 1; else return n * factorial(n - 1); } 在尾recursion函数中调用函数本身之后没有任何事情要做，但对我来说没有意义。
编译器只是能够转换这一点
int fac_times (int n, int acc) { if (n == 0) return acc; else return fac_times(n - 1, acc * n); }
成这样的东西：
int fac_times (int n, int acc) { label: if (n == 0) return acc; acc *= n--; goto label; }
你问为什么“它不需要堆栈来记住它的返回地址”。
我想转过来。 它确实使用堆栈来记住返回地址。 诀窍是发生尾recursion的函数在栈上有自己的返回地址，当它跳转到被调用的函数时，它将把它作为它自己的返回地址。
具体而言，没有尾部呼叫优化：
f: ... CALL g RET g: ... RET
在这种情况下，当调用g时，堆栈将如下所示：
SP -> Return address of "g" Return address of "f"
另一方面，尾部呼叫优化：
f: ... JUMP g g: ... RET
在这种情况下，当调用g时，堆栈将如下所示：
SP -> Return address of "f"
显然，当g返回时，它将返回到f从中被调用的位置。
编辑 ：上面的例子使用一个函数调用另一个函数的情况。 当函数自己调用时机制是相同的。
尾部recursion通常可以被编译器转换成循环，特别是当使用累加器时。
// tail recursion int fac_times (int n, int acc = 1) { if (n == 0) return acc; else return fac_times(n - 1, acc * n); }
会编译成类似的东西
// accumulator int fac_times (int n) { int acc = 1; while (n > 0) { acc *= n; n -= 1; } return acc; }
在recursion函数中必须存在两个元素：
- recursion调用
- 一个地方保持返回值的计数。
“常规”recursion函数将（2）保留在堆栈帧中。
常规recursion函数中的返回值由两种types的值组成：
- 其他返回值
- 拥有函数计算的结果
让我们看看你的例子：
int factorial (int n) { if (n == 0) return 1; else return n * factorial(n - 1); }
例如，帧f（5）“存储”自己的计算结果（5）和f（4）的值。 如果我调用阶乘（5），就在堆栈调用开始崩溃之前，我有：
[Stack_f(5): return 5 * [Stack_f(4): 4 * [Stack_f(3): 3 * ... [1[1]]
注意，除了我提到的值之外，每个栈都存储函数的整个范围。 因此，recursion函数f的内存使用是O（x），其中x是我必须做的recursion调用的数量。 所以，如果我需要1kb的RAM来计算阶乘（1）或阶乘（2），我需要〜100k来计算阶乘（100），依此类推。
一个尾recursion函数把（2）放在它的参数中。
在尾recursion中，我使用参数将每个recursion帧中的部分计算结果传递给下一个。 让我们来看看我们的因子例子，尾recursion：
int factorial（int n）{int helper（int num，int accumulate）{if num == 0 return accumulated else else return helper（num-1，cumulative * num）} return helper（n，1）
}
我们来看看阶乘（4）中的框架：
[Stack f(4, 5): Stack f(3, 20): [Stack f(2,60): [Stack f(1, 120): 120]]]]
看到差异？ 在“常规”recursion调用中，recursion函数recursion地组成最终值。 在尾recursion中，他们只引用基本情况（最后一个评估） 。 我们称累加器为追踪旧值的参数。
recursion模板
常规的recursion函数如下所示：
type regular(n) base_case computation return (result of computation) combined with (regular(n towards base case))
为了在尾recursion中转换它，我们：
- 引入携带累加器的辅助function
- 在主函数中运行辅助函数，将累加器设置为基本情况。
看：
type tail(n): type helper(n, accumulator): if n == base case return accumulator computation accumulator = computation combined with accumulator return helper(n towards base case, accumulator) helper(n, base case)
看到不同？
尾巴呼叫优化
由于没有状态被存储在尾部调用堆栈的非边界情况下，所以它们并不那么重要。 有些语言/口译员会用新的替代旧的堆栈。 因此，在没有任何堆栈帧限制调用次数的情况下， 尾部调用在这些情况下的行为就像一个for循环 。
这是由你的编译器来优化它，否则。
下面是一个简单的例子，展示了recursion函数的工作原理：
long f (long n) { if (n == 0) // have we reached the bottom of the ocean ? return 0; // code executed in the descendence return f(n-1) + 1; // recurrence // code executed in the ascendence }
尾recursion是一个简单的recursion函数，在函数的末尾执行recursion函数，因此没有代码是以百分比forms完成的，这有助于大多数高级编程语言的编译器做所谓的尾recursion优化 ，也有一个更复杂的优化被称为尾recursion模
我的回答更多的是猜测，因为recursion是与内部实现相关的东西。
在尾recursion中，recursion函数在相同函数的末尾被调用。 可能编译器可以通过以下方式进行优化：
- 让正在进行的function（即使用堆栈被召回）
- 将要用作参数的variables存储在临时存储器中的函数中
- 之后，再次使用临时存储的参数调用该函数
正如你所看到的，在同一个函数的下一次迭代之前，我们正在清理原来的函数，所以我们实际上并没有“使用”堆栈。
但是我相信如果在函数内部调用析构函数，那么这个优化可能不适用。
编译器是足够智能的，以了解尾recursion。在情况下，从recursion调用返回时，没有挂起操作，recursion调用是最后一条语句，属于尾recursion类。 编译器基本上执行尾recursion优化，删除堆栈实现。考虑下面的代码。
void tail(int i) { if(i<=0) return; else { system.out.print(i+""); tail(i-1); } }
执行优化之后，上面的代码被转换成下面的代码。
void tail(int i) { blockToJump:{ if(i<=0) return; else { system.out.print(i+""); i=i-1; continue blockToJump; //jump to the bolckToJump } } }
这是编译器如何做尾recursion优化。
