Introduction to the

Some problems can be solved more naturally using recursion. For example, consider the Fibonacci sequence: each number in the sequence is the sum of the first two numbers in the sequence. Any problem that requires you to build or traverse a tree data structure can be solved recursively. Exercise your strong recursive thinking and you will find it very easy to solve such problems.

In this article, I’ll give you two examples of how recursive functions work.

The outline
  • What is recursion
  • Recursion of numbers
  • Array recursion
  • conclusion

What is recursion

Recursion of a function is a call to itself within a function. Here’s a simple example:

function doA(n) {... doA(n- 1);
}
Copy the code

To understand how recursion works in theory, let’s take an example that has nothing to do with code. Imagine that you are a telephone operator in a company. Since this is a busy company, your landline is connected to multiple lines, so you can handle multiple calls at the same time. Each line corresponds to a button on the receiver that flashes when an incoming call comes in. When you arrive at work today, there are four buttons flashing, so you need to answer all those calls.

You get on line one and tell him “please hold”, you get on line two and tell him “please hold”, you get on line three and tell him “please hold”, and finally you get on line four and talk to him. When you finish talking to line 4, you go back to line 3, when you finish talking to line 3, you go to line 2, when you finish, you go to line 1, when you finish talking to the customer on line 1, you can finally put down the phone.

Each call in this example is like a recursive call to a function. When you receive a call and cannot deal with it immediately, the call is put on hold; When you have a function call that doesn’t need to trigger immediately, it stays on the call stack. When you can answer a phone call, the line is connected; When your code can trigger a function call, it pops off the call stack. Recall this metaphor when you look at the code examples later and get a little confused.

Recursion of numbers

Every recursive function needs a termination condition so that it does not loop endlessly. However, simply adding a termination condition is not enough to avoid an infinite loop. The function must approach the termination condition step by step. In recursive steps, problems are reduced to smaller problems.

Let’s say I have a function that goes from 1 to n. For example, when n = 4, it implements “1 + 2 + 3 + 4”.

First, we need to look for termination conditions. This step can be thought of as finding the condition that ends the problem without recursion. When n equals zero, we can’t split anymore, so our recursion stops at zero.

In each step, you will subtract 1 from the current number. What are recursive conditions? Call the function sum with the decreasing number.

function sum(num){
    if (num === 0) {
        return 0;
    } else {
        return num + sum(--num)
    }
}
 
sum(4);     / / 10
Copy the code

Each step is as follows:

  • Perform the sum (4).
  • Is 4 equal to 0? If no, keep sum(4) and execute sum(3).
  • Is 3 equal to 0? If no, keep sum(3) and execute sum(2).
  • Is 2 equal to 0? If no, leave sum(2) and execute sum(1).
  • Is 1 equal to 0? If no, leave sum(1) and execute sum(0).
  • Is 0 equal to 0? If yes, calculate sum(0).
  • Extract the sum (1).
  • Extract the sum (2).
  • Extract the sum (3).
  • Extract the sum (4).

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

sum(4)
4 + sum(3)
4 + ( 3 + sum(2))4 + ( 3 + ( 2 + sum(1)))4 + ( 3 + ( 2 + ( 1 + sum(0))))4 + ( 3 + ( 2 + ( 1 + 0)))4 + ( 3 + ( 2 + 1))4 + ( 3 +  3 ) 
4 + 6 
10
Copy the code

We can see that the parameters in the recursive condition change and gradually approach and eventually meet the termination condition. In the case above, we decrement the parameter by one at each step of the recursive condition, and finally test whether the parameter is equal to 0 in the termination condition.

task
  1. Write a sum of numbers using a regular loop instead of recursively.
  2. Write a recursive function to multiply two numbers. Such as:Multiply (2, 4)Will return 8, writeMultiply (2, 4)What happens at each step.

Array recursion

The recursion of an array is similar to the recursion of a number, similar to the decrement of numbers, where we decrement the number of elements in the array at each step until we get an empty array.

Consider taking an array as an argument to a summation function and returning the sum of all the elements in the array. The summation function is as follows:

function sum(arr) {
    var len = arr.length;
    if (len == 0) {
        return 0;
    } else {
        return arr[0] + sum(arr.slice(1)); }}Copy the code

If the array length is equal to 0, 0 is returned, arr[0] represents the first digit of the array, and arr.slice(1) represents the arR array truncated from the first digit and returns the truncated array. Var arr = [1,2,3,4]; , arr[0] = 1, arr. Slice (1) = [2,3,4]. What happens when we execute sum([1,2,3,4])?

sum([1.2.3.4])
1 + sum([2.3.4])
1 + ( 2 + sum([3.4]))1 + ( 2 + ( 3 + sum([4)))1 + ( 2 + ( 3 + ( 4 + sum([]) )))
1 + ( 2 + ( 3 + ( 4 + 0)))1 + ( 2 + ( 3 + 4))1 + ( 2 + 7 ) 
1 + 9
10
Copy the code

Each execution checks to see if the array is empty; otherwise, recursion is performed on the array with progressively decreasing elements.

task
  1. Write the sum function of an array using the regular loop method instead of recursively.
  2. To define alength()The Array function returns the length of the Array (you cannot use the Javascript Array object’s built-in length property). Such as:length(['a', 'b', 'c', 'd'])And write down what happened at each step.

conclusion

A procedure or function in the introduction to the definition or call their own, directly or indirectly, with a kind of method, it is usually the problem of a large complex layers into a similar to the original problem of smaller problems to solve, the recursion strategy only a small number of procedures can be required to describe the problem solving process of repeatedly calculation, greatly reduces the amount of program code.

Here are just two small examples to illustrate recursion, both of which are in the form of a variable plus a function. Of course, there are many examples of function plus a function, such as the famous Fibonacci sequence mentioned at the beginning of this article. The code is as follows:

function func( n ) { 
    if (n == 0 || n == 1) {
        return 1;
    }
        return func(n- 1) + func(n2 -);
}
    
Copy the code

Here are the steps and pros and cons of using recursion.

steps
  1. Find the rule, convert the rule into a formula return.
  2. Find the exit, the exit is the termination condition, it must be a known condition.
advantages
  1. The code is unusually clean.
  2. It fits the human mind.
disadvantages
  1. Since recursion is a call to the function itself, function calls consume time and space: with each call, space is allocated in the memory stack to store parameters, temporary variables, return addresses, and so on, pushing and popping data onto the stack takes time. This is bound to lead to a significant reduction in execution efficiency.
  2. Most of the calculation in recursion is repetitive, and its essence is to break down a problem into many small problems, which overlap each other. Such repeated calculation will also lead to low efficiency.
  3. The call stack may overflow. The stack has a capacity limit, and when there are too many levels of calls, the stack can exceed its capacity limit, resulting in stack overflow!

So the disadvantages of recursion are obvious, in the actual development, under controlled circumstances, reasonable use.

Thank you for reading!