c - 尾递归究竟是如何工作的？

Question

我几乎了解尾递归的工作原理以及它与普通递归之间的区别。我只是不明白为什么它不需要堆栈来记住它的返回地址。

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

在尾递归函数中调用函数本身后无事可做，但这对我来说没有意义。

Answer 1

编译器可以简单地转换这个

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

Answer 2

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

我想扭转这种局面。它确实使用堆栈来记住返回地址。诀窍是发生尾递归的函数在堆栈上有自己的返回地址，当它跳转到被调用函数时，它会将其视为自己的返回地址。

具体来说，没有尾调用优化：

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

编辑：上面的示例使用一个函数调用另一个函数的情况。当函数调用自身时，机制是相同的。

Answer 3

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

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

Answer 4

递归函数中必须存在两个元素：

1. 递归调用
2. 一个记录返回值的地方。

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

常规递归函数中的返回值由两种类型的值组成：

• 其他返回值
• 拥有函数计算的结果

让我们看看你的例子：

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

请注意，除了我提到的值之外，每个堆栈都存储函数的整个范围。因此，递归函数 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]]]]

看到差异了吗？在“常规”递归调用中，返回函数递归地组成最终值。在尾递归中，他们只引用基本情况（最后一个评估）。我们称accumulator为跟踪旧值的参数。

递归模板

常规递归函数如下：

type regular(n)
    base_case
    computation
    return (result of computation) combined with (regular(n towards 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)

看到不同？

尾调用优化

由于尾调用堆栈的无边界情况没有存储任何状态，因此它们并不那么重要。一些语言/解释器然后用新堆栈替换旧堆栈。因此，由于没有限制调用次数的堆栈帧，尾调用在这些情况下的行为就像一个 for 循环。

由你的编译器来优化它，或者不。

Answer 5

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

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

}

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

Answer 6

递归函数是一个自己调用的函数

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

不利的一面是，如果编写不当，它们可能会导致无限循环和其他意外结果。

我将解释简单递归函数和尾递归函数

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

1. 要考虑的第一点是什么时候应该决定退出 if 循环
2. 第二个是如果我们是自己的函数要做什么流程

从给定的例子：

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

从上面的例子

if(n <=1)
     return 1;

是何时退出循环的决定因素

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循环，所以它返回4 * fact(3)

2. 在堆栈内存中，我们有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)

记住我们调用了```4 * fact(3)`

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

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

3. 在堆栈内存中，我们有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)

输出为fact(2) = 2 * fact(1)

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

3. 在堆栈内存中，我们有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

记得我们打电话4 * 3 * 2 * fact(1)

输出为fact(1) = 1

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

最后，fact(4) = 4 * 3 * 2 * 1 = 24

尾递归将是

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)

2. 在堆栈内存中，我们有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)

2. 在堆栈内存中，我们有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循环失败，所以它进入else循环

所以它返回fact(1, 24)

3. 在堆栈内存中，我们有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循环是真的

所以它返回running_total

输出为running_total = 24

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

Answer 7

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

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

1. 让正在进行的函数结束（即调用使用的堆栈）
2. 将要用作函数参数的变量存储在临时存储器中
3. 在此之后，使用临时存储的参数再次调用该函数

如您所见，我们在同一函数的下一次迭代之前结束了原始函数，因此我们实际上并没有“使用”堆栈。

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

Answer 8

编译器有足够的智能来理解尾递归。如果从递归调用返回时，没有挂起的操作并且递归调用是最后一条语句，则属于尾递归的范畴。编译器基本上执行尾递归优化，删除堆栈实现。考虑下面的代码。

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

这就是编译器进行尾递归优化的方式。