Shulou(Shulou.com)06/03 Report--

This article introduces the case and code of recursive function in Javascript. The content is very detailed. Interested friends can use it for reference. I hope it will be helpful to you.

one。 Understanding of Recursive function

1. Recursion in life

A typical example of "recursion" in life is "asking for directions". As shown in the picture, after entering the cinema, the little brother could not find his seat and asked his little sister, "which row is this?" the little sister asked forward in turn. After asking the audience in the first row, they gave back the results in turn, "I am the first row" and "I am the second row". Finally determine the number of rows in which their seats are located.

In this process, it fully reflects the idea of "transmission" (inquiry) and "return" (feedback), so this phenomenon is called "recursion".

2. Recursion in programming

Computers have two characteristics: "stupid" and "fast". Therefore, after the "complex problem" is transformed into "multi-step simple problem", the computer can execute efficiently.

Recursion is a kind of programming algorithm, which simplifies some complex problems by calling itself, and it is easy to get a solution.

The following is a simple case study of recursion in programming

Case: calculate the sum of 1 / 2 / 3 / 4 / 5 / 6.

Function fn (n) {if (n = 1) {return 1;} return n + fn (n-1);} fn (6)

Calculation process: F (6) = 6 + f (5)

F (6) = 6 + 5 + f (4)

F (6) = 6 + 5 + 4 + f (3)

F (6) = 6 + 5 + 4 + 3 + f (2)

F (6) = 6 + 5 + 4 + 3 + 2 + f (1)

F (6) = 6 + 5 + 4 + 3 + 2 + 1

From the above, we can see the nature of recursive functions:

Call itself

There are two elements in the implementation of recursive functions:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

Termination condition

Gradually approaching the termination condition

The termination condition in the case is fn (1) = 1 when n = 1. If there is no termination condition, the function will continue to calculate f (0), f (- 1), f (- 2) and enter the endless loop, unable to get the result.

Through the calculation process, we can see that the function calculates f (6), f (5), f (4), f (3), f (2), f (1) in turn, which satisfies the second element gradually approaching the termination condition.

two。 The use of recursive functions

Through the above explanation, we must have understood the principle of recursive function.

So how are recursive functions written?

How to use recursive functions to solve practical problems?

Exploring the "routine" of Recursive function Writing with examples

Example: calculate the factorial of n.

Step 1: find the termination condition and write to if

Mathematical knowledge: n! = n * (n-1) * (n-2) * (n-3) * * 3 * 2 * 1

Obviously, the termination condition is n = 1; when, return 1; therefore, the first half of the function can be completed:

Function fn (n) {if (n = 1) {return 1;} / / to be continued}

Step 2: find the equivalent relation of the function and write it to return

Mathematical knowledge: n! = n * (n-1)!

Through mathematical knowledge n! = n * (n-1)! And the nature of recursive functions (calling itself)

It is concluded that the equivalent relation of the function is f (n) = n * f (n-1).

Thus, you can complete the second half of the function:

Function fn (n) {if (n = 1) {return 1;} return n * fn (n-1);}

At this point, a simple recursive function is written, and the most important feature of the recursive function is the simplicity of the code (simple enough to make people feel guilty).

To sum up, the writing "routine" of recursive function

1. Find the termination condition and write to if

two。 Find the equivalent relation of the function and write it to return

three。 The problem of recursive function

You would say that the above two examples can be easily written in loops, so why do you need to use recursion?

In fact, problems that can be solved with recursion can also be solved with loops! Moreover, the operation speed of recursion is slower than that of loops, because recursion needs to call functions layer by layer and occupy system memory. When the level of recursion is deeper, it consumes more performance and is often not recommended.

Q: what is the meaning of recursive existence?

Recursion is to simplify complex problems, provide ideas for solving problems, and then get a "circular algorithm".

For simple problems, you can see the "circular algorithm" at a glance, but for abstract problems, you can usually adopt recursive ideas first, such as:

Example: someone needs to walk up 10 steps. There are two ways to walk: one step at a time, and two steps at a time. The two walking methods can be used interchangeably. How many ways are there to walk up the 10 steps?

It is difficult to directly see the circular solution to this problem, so we might as well try to solve it from a recursive point of view:

When you are only one step away from reaching the 10th step, there are two possibilities:

Type 1: from level 8 to > level 10 (2 steps at a time)

Type 2: from level 9 to > level 10 (1 step at a time)

Suppose: from level 0 to level 8, there are x ways to go.

1,1,1,1,1,1,2,2

1,1,1,1,1,2,1,2

1,2,1,1,1,2,2

1,2,1,2,2,2

/ / endless, a total of x, the last step of each method is 2 (steps)

Suppose: from level 0 to level 9, there are y ways to go.

1,1,1,1,1,1,1,2,1

1,1,2,1,1,2,1,1

1,2,1,2,2,1,1

1,2,2,2,2,1

/ / inexhaustible, a total of y, the last step of each method is 1 (step)

Then, from level 0 to level 10, there are x + y ways.

Therefore, 10 step walking method = 9 step walking method + 8 step walking method, that is, f (10) = f (9) + f (8)

So the functional relationship we need is f (n) = f (n-1) + f (n-2).

Next, find the termination condition:

When there are 1 steps, there is only one way to walk (1 step and 1 step), which is n = 1; when return 1

When there are 2 steps, there are only 2 ways to walk (2 times, 1 step 1 step or 1 step 2 steps), which is n = = 2; when return 2

As a result, recursive functions can be written.

Function fn (n) {if (n = 1 | | n = 2) {return n;} return fun (n-1) + fun (n-2);}

The following figure shows the execution of the function

It can be seen that the same function (the same background color) has been called repeatedly in the process of function execution, which greatly consumes the performance of the system. After testing, this recursive function can be calculated to f (45) at most; the result around (testing should be careful), which is the main problem of recursive function.

So how to optimize this problem?

That is, the recursive algorithm is changed to a circular algorithm.

Through the previous derivation, we know that f (n) = f (n-1) + f (n-2)

Step 1 = = > method of walking: 1

2 steps = > method of walking: 2

3 steps = > method of walking: 1 + 2 = 3

4 steps = > walking method: 2 + 3 = 5

5 steps = > walking method: 3 + 5 = 8

6 steps = > method of walking: 5 + 8 = 13

7 steps = > walking method: 8 + 13 = 21

That is, as long as you know the results of the first two items (1 step and 2 steps), you can calculate the results of all the following items from the bottom up. So you can write a loop function.

Function fn (n) {if (n = 1 | | n = 2) {return n;} var left = 1; / / data on the left var right = 2; / / data on the right var sum = 0; for (var I = 3; I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.