Loop/recursion

  • Loop: a block of code that executes n times, including while loops and for loops.

A for loop is usually used when a block of code executes a certain number of times, so it is also called an iteration. The conditions for breaking out of a while loop are often complex and not solely dependent on the number of times

  • Recursion: the function calls itself.

The key to both loops and recursion is exit. (Cyclic condition recursive exit)

Loop and recursive transformation

The difference between loop and recursion is not in the form of the code (loop is executing a block of code multiple times, recursion is executing itself multiple times, good mapping, loop and recursion can often be converted to each other). , but in a different mode of thinking.

  • Circular thinking mode to consider more, circular conditions, circular operations, the update of conditions
  • Recursive thinking is simple: consider a recursive exit and a recursive formula (a way to reduce the size of the problem) **

Use a simple example to illustrate the circular/recursive mindset difference.

Circular thinking and recursive thinking are often very different on the same problem. Recursive thinking is simpler, but more complex in time and space.

The following example is not a circular and recursive solution to an algorithm, but a circular and recursive implementation under the same mode of thinking.

Fibonacci

Title: we set F(n) = 1,1,2,3,5,8,13… A sequence such as F(n-1)+F(n-2) is called the Fibonacci sequence.

Circular thinking model

Analysis: add the first and second numbers to get the third; Add the second and third trees to get the fourth; Add up the third and fourth to get the fifth… Until you figure out the number.

Several key steps of the loop algorithm:

  1. Initialize the
  2. Determining cycle conditions
  3. Execute loop, (branch) modify condition/break loop
  4. Returns the result
  5. Checking boundary conditions

Implementation – Cyclic implementation

In this case, the correspondence is as follows:

  1. Initialization: the addend and the addend a and b are 1 and 1 respectively, and the result to be returned is C
  2. Loop condition: N -2 loops in total
  3. Execution loop: sum a and B to get C; Modify the loop condition: assign b to A and C to B
  4. Return result:
  5. Check the boundary case, n is 1 or 2
function fibonacci_circle(n) {
  if (n === 1 || n === 2) {
    return 1
  } else {
    let a = 1,
      b = 1,
      c
    let count = 0
    while (count < n - 2) {
     
      c = a + b
      a = b
      b = c
      count++
    }
    return c
  }
}
let result = fibonacci_circle(6)
console.log(result)
Copy the code

Implementation – Recursive implementation

  1. The code block involves an addend and an addend, so we need to make some changes to the parameters of the function: the function takes three arguments, the first and second arguments are the addend and the addend, and the third argument is the distance from the desired number to the first. Take the sum of a and b and you get C; Modify recursion conditions
function fibonacci_recursion(first, second, n) {
  // Perform the operation
  let a = first,
    b = second
  let c = first + second
  // Modify the condition
  a = second
  b = first + second
}
Copy the code
  1. Determine the recursive exit: return C when the third argument is 3 (the distance is only 3)
  2. Consider boundary conditions: the case where the third parameter is 1 or 2
function fibonacci_recursion(first, second, n) {
  // Perform the operation
  let a = first,
    b = second
  let c = first + second
  // Modify the condition
  a = second
  b = first + second
  if (n > 3) {
    return fibonacci_recursion(a, b, n - 1)}else if (n === 3) {
    return c
  } else if (n === 1 || n === 2) {
    return 1}}debugger
let result = fibonacci_recursion(1.1.6)
console.log(result)


Copy the code

(The form above, which returns the result of a recursive call directly, is called tail recursion.)

Recursive thinking model

The key steps of the recursive algorithm are simple:

  1. Identify recursive exits
  2. Determine the recursion formula
  3. Check the boundary

Implementation – recursive writing

  1. Recursive exit: n is either 1 or 2
  2. Recursive formula, each number is the sum of the first two numbers
function fibonacci_recursion(n) {
  if (n >= 3) {
    N-1 and n-2 update the recursion condition
    let result = fibonacci_recursion(n - 1) + fibonacci_recursion(n - 2)
    return result
  } else if (n === 1 || n === 2) {
    return 1}}debugger
let result = fibonacci_recursion(6)
console.log(result)
Copy the code

(This algorithm is called non-tail recursion.)

Complexity analysis

TODO: Write 8 after that, I’m a little bit confused

conclusion

Recursion Because of the simple thinking mode, many complex algorithms are often implemented based on recursion rather than pure loop.

When you write an algorithm, you first think about whether you can reduce the size of the problem, and if you can reduce the size, you extract a formula, you can use recursion.

Then whether it’s a loop or a recursion, it’s to determine what a block of code is going to do over and over again, what a single step is going to do.