How exactly does tail recursion work?

I almost understand how tail recursion works and the difference between it and a normal recursion. I only don't understand why it doesn't require stack to remember its return address.

// 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);
}

There is nothing to do after calling a function itself in a tail recursion function but it doesn't make sense for me.

19091 次浏览
小开

我的答案更多的是猜测，因为递归与内部实现有关。

在尾递归中，递归函数在同一个函数的末尾被调用。也许编译器可以通过以下方式进行优化:

  1. 让正在执行的函数结束(即收回已使用的堆栈)
  2. 将要用作函数参数的变量存储在临时存储器中
  3. 之后，再次使用临时存储的参数调用该函数

正如您所看到的，我们在同一个函数的下一次迭代之前结束了原来的函数，所以我们实际上并没有“使用”堆栈。

但是我相信如果在函数内部有析构函数需要调用，那么这种优化可能不适用。

小开
最佳答案

编译器可以简单地对此进行转换

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;
}
小开

编译器通常可以将尾递归转换为循环，特别是在使用累加器时。

// 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;
}
小开

您会问为什么“它不需要堆栈来记住它的返回地址”。

I would like to turn this around. It does use the stack to remember the return address. The trick is that the function in which the tail recursion occurs has its own return address on the stack, and when it jumps to the called function, it will treat this as it's own return address.

具体来说，没有尾部呼叫优化:

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的位置。

EDIT: The example above use the case where one function calls another function. The mechanism is identical when the function calls itself.

小开

下面是一个简单的例子，展示了递归函数是如何工作的:

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


}

尾递归是一个简单的递归函数，递归在函数的末尾完成，因此没有代码在上升阶段完成，这有助于大多数高级编程语言的编译器完成所谓的 尾部递归优化，也有一个更复杂的优化称为 尾递归模

小开

递归函数中必须包含两个元素:

  1. 递归调用
  2. 保存返回值计数的位置。

“常规”递归函数将(2)保存在堆栈帧中。

正则递归函数中的返回值由两种类型的值组成:

  • Other return values
  • 自有函数计算的结果

让我们看看你的例子:

int factorial (int n) {
if (n == 0) return 1;
else return n * factorial(n - 1);
}

例如，框架 f (5)“存储”它自己的计算结果(5)和 f (4)的值。如果我调用 factorial (5) ，就在堆栈调用开始崩溃之前，我有:

 [Stack_f(5): return 5 * [Stack_f(4): 4 * [Stack_f(3): 3 * ... [1[1]]

注意，除了我提到的值之外，每个堆栈还存储函数的整个作用域。所以，递归函数 f 的内存使用量是 O (x) ，其中 x 是我必须进行的递归调用的数量。因此，如果我需要1kb 的 RAM 来计算阶乘(1)或阶乘(2) ，我需要约100k 来计算阶乘(100) ，以此类推。

在它的参数中放入(2)的尾递归函数。

在尾部递归中，我使用参数将每个递归帧中的部分计算结果传递给下一个递归帧。让我们看看我们的阶乘例子，尾递归:

int factorial (int n) {
int helper(int num, int accumulated)
{
if num == 0 return accumulated
else return helper(num - 1, accumulated*num)
}
return helper(n, 1)
}

让我们看看阶乘(4)中的帧:

[Stack f(4, 5): Stack f(3, 20): [Stack f(2,60): [Stack f(1, 120): 120]]]]

See the differences? 在“常规”递归调用中，返回函数递归地构成最终值。在 Tail Recursion 中，他们只引用基本情况(最后一个被评估的). We call 蓄电池 the argument that keeps track of the older values.

递归模板

常规递归函数如下:

type regular(n)
base_case
computation
return (result of computation) combined with (regular(n towards base case))

要在 Tail 递归中转换它，我们需要:

  • 引入一个携带累加器的 helper 函数
  • run the helper function inside the main function, with the accumulator set to the base case.

看:

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)

看出区别了吗？

尾部呼叫优化

Since no state is being stored on the Non-Border-Cases of the Tail Call stacks, they aren't so important. Some languages/interpreters then substitute the old stack with the new one. So, with no stack frames constraining the number of calls, 跟踪呼叫的行为就像一个 for 循环 in these cases.

优化与否取决于编译器。

小开

编译器具有足够的智能来理解尾部递归。在这种情况下，当从递归调用返回时，没有挂起操作，递归调用是最后一个语句，属于尾部递归的范畴。 编译器基本上执行尾递归优化，删除堆栈实现。

void tail(int i) {
if(i<=0) return;
else {
system.out.print(i+"");
tail(i-1);
}
}

After performing optimization , the above code is converted into below one.

void tail(int i) {
blockToJump:{
if(i<=0) return;
else {
system.out.print(i+"");
i=i-1;
continue blockToJump;  //jump to the bolckToJump
}
}
}

编译器就是这样做尾递归优化的。

小开

递归函数是 自己召唤自己

它允许程序员使用 最小代码量编写高效的程序。

缺点是，他们可以 导致无限循环和其他意想不到的结果，如果 写得不好。

我会解释两个 简单递归函数和尾递归函数

为了写一个 简单的递归函数

  1. 首先要考虑的是你应该什么时候决定出柜 的循环，即 if 循环
  2. 第二个问题是，如果我们是自己的函数，进程该怎么做

例如:

public static int fact(int n){
if(n <=1)
return 1;
else
return n * fact(n-1);
}

From the above example

if(n <=1)
return 1;

Is the deciding factor when to exit the loop

else
return n * fact(n-1);

是要完成的实际处理

为了便于理解，让我把这个任务一一破解。

让我们看看如果我运行 fact(4)，内部会发生什么

  1. 取代 n = 4
public static int fact(4){
if(4 <=1)
return 1;
else
return 4 * fact(4-1);
}

If循环失败，因此它进入 else循环 so it returns 4 * fact(3)

  1. 在堆栈内存中，我们有 4 * fact(3)

    取代 n = 3

public static int fact(3){
if(3 <=1)
return 1;
else
return 3 * fact(3-1);
}

If循环失败，因此它进入 else循环

所以它返回 3 * fact(2)

Remember we called ```4 * fact(3)``

fact(3) = 3 * fact(2)的输出

到目前为止，堆栈有 4 * fact(3) = 4 * 3 * fact(2)

  1. 在堆栈内存中，我们有 4 * 3 * fact(2)

    取代 n = 2

public static int fact(2){
if(2 <=1)
return 1;
else
return 2 * fact(2-1);
}

If循环失败，因此它进入 else循环

所以它返回 2 * fact(1)

记得我们叫 4 * 3 * fact(2)

The output for fact(2) = 2 * fact(1)

So far the stack has 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

  1. 在堆栈内存中，我们有 4 * 3 * 2 * fact(1)

    取代 n = 1

public static int fact(1){
if(1 <=1)
return 1;
else
return 1 * fact(1-1);
}

If循环为真

所以它返回 1

Remember we called 4 * 3 * 2 * fact(1)

fact(1) = 1的输出

到目前为止，堆栈有 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

最后是 事实(4) = 4 * 3 * 2 * 1 = 24的结果

enter image description here

尾部递归是

public static int fact(x, running_total=1) {
if (x==1) {
return running_total;
} else {
return fact(x-1, running_total*x);
}
}
  1. 替换 n = 4 
public static int fact(4, running_total=1) {
if (x==1) {
return running_total;
} else {
return fact(4-1, running_total*4);
}
}

If循环失败，因此它进入 else循环 所以它返回 fact(3, 4)

  1. 在堆栈内存中，我们有 fact(3, 4)

    取代 n = 3

public static int fact(3, running_total=4) {
if (x==1) {
return running_total;
} else {
return fact(3-1, 4*3);
}
}

If循环失败，因此它进入 else循环

所以它返回 fact(2, 12)

  1. 在堆栈内存中，我们有 fact(2, 12)

    取代 n = 2

public static int fact(2, running_total=12) {
if (x==1) {
return running_total;
} else {
return fact(2-1, 12*2);
}
}

If loop fails so it goes to else loop

所以它返回 fact(1, 24)

  1. 在堆栈内存中，我们有 fact(1, 24)

    取代 n = 1

public static int fact(1, running_total=24) {
if (x==1) {
return running_total;
} else {
return fact(1-1, 24*1);
}
}

If loop is true

所以它返回 running_total

running_total = 24的输出

最后是 fact(4,1) = 24的结果

enter image description here


提交答案