尾递归如何工作？ [英] 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.

推荐答案

编译器可以轻松地对此进行转换

The compiler is simply able to transform this

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

这篇关于尾递归如何工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！