What is tail recursion?

Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean exactly?

---

Consider a simple function that adds the first N integers. (eg sum(5) = 1 + 2 + 3 + 4 + 5 = 15 ).

Here is a simple JavaScript implementation that uses recursion:

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

If you called recsum(5) , this is what the JavaScript interpreter would evaluate:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

Note how every recursive call has to complete before the JavaScript interpreter begins to actually do the work of calculating the sum.

Here's a tail-recursive version of the same function:

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

Here's the sequence of events that would occur if you called tailrecsum(5) , (which would effectively be tailrecsum(5, 0) , because of the default second argument).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

In the tail-recursive case, with each evaluation of the recursive call, the running_total is updated.

Note: The original answer used examples from Python. These have been changed to JavaScript, since modern JavaScript interpreters support tail call optimization but Python interpreters don't.

---

In traditional recursion , the typical model is that you perform your recursive calls first, and then you take the return value of the recursive call and calculate the result. In this manner, you don't get the result of your calculation until you have returned from every recursive call.

In tail recursion , you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step. This results in the last statement being in the form of "(return (recursive-function params))" (I think that's the syntax for Lisp). Basically, the return value of any given recursive step is the same as the return value of the next recursive call .

The consequence of this is that once you are ready to perform your next recursive step, you don't need the current stack frame any more. This allows for some optimization. In fact, with an appropriately written compiler, you should never have a stack overflow snicker with a tail recursive call. Simply reuse the current stack frame for the next recursive step. I'm pretty sure Lisp does this.

---

An important point is that tail recursion is essentially equivalent to looping. It's not just a matter of compiler optimization, but a fundamental fact about expressiveness. This goes both ways: you can take any loop of the form

while(E) { S }; return Q

where E and Q are expressions and S is a sequence of statements, and turn it into a tail recursive function

f() = if E then { S; return f() } else { return Q }

Of course, E , S , and Q have to be defined to compute some interesting value over some variables. For example, the looping function

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

is equivalent to the tail-recursive function(s)

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(This "wrapping" of the tail-recursive function with a function with fewer parameters is a common functional idiom.)

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

上一篇: 什么是依赖注入？

下一篇: 什么是尾递归？