Tail recursion is an optimization strategy compared with ordinary recursive functions.

Introduction of the recursive

Recursion is when a function calls itself again. So a recursive function must internally define a base case, and when this base case occurs, the function can return the result. Otherwise the recursion will call itself endlessly and eventually fill up the memory where the program is running.

Here are a few similar examples where recursive functions might be used

Fibonacci numbers

The Fibonacci sequence is that the first number is 1, the second number is also 1, but the third number is the sum of the first two numbers, and so on. The sequence is as follows:

1 1 2 3 5 8 13 21 34 55 89 144...Copy the code

Since all but the first number can be obtained by adding the first two numbers, the law of the Fibonacci sequence can be expressed by a recursive function.

function fibonacci(n) {
    if (n === 1 || n == 2) {
        return 1
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2)}}Copy the code

Array sum

Suppose there is a sequence [n1, n2, n3… And how wilt thou find the sum of all their numbers? At this point, we can also imagine that the sum of N numbers can be derived as the sum of the NTH number plus all the preceding numbers, where the NTH number is known, so we can use this as the base case, and then use the above derivation as our recursive function.

function sum(arr) {
    function helper(n) {
        if (n === 0) {
            return arr[0];
        } else {
            return arr[n] + helper(arr[n - 1]); }}return helper(arr.length - 1);
}
Copy the code

Take N factorial

Factorial is also a mathematical concept, where the factorial of any number is equal to that number multiplied by anything less than that number until it reaches 1, such as the factorial of 5 as follows

5! Is equal to 5 times 4 times 3 times 2 times 1Copy the code

So we can also use recursive function to express this law, where 1 is the base case, and each time multiplied by 1 less than the current number is the recursive function itself.

function factorial(n) {
    if (n === 1) {
        return 1;
    } else {
        return n * factorial(n - 1); }}Copy the code

Through the above three cases, we can understand how recursion is applied to solve practical problems, and know which rules of problems can be solved by recursion, that is, there is a situation of repeating itself.

So what is tail recursion?

Tail recursion is introduced

Tail recursion is a recursive optimization method based on some problems existing in recursion. For example, the following problems

Stack overflow

Recursion itself is divided into “recursion” and “return” two processes, “recursion” refers to progressive, a problem to a deeper level of sub-problems to solve, and “return” refers to when the most basic situation is triggered, reverse the previous progressive order, the result of the process from inside out back to the outermost function call.

We can see from the example above that when we use recursion to solve for a large input, such as the 500th Fibonacci number, or the sum of a sequence of five million numbers, or the factorial of 100.

So what are we facing?

As we know, different programming languages have their own design for function calls. In the case of JavaScript, each time a function is called, the JS engine actually puts that function call into a place called the execution stack, where it is to be executed. The variables used in the function will exist in the stack, and these stacks and execution stacks are the actual memory space allocated to the JS engine by the computer, and its upper limit is certain.

The recursive functions we have written above are logically fine, but from a practical execution point of view, there is a fatal risk of Stack Overflow, also known as Stack Overflow, when encountering large inputs.

Taking Fibonacci sequence problem as an example, when we call Fibonacci (500), the JS engine will push Fibonacci (500) into the execution stack, and when the event loop queue is idle, it will take out the task at the top of the stack from the execution stack for execution, that is, to parse the execution of Fibonacci (500). When Fibonacci (500) is executed, Fibonacci (499) and Fibonacci (498) need to be executed respectively. After the results of Fibonacci (500) are obtained, Fibonacci (499) and Fibonacci (498) need to be added and returned.

We didn’t know the results of either, so we pushed Fibonacci (499) and Fibonacci (498) into the execution stack, and we pushed one Fibonacci (500) out of the execution stack, only to push two new tasks.

This was not the worst, but when Fibonacci (499) was executed, two new execution tasks were created, namely Fibonacci (498) and Fibonacci (497), before Fibonacci (498) had even been executed. Similarly, Stack space quickly fills up, causing the JS engine to become overwhelmed and throw Stack Overflow program errors.

Computing redundancy

So what’s wrong with ordinary recursive functions? Let’s take the summation of a sequence. Let’s say we want to find the sum of [3, 5, 9, 7, 11, 28]. So what’s going on in our program is

sum(4) + 28 sum(3) + 11 + 28 sum(2) + 7 + 11 + 28 sum(1) + 9 + 7 + 11 + 28 sum(0) + 5 + 9 + 7 + 11 + 28 3 + 5 + 9 + 7 + 11 plus 28 8 plus 9 plus 7 plus 11 plus 28 17 plus 7 plus 11 plus 28 24 plus 11 plus 28 35 plus 28 63Copy the code

This might not be intuitive, but let’s see how the factorial function works

factorial(5) = 5 * factorial(4)
             = 5 * 4 * factorial(3)
             = 5 * 4 * 3 * factorial(2)
             = 5 * 4 * 3 * 2 * factorial(1)
             = 5 * 4 * 3 * 2 * 1
             = 5 * 4 * 3 * 2
             = 5 * 4 * 6
             = 5 * 24
             = 120
             
Copy the code

And you might wonder why we’re doing this, because we’ve seen a lot of things in between, like sum(3) + 11 + 28, and you can just sum(3) + 39, and you already have two visible numbers, so why wait until the end, Why don’t you just fill it up and move on.

And the execution of factorial, why not multiply all the numbers you see in the middle and then multiply the unknown function call, say, as follows

factorial(5) = 5 * factorial(4) 
             = 20 * factorial(3) 
             = 60 * factorial(2) 
             = 120 * factorial(1) 
             = 120
             
Copy the code

Isn’t that much better? Either! You’re right, this is actually an optimization for tail recursion.

The so-called tail recursion, is in each recursive process, will be able to calculate the content of the first execution, and then go to the next recursive function call. In this way, when the whole recursive process comes to the base case, which is the end of the recursive call, the result of the entire recursive execution can be directly obtained.

So you might say, well, if we have this intuitive solution, why do we have this inefficient recursive solution? That’s because this is the space that you can optimize from the point of view of the implementation of the program, and from the point of view of the original recursive function, it’s more intuitive to write the program that way.

Let’s go back and forth to the original code

function factorial(n) {
    if (n === 1) {
        return 1;
    } else {
        return n * factorial(n - 1); }}Copy the code

The intuitive way to write this function is that we already know the factorial result of 1, so we’ll use that as the base case. And then the factorial of any other number is the product of that number and the factorial of the preceding number. The logic doesn’t seem problematic, it’s intuitive.

But when it’s actually executed, because of the way the programming language is designed to execute functions, when we come across a new function call, we take precedence over the execution of the function, putting the function on the execution stack. Therefore, between the layers of recursive function, it depends on the “return” process to do the specific calculation. This is why you see multiple numbers multiplied, but then proceed to the next level of the function call, rather than compute the intermediate results and then proceed to the function call.

The seemingly optimizable process above is that we use mathematical thinking to lay out the entire process on a sheet of paper, so it’s intuitive that the middle numbers can be multiplied to reduce the computation. But in a computer program, those numbers are not really in the same area. For example, 5 * factorial(4) is the result of calling factorial(5), where 5 and factorial are in the execution region of factorial(5). The program will delimit a region for temporary storage for 5 and factorial. This range is delimited for the execution of factorial of 5. And when factorial of 4 is evaluated, there will be a separate area for factorial of 4 to house 4 and factorial of 3. So the 5 and the 4 are isolated from each other, so you can’t compute ahead of time.

So tail recursion can do what we saw above, “ahead of time”, and carry the result of the intermediate calculation into the next level of recursion, just by adding an argument to the recursive function.

function factorial(n) {
    function helper(n, temp) {
        if (n === 1) {
            return temp;
        } else {
            temp = n * temp;
            return helper(n - 1, temp); }}return helper(n, 1);
}
Copy the code

This function is executed as follows

Execution stack temp return
– 1 –
factorial(5) 5 helper(4, 5)
factorial(4) 20 helper(3, 20)
factorial(3) 60 helper(2, 60)
factorial(2) 120 helper(1, 120)
factorial(1) 120 120

Compared with the ordinary recursive function, we add a parameter to store the intermediate calculation process for the recursive function, so that the whole recursive process only needs to calculate in the “recursive” process, and then update the intermediate results calculated in each layer of recursion into this parameter, and continue to pass down.

In this way, in the process of “return”, since the intermediate parameter always keeps the latest calculation result, when reaching the end of the recursion, the value stored in this parameter is the final result of the whole recursion, and it only needs to be directly returned layer by layer. This also saves extra space that we would have allocated for temporary values 5, 4, 3, 2 at each level of recursion.

Memory footprint

These temporary value occupies space is also the third disadvantage of ordinary recursive, namely the footprint, because these intermediate value preserved to recursive implementation to “return” to use in the process, so every layer of recursive will produce a large number of intermediate data, and the intermediate data before the recursive achieve basic situation will take up a lot of memory space program.

Tail recursion becomes an iterative function

We know that most of the code written recursively can be rewritten to be iterative, because recursive functions are eventually parsed into iterative functions.

So let’s try to rewrite our recursion code in iterative form, and here we do it in a step-by-step way, by first writing the original recursion as a goto execution.

So let’s take the factorial function, the original recursion is

function factorial(n) {
    function helper(n, temp) {
        if (n === 1) {
            return temp;
        } else {
            temp = n * temp;
            returnhelper(n, temp); }}return helper(n, 1);
}
Copy the code

If we use the goto syntax, we can change it slightly to the following

function factorial(n) {
    let temp = 1;
    function helper(n) {
        if (n === 1) {
            return temp;
        } else {
            temp = n * temp;
            n = n - 1; Goto the first3Line}}return helper(n);
}
Copy the code

Here we take the intermediate variable parameters that were originally brought into each level of recursion and pull them out of the recursion. Then, we transform the program in goto form into an iterative function form on this basis.

function factorial(n) {
    let temp = 1;
    while(n ! = =1) {
        temp = n * temp;
        n = n - 1;
    }
    return temp;
}
Copy the code

The point here is that, in our analysis, the recursive part is actually something that is repeated over and over again. The trigger condition is that the “basic condition” has not been reached. So we can change the condition that triggers the recursion to the condition that triggers the loop, such that the code in the recursive program above slightly modifies the judgment logic, as follows

function factorial(n) {
    let temp = 1;
    function helper(n) {
        if(n ! = =1) {
            temp = n * temp;
            n = n - 1; Goto the first3Line}else {
            returntemp; }}return helper(n);
}
Copy the code

That makes it a lot clearer

  1. They both agree on how and where intermediate variables are stored.
  2. And then there’s the main repetition, and for recursive and iterative loops, which is the trigger condition for the repetition of the program, n hasn’t reached 1, so the program hasn’t reached the base case.
  3. In the execution of each layer, it is necessary to calculate the intermediate result that can be obtained so far, namely, temp = N * temp. In order to continue to enter the next layer, it is necessary to reduce the cycle identification by 1, namely, n = n-1
  4. The goTO in the recursion completes the execution of the current iteration and continues to the next iteration
  5. Finally, when the program continues to repeat the condition is not satisfied, that is, the base case is reached, the program will always store the latest intermediate results of the variable value returned

summary

This article is my summary of some personal understanding in the process of learning tail recursion. Some of them refer to many existing explanations on the Internet. If there are content errors or inaccurate explanations, please correct them.

Learning recursion helps us to understand the internal principles of program operation, such as the differences in storage and processing of recursive intermediate variables in different programming languages in the process of recursive execution, as well as the various means of program optimization resulting from this. In addition, it is a valuable programming exercise to understand that recursion can eventually be converted into iterative loops during program execution, and to learn how to manually convert recursion into iterative form.