尾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优化。