尾递归与非尾递归

1. Introduction

In this tutorial, we’ll explain what tail recursion is. We’ll also talk about the advantages tail-recursive functions have over non-tail recursion.

2. Recursion

In brief, a recursive function is any function that calls an instance of itself. Let’s take a look at a function for summing arrays:

algorithm RecursiveSum(x):
    // INPUT
    //    x = [x_1, x_2, ..., x_n] - the array to sum
    // OUTPUT
    //    The sum x_1 + x_2 + ... + x_n

    if x is empty:
        // the base case
        return 0
    else:
        // the recursive call
        return x_n + RecursiveSum([x_1, x_2, ..., x_{n-1}])

We see that ![SUM(x_1, x_2, \ldots, x_n) makes a recursive call to , which in turn calls , and so on until the base case of . This presents three issues: two pertaining to recursively processing the input, and one related to memory.

2.1. The Traversal Issues

The first issue is that we risk a stack overflow. If the recursion is too deep, it will eventually run out of the stack space and be unable to add a new frame. This scenario plays out in the case of inputs that are too large.

The second is that calculation starts from the base case, and we traverse the whole array to reach it. During that pass, we don’t do any calculations. Only after hitting the base case can we start adding the array’s elements to one another. We do so by going back to the first call. So, we pass the input array twice instead of once, as illustrated on the example of :

   

2.2. Memory

The third issue is that each recursive call adds a new frame to the call stack, and each frame reserves additional memory for local variables and input arguments. That’s not a problem in our previous example but is in the next one. For example, let’s imagine that we don’t have in memory the array we want to sum. Instead, we can get by downloading a gigabyte of raw data from and processing it to get a single number:

algorithm DownloadAndSum(u):
    // INPUT
    //    u = the URLs url_1, url_2, ..., url_n pointing to the elements x1, x2, ..., xn of the array we want to sum
    // OUTPUT
    //    The sum of x1 + x2 + ... + xn

    if u is empty:
        return 0
    else:
        data_n <- download the data from url_n
        x_n <- process data_n
        return x_n + DownloadAndSum([url_1, url_2, ..., url_{n-1}])

Now, each stack frame takes a gigabyte of memory even though we don’t need to hold the raw data after processing them.

3. Tail vs. Non-Tail Recursion

Both problems stem from the fact that and are non-tail recursive functions. A function is tail-recursive if it ends by returning the value of the recursive call. Keeping the caller’s frame on stack is a waste of memory because there’s nothing left to do once the recursive call returns its value. So, instead of allocating a new frame for the call, we can reuse the existing one. As a result, compilers can recognize a tail-recursive function and optimize frame allocation.

To benefit from tail-call optimization, a function need not be recursive. It can call any function, as long as the only thing to do after the call is to return the called function’s value. However, we’ll focus only on recursions in this article.

3.1. Tail-Recursive SUM

isn’t tail-recursive because, after the recursive call, it adds to the returned value. To make it tail-recursive, we should adjust it a bit. More specifically, we should move addition into an argument so that the last line is . The idea is to sum the numbers as we pass through the array the first time and pass the current partial sum as an argument to . That way, there’s no need to go back once we reach the base case, and the same frame can be reused:

algorithm SUM(x, s):
    // INPUT
    //    x = the array to sum
    //    s = the current partial sum
    // OUTPUT
    //    The sum x_1 + x_2 + ... + x_n

    if x is empty:
        // the base case
        return s
    else:
        // the recursive call
        return SUM([x_1, x_2, ..., x_{n-1}], s + x_n)

We call it with as the initial value for , and here’s how its execution would look like for :

   

The same strategy would work with and other non-tail recursions. However, not all functions can be tail-optimized. If we have to process the recursive call’s return value in any way, then tail-call optimization is impossible.

4. Deriving Iterative Algorithms from Tail-Recursive Functions

Writing tail-recursive functions is equivalent to using a GOTO command in place of the recursive call:

algorithm SUM(x, s):
    // INPUT
    //    x = [x_1, x_2, ..., x_n] = the array to sum
    //    s = the current partial sum (set to 0 in the first call)
    // OUTPUT
    //    The sum x_1 + x_2 + ... + x_n

    s <- 0
    // sum loop
    if n = 0:
        return s
    else:
        s <- s + x_n
        n <- n - 1
        GOTO sum loop
        
    return s

We made two other changes. First, the partial sum became a local variable that we initialize at the beginning of . The second change is that now we treat as a variable that points to the end of the unprocessed part of the array. So, we decrease it by 1 step by step, right before each GOTO.

4.1. From GOTO to WHILE

The above GOTO function translates to an iterative algorithm with a while-loop. The negation of the base case condition becomes the while-loop’s condition. The else-branch, except for the GOTO command, becomes the body of the while-loop, and the initialization of the partial result comes before the loop. Finally, we move the base case after the loop and get an iterative function. We iterate over the size of the input. In our example, that will be , so the while loop’s condition is :

algorithm Sum(x):
    // INPUT
    //    x = the array to sum
    // OUTPUT
    //    The sum x_1 + x_2 + ... + x_n

    s <- 0

    while n > 0:
        s <- s + x_n
        n <- n - 1

    return s

5. Conclusion

In this article, we explained the difference between the tail and non-tail recursion. The functions of the former type can reuse the existing stack frame, so they save memory and avoid the stack overflow error. Also, they finish the calculation after processing the base case, so they don’t traverse the call stack back to the original frame. However, to be tail-recursive and enjoy these benefits, a function has to end by returning the return value of the recursive call.