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

into something like this:

int fac_times (int n, int acc) {
label:
    if (n == 0) return acc;
    acc *= n--;
    goto label;
}

---

You ask why "it doesn't require stack to remember its return address".

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.

Concretely, without tail call optimization:

f: ...
   CALL g
   RET
g:
   ...
   RET

In this case, when g is called, the stack will look like:

   SP ->  Return address of "g"
          Return address of "f"

On the other hand, with tail call optimization:

f: ...
   JUMP g
g:
   ...
   RET

In this case, when g is called, the stack will look like:

   SP ->  Return address of "f"

Clearly, when g returns, it will return to the location where f was called from.

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

---

Tail recursion can usually be transformed into a loop by the compiler, especially when accumulators are used.

// tail recursion
int fac_times (int n, int acc = 1) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

would compile to something like

// accumulator
int fac_times (int n) {
    int acc = 1;
    while (n > 0) {
        acc *= n;
        n -= 1;
    }
    return acc;
}

链接地址: http://www.djcxy.com/p/80672.html

上一篇: 递归本身就是一个功能吗？

下一篇: 尾递归究竟如何工作？