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

This article introduces the relevant knowledge of "JavaScript Recursion and sequence of knowledge points". In the operation of actual cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1. What is recursion

In a program, the so-called recursion is that the function itself calls itself directly or indirectly.

1.1 call yourself directly

Function f () {console.log (1); f ();}

1.2 call yourself indirectly

Function F1 () {f2 ();} function f2 () {F1 ();}

As far as recursion is concerned, the most important thing is to jump out of the structure, because only by jumping out of the structure can there be results.

1.3 the so-called recursion is the thought of regression.

A recursive call, write a recursive function, and eventually convert to your own function.

Add a function f, if it is a recursive function, that is to say, the problem in the function is still transformed into the form of f.

The idea of recursion is to transform a problem into a solved problem.

Example: 1, 2, 3, 4, 4, 1, 2, 3, 4, 4, 1, 5, 5, 4, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 100, the result of accumulation

First of all, let's assume that the recursive function has been written, and let's say foo, that is, foo (100) is the sum of 1 to 100.

Looking for a recursive relation, that is, the relationship between n and Nmuri 1, or Nmai 2: foo (n) = n + foo (nMul 1)

Var res = foo; var res = foo (99) + 100

Convert the recursive result to a recursive body

Function foo (n) {return n + foo (n-1);}

Convert 100 to 99

Convert 99 to 98

...

Convert from 2 to 1

Find 1 and the result is 1.

That is, foo (1) is 1

Add the critical condition to the recursive body

Function foo (n) {return (n = 1) return 1; return n + foo (n-1);}

2. Examples of recursive evaluation

2.1 arithmetic sequence 1

Series: find 1, 3, 5, 7, 9. The result of item n is the sum of the previous term n. The serial number starts with 0.

Find the value of item n

First of all, let's assume that the recursive function has been written, and let's say fn. Then the nth item is fn (n)

Find the recurrence relation: fn (n) = = f (n-1) + 2

Recursive body

Function fn (n) {return fn (nmur1) + 2;}

Find the critical condition

Find n-> n Mel 1

Find nMub 1-> nMel 2

...

Find 1-> 0

Item 0 is 1.

Add critical condition

Function fn (n) {if (n = 0) return 1; return fn (nmur1) + 2;}

The sum of the first N terms

Assuming it is completed, sum (n) is the sum of the first n terms.

Find the recursive relation: the sum of the first n terms is equal to the sum of the n terms + the previous nmur1 terms

Get a recursive body

Function sum (n) {return fn (n) + sum (n-1);}

Find the critical condition

N = 1 the result is 1

Get the recursive function

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

2.2 arithmetic sequence 2

Series: 2, 4, 6, 8, 10 n and the first n sum

Item n

Function fn (n) {if (n = 0) return 2; return fn (nmur1) + 2;}

Sum of first n terms

Function sum (n) {if (n = 0) return 2; return sum (n-1) + fn (n);}

2.3 difference score column

Series: 1, 1, 2, 4, 7, 11, 16, … Find the nth item and the sum of the first n terms.

Find item n, starting with 0

Assuming that the result fn has been obtained, fn (10) is item 10

Find a recursive relation

Item 0 and item 1, the difference is 0 = > fn (0) + 0 = fn (1)

Item 1 and item 2, difference 1 = > fn (1) + 1 = fn (2)

Item 2 and item 3, difference 2 = > fn (1) + 2 = fn (2)

...

Item nmur1 and item n, the difference between item nmur1 = > fn (nMel 1) + nMel 1 = fn (n)

The recursive body is also clear, and the critical condition is n = 0 = > 1.

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

If it starts with 1, then item n is

Assuming that the result fn has been obtained, fn (10) is item 10

Find a recursive relation

Item 1 and item 2, difference 0 = > fn (1) + 0 = fn (2)

Item 2 and item 3, difference 1 = > fn (2) + 1 = fn (3)

Item 3 and item 4, difference 2 = > fn (3) + 2 = fn (4)

...

Item n Mel 1 and item n, the difference between item n Mel 1 = > fn (n Mel 1) + n-2 = fn (n)

Critical condition n = 1 = > 1

Sum of first n terms

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

2.4 Fibonacci series

This is one of the most common interview questions. Fibonacci numbers are listed as: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Ask for item n

The recursive relation fn (n) = = fn (n-1) + fn (n-2), so the recursive function is

Function fib (n) {if (n = 0 | | n = = 1) return 1; return fib (n-1) + fib (n-2);}

3. Advanced recursion

3.1 factorial

Calculating factorial is a classic example of recursive programming. Factorial is an operation, and to calculate the factorial of a number is to use that number to multiply all numbers smaller than it, including 1. For example, factorial (5) is equivalent to 5, 4, 3, 2, 1, and factorial (3) is equivalent to 3, 3, 2, 1.

five! It's 1 * 2 * 3 * 4 * 5. The factorial of 0 is 1, and the factorial starts at 1.

Find the factorial of n

Function foo (n) {if (n = 1) return 1; return foo (n-1) * n;} console.log (foo (5)); / / 120

It is very similar to the recursive function of summation from 1 to 100, but it is just a variant.

3.2 exponentiation

To find power is to find the power of a certain number.

2 to the square of 22, 2 to the power of 2

Find the m power of n

Finally, we will get a function power (n, m)

The m power of n is the multiplication of m ns, that is, n times (mmur1) n multiplies.

Function power (n, m) {if (m = 1) return n; return power (n, m-1) * n;} console.log (power (2m 3)); / / 8

4. Recursive deep copy

If you want to achieve a deep copy, then you need to consider comparing the properties of the object with the properties of the attribute. Copy it all over.

4.1 simple implementation

If you want to achieve:

Assuming that you have implemented clone (o1reo2), give a copy of the members of object O2 to o1

A simple algorithm to copy the attributes of O2 into o1

Function clone (o1meno2) {for (var k in o2) {o1 [k] = O2 [k];}}

Find a recursive relation, or reduce it to a solved problem

Assuming that the method has been implemented, ask if O2 [k] is an object

Continue to use this method

So what you need to consider is O2 [k] if it's a reference type, use the clone () function again

If O2 [k] is not a reference type, then assign the value directly

Function clone (o1, O2) {for (var k in O2) {if (typeof o2 [k] = 'object') {o1 [k] = {}; clone (o1 [k], O2 [k]);} else {o1 [k] = O2 [k] } var person1 = {name: 'Zhang San', children: [{name: 'Zhang Yi'}, {name: 'Zhang er'}, {name: 'Wang San'}]}; var person2 = {}; clone (person2, person1)

4.2 complex implementation clone (o)-> newObj

Function clone (o) {var temp = {}; for (var k in o) {if (typeof o [k] = = 'object') {temp [k] = clone (o [k]);} else {temp [k] = o [k];}} return temp } var person1 = {name: 'Zhang San', children: [{name: 'Zhang Yi'}, {name: 'Zhang er'}, {name: 'Wang San'}]}; var person2 = clone (person1); / / modify one to see if the other also modifies person2.name ='Li Si'; person2.children [0]. Name = 'Wang Xiaohu' Person2.children [1]. Name = 'Zhang Dahu'; person2.children [2]. Name ='Li Changhu'

4.3.Recursive implementation of getElementsByClassName method

It has the following DIV structure:

1 2 3 4 5 6 7 8

If you implement a method byClass (node, 'centering, list), it means to find an element on a node that conforms to the class attribute c

Look in the child elements of the current element, and if there is anything that meets the requirements, store it in an earlier array

First of all, traverse the child nodes, and then see whether the child nodes have any child nodes, if there is no direct judgment, if there is recursion.

Function byClass (node, className, list) {var nodes = node.childNodes; for (var iS0; I 0) {byClass (nodes [I], className, list);} var arr = []; byClass (document.body, 'centering, arr); console.log (arr); "JavaScript Recursion and sequence of knowledge explanation" content is introduced here, thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.