Recursion in Functional JavaScript

You may have heard of recursive functions in JavaScript, and even tried to write some. But you may not have seen many examples of recursion that actually works. In fact, besides the particularity of this approach, you may not have considered when and where recursion is useful, or how dangerous it is if used improperly.

Key points

• Recursion is a JavaScript method that allows the function to repeatedly call itself until the result is reached. It is particularly useful for problems involving iterative branches, such as fractal math, sorting or traversing complex or nonlinear data structures.
• While recursion can make the code more concise and easy to understand, if used improperly, it can be dangerous due to the risk of exceeding the engine's memory capacity. This is because JavaScript recursive functions need to keep track of where they are called from every time so that they can continue to execute in the right place.
• In many functional programming languages, a technique called tail call optimization is used to manage recursion. This allows each continuous loop in the recursive function to happen immediately, rather than piled up in memory. However, most JavaScript compilers are not optimized for this yet.
• Custom bounce functions can be built to iteratively manage recursive execution, leaving only one operation on the stack at a time. This can help avoid creating deep stack operations waiting to be performed, but usually at the expense of performance and readability.

Purpose of recursion

Recursion is a technique that iterates through the operation by having a function call itself repeatedly until the result is obtained. Most loops can be rewritten in recursive styles, and in some functional programming languages, this loop method is the default.

However, while JavaScript's functional programming style supports recursive functions, we need to realize that most JavaScript compilers are not currently safely optimized for them.

Recursion is best used when you need to repeatedly call the same function with different parameters in the loop. While it can be used in many cases, it is most effective in solving problems involving iterative branches such as fractal math, sorting or traversing nodes of complex or nonlinear data structures.

One of the reasons why recursion is favored in functional programming languages ​​is that it allows building code that does not require the use of local variables to set and maintain state. Recursive functions are also easy to test because they are easy to write in a pure way, have a specific and consistent return value for any given input and have no side effects on the state of the external variable.

Cycle

A classical function example that recursion can be applied is factorial. This is a function that returns the result of a number repeatedly multiplied by each previous integer, all the way to 1.

For example, the factorial of 3 is:

<code>3 × 2 × 1 = 6</code>

The factorial of

6 is:

<code>3 × 2 × 1 = 6</code>

You can see how quickly these results get bigger. You can also see us repeating the same behavior over and over again. We take the result of a multiplication operation and multiply it by the second value to minus 1. Then we do this again and again until we reach 1.

Using a for loop, it is not difficult to create a function that iterates to do this until the correct result is returned:

<code>6 × 5 × 4 × 3 × 2 × 1 = 720</code>

This works, but from a functional programming standpoint, it is not elegant. To support the for loop and then return the result, we have to use several local variables that maintain and track the state. Wouldn't it be more concise if we could discard the for loop and adopt a more functional JavaScript method?

Recursion

We know that JavaScript allows us to write functions that take functions as parameters. So what if we want to use the actual function we are writing and execute it in the context where we run it?

Is this even possible? sure! For example, consider such a simple while loop:

<code class="language-javascript">var factor = function(number) {
  var result = 1;
  var count;
  for (count = number; count > 1; count--) {
    result *= count;
  }
  return result;
};
console.log(factor(6));
// 720</code>

After this is done, the value of the counter has changed, but the loop has completed its job of printing each value, as we slowly extracted the state from it.

Recursive versions of the same loop may look more like this:

<code class="language-javascript">var counter = 10;
while(counter > 0) {
    console.log(counter--);
}</code>

Did you see how we call the countdown function directly in the definition of the countdown function? JavaScript handles it like a boss and only does what you want it to do. Every time countdown is executed, JavaScript tracks where it is called, and then goes back to the stack of that function call until it is finished. Our function also avoids modifying the state of any variable, but still uses the passed values ​​to control recursion.

Back to our factorial case, we can rewrite the previous function like this to use recursion:

<code class="language-javascript">var countdown = function(value) {
    if (value > 0) {
        console.log(value);
        return countdown(value - 1);
    } else {
        return value;
    }
};
countdown(10);</code>

Writing code in this way allows us to describe the entire process in a stateless way without any side effects. It is also worth noting that we first test the values ​​of the parameters passed to the function and then perform any calculations. We want any function that is about to call itself to exit quickly and cleanly when it reaches its termination. For factorials calculated in this way, when the incoming number is zero or negative, the termination situation is reached (we can also test negative values ​​and return different messages if we want).

Tail call optimization

One of the problems with contemporary JavaScript implementations is that they do not have a standard way to prevent recursive functions from stacking themselves infinitely and consuming memory until they exceed the engine's capacity. JavaScript recursive functions need to keep track of where they are called from every time so that they can continue to execute in the right place.

In many functional programming languages ​​such as Haskell and Scheme, this is managed using a technique called tail call optimization. Using tail call optimization, each continuous loop in the recursive function will happen immediately, rather than piled up in memory.

In theory, tail call optimization is part of the ECMAScript 6 (the next version of current JavaScript) standard, but most platforms have not fully implemented it yet.

Bounce function

If necessary, there are ways to force JavaScript to execute recursive functions in a safe way. For example, custom bounce functions can be built to iteratively manage recursive execution, leaving only one operation on the stack at a time. The bounce function used in this way can take advantage of JavaScript's ability to bind functions to a specific context in order to bounce the recursive function back to itself, building the result one at a time until the loop is complete. This will avoid creating deep stack operations waiting for execution.

In fact, using a bouncing function often reduces performance for safety. Furthermore, most of the elegance and readability we get by writing functions recursively is lost in the code convolution needed to make this approach work in JavaScript.

If you are curious, I encourage you to read more about this concept and share your thoughts in the discussion below. You can start with a short topic on StackOverflow and explore some articles by Don Taylor and Mark McDonnell that go deeper into the pros and cons of bouncing functions in JavaScript.

We are not at that point yet

Recursion is a powerful technique that is worth knowing. In many cases, recursion is the most straightforward way to solve complex problems. However, before ECMAScript 6 fully implements with tail call optimization where we need it, we need to be very careful about how and where the recursive is applied.

FAQs about recursion in functional JavaScript (FAQs)

What is the basic situation in recursion? Why is it important?

The basic situation in recursion is the condition that prevents the function from calling itself infinitely. It is crucial because without it, the recursive function will call itself infinitely, causing a stack overflow error. The basic situation is usually the condition that a function checks before making a recursive call. If this condition is met, the function returns a value and stops calling itself.

How does recursion work in JavaScript?

In JavaScript, recursion works by calling the function itself until the basic situation is reached. The function is divided into basic case and recursive case. The basic case returns a value without calling the function again, while the recursive case calls the function again with different parameters. The function continues to call itself until the base case is reached, at which point it starts returning the value.

What is tail recursion in JavaScript?

Tail recursion is a special type of recursion, where the recursive call is the last operation in the function. This is important because it allows JavaScript engine optimization to recurse, using a technique called tail call optimization. This can significantly reduce the amount of memory used by the function, allowing it to handle larger inputs.

What are the advantages and disadvantages of using recursion in JavaScript?

Recursion can make the code more concise and easy to understand by breaking complex problems into simpler problems. It is especially useful for tasks such as traversing tree data structures. However, recursion may also be less efficient than iterative solutions, and if implemented incorrectly, it may cause a stack overflow error.

How to avoid stack overflow errors in recursive functions?

When the recursive function calls itself too many times and fills the call stack, a stack overflow error will occur. To avoid this, make sure your recursive function has the basic case that will eventually reach. Also, consider using tail recursion, which the JavaScript engine can optimize to use less memory.

How is recursion used in functional programming?

In functional programming, recursion is often used as a replacement for loops. Since functional programming discourages the use of variable states, recursion can be used to perform repeated operations without changing any states.

Can all recursive functions be converted into iterative functions?

Yes, in theory, all recursive functions can be converted into iterative functions. However, iterative versions can be more complex and difficult to understand, especially for functions involving complex tree or graph traversals.

What is mutual recursion in JavaScript?

Mutual recursion refers to two or more functions being called with each other in a loop. This may be a powerful technique to solve certain types of problems, but it may also be harder to understand and debug than simple recursion.

How to debug recursive functions in JavaScript?

Draining recursive functions can be challenging due to repeated function calls. However, it may be helpful to print the function's parameters and return values ​​at each step using the console.log statement. Additionally, it is very useful to use a debugger tool that allows you to perform function calls step by step.

Are there any performance considerations when using recursion?

Yes, a recursive function may not be as efficient as its iterative counterpart due to the overhead of repeated function calls. If they call themselves too many times, they can also cause a stack overflow error. However, in many cases, the readability and simplicity of a recursive solution can outweigh these performance considerations.

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