Understanding Recursion With JavaScript

Some problems are more suitable for recursion. For example, a sequence such as a Fibonacci sequence has a recursive definition. Each number in the sequence is the sum of the first two numbers in the sequence. Problems that need to be built or traversed with tree data structures can also be solved by recursion. Training yourself to think recursively will give you powerful skills to solve such problems.

In this tutorial, I will explain step by step how several recursive functions work and show you some techniques to systematically define recursive functions.

content:

• What is recursion?
• Digital recursion
• List recursion
• Build a list
• Tail recursion
• Summarize

What is recursion?

Recursively defined functions are functions defined by their simplified versions themselves. Here is a simplified example:

 function doA(n) {
    // ...
    if (n > 0) {
        doA(n-1);
    }
}

To conceptually understand how recursion works, we will look at an example that is code-independent. Suppose you are responsible for answering calls from the company. Since this is a busy company, your phone has multiple phone lines, you can handle multiple phone calls at the same time. Each phone line has a button on the handset, which will flash when there is an incoming call. Today, when you go to work and turn on the phone, four lines flash at the same time. So you start answering all the calls.

You pick up the first line and tell them: "Please wait." Then you pick up the second line and put them on standby too. Next, you pick up the third line and put them on standby, and so on. Finally, when you finish each call, you go back to the previous caller, complete that call and hang up.

Each call in this example is similar to a recursive call in a function. When you get a call, it is put into the call stack (in code). If you can't complete a call immediately, you put it on standby. If your function call cannot be calculated immediately, it will remain in the call stack. When you can answer the call, it will be picked up. When your code is able to calculate function calls, it pops out of the stack. Remember this metaphor when you look at the following code example.

Digital recursion

All recursive functions require a basic case so that they can terminate. However, just adding a base case to our function does not prevent it from running infinitely. The function must have a step to bring us closer to the basic situation. This is the recursive step. In the recursive step, the problem is reduced to a smaller version of the problem.

Suppose you have a function that multiplies all numbers starting from n. This is called the factorial function, we write it as 4!, if n is equal to 1.

In each step you will subtract 1 from the current number. What is the recursive situation? The recursive case is the function fact(4).

16. Is 4 equal to 1? no. Put fact(3).
17. Is 3 equal to 1? no. Put fact(2).
18. Is 2 equal to 1? no. Put fact(1).
19. Is 1 equal to 1? yes. Returns fact(2) and returns 2.
20. Get 3 * fact(2) is fact(4) and returns 24.

Here is another way to see how the function handles each call:

 <code>fact(4) 4 * fact(3) 4 * ( 3 * fact(2) ) 4 * ( 3 * ( 2 * fact(1) )) 4 * ( 3 * ( 2 * 1 ) ) 4 * ( 3 * 2 ) 4 * 6 24</code>

In recursive cases, the parameters should change and bring you closer to the basic case. This parameter should be tested in basic cases. In the previous example, because we subtract 1 in the recursive case, in the basic case we test whether the parameter is equal to 0.

challenge

1. Implement the sum function using loops instead of recursively.
2. Create a function that recursively multiplies two numbers. For example, 0; otherwise, you return the first element of the array plus sum call.
3. Simplifies the filter function so that it removes all items from the list. For example, ["a", "b", "d"].

Tail recursion

Tail recursion is a form of recursion that allows the compiler to perform tail call optimization (TCO) to prevent many performance flaws of ordinary recursion. In addition, tail recursion solves the problem of maximum depth of function calls. However, you have to write the function somehow to make it work.

Tail recursion is suitable for functions that call recursive functions at the end of a function. For example, here is the tail recursive version of the sum() function: the entire return value of sum() is the entire return value, so the runtime can safely discard the external function and return only the results of the internal function. However, many people will trip over something like this:

 function notTailRecursive(n) {
    // ...
    return notTailRecursive(n) 1
}

You might think this uses tail recursion because the recursive function is called at the end. But, it doesn't. This is because JavaScript must return to an external function to add 1. One of the ways you can rewrite it is to pass 1 into the argument so that the inner function can do that calculation.

Not all browsers currently support tail call optimization, but it is in the ES standard, so we may see more support for it in the future. Furthermore, it is usually a good practice because it usually isolates changes to function parameters.

challenge

Reconstruct an example recursive function in this article into a tail recursive function.

Summarize

There are three parts for recursive functions. The first is the basic situation, which is the termination condition. The second is the step that brings us closer to the basic situation. The third is the recursive step, where the function calls itself with simplified input.

Recursion is like iteration. Any function you can define recursively or using a loop. Other things to consider when using recursion include recursive nested lists and optimized recursive calls.

You can refactor the recursive function into a tail recursive function, which can provide performance advantages.

A good resource to continue learning recursion is the book The Little Schemer. It uses a Q&A format to teach you how to think recursively.

This post has been updated with Jacob Jackson's contributions. Jacob is a web developer, tech writer, freelancer and open source contributor.

The above is the detailed content of Understanding Recursion With JavaScript. For more information, please follow other related articles on the PHP Chinese website!