Understanding recursion in action (I)

1 What is recursion

Simply put, the function calls itself:

function f() {
  f();
}
f();

Copy the code

The Maximum Call Stack size exceeded the Maximum call stack size exceeded.

What is a correct recursion

The above execution error, so the above statement is not strict, does not burst the stack function call itself, may be correct recursion

How to do not burst the stack? Function calls are a process of pushing on and off the stack, so keep the number of pushes on the stack within a certain range.

Such as:

function f(x) {
  // Add a constraint when x is reduced
  if(x == 0) return
  f(x-1);
}
f();


//or 

function f(x) {
 // If x is increasing, add a constraint
  if(x > 10) return 
  f(x+1);
}
f();

Copy the code

As we can see from the above example, adding a constraint, or the function continues to execute, prevents the stack from bursting. This is also called increasing the recursive exit

Now you can think of it as a function that has a recursive exit that calls itself recursively, but it just adds variables, it doesn’t make any sense, you have to do something inside the function.

How do you write recursion by taking n factorial

When writing recursions, consider three things:

To repeat: The factorial of n times n-1 can be decomposed into the factorial of n-1 times n-1-1 when n is n-1, which can be further abstracted into n times f(n-1), which is a recursive function, which is a repetition of the problem, and because it’s smaller, it’s called a subproblem, Imagine being lazy. I’m going to assume that everything else is done, and I’m just going to deal with the current level.
Find variation: the amount of variation should be used as a parameter, should it be one or more, and when to use more than one parameter? When you have one variable and you can’t go any further, when you have one parameter, and you increase or decrease one parameter, you decrease n by one
Find boundaries: this is the case above in preventing stackOverflow, which is to increase the end condition of recursion, namely recursive exit

So after the above analysis, the general framework for writing a recursion is as follows:

//1 defines function n as the found change
// The difficulty here is, how do I know what it is? We defined f of n as the factorial of n, so f of n minus 1 is the factorial of f of n minus 1, regardless of how you did it, how you defined it that's what it does.
function f(n) {
  //3 Define recursive exit to prevent stack burst
  if (n == 1) return 1;
  //2 Find the subproblem recursively
  return n * f(n - 1);
}

let n = 5;
console.log(f(n)); / / 120

Copy the code

Let’s look at another practical example: find the direct sum from I to j (I <j).

How do I convert loops to recursive writing?

Find the direct sum from I to j (I <j)

Circular writing:

const sum = (i, j, res = 0) = > {
  for (let k = i; k <= j; k++) {
    res += k;
  }
  return res;
};
console.log(sum(1.100));  / / 55
Copy the code

Change to recursion: The general framework of the above recursive solution is:

1. See if repetition can be found first. You can add the current value to the sum of 2 and then look for the change and stop recursing every time you add 1, 3 to the exit I >j

SumRecursive (I +1) determines the value after the current value
// I +1 is change
If (I >j) return 0 if(I >j) return 0 if(I >j) return 0 if(I >j) return 0
const sumRecursive = (i, j) = > {
  if (i > j) return 0;
  return i + sumRecursive(i + 1, j);
};

console.log(sumRecursive(1.10));/ / 55


// if I 
const sumRecursive = (i, j) = > {
  if (j < i) return 0;
  return j + sumRecursive(i, j - 1);
};

console.log(sumRecursive(1.10)); / / 55

Copy the code

5 Array Summation

let arr = [1.2.3.4.5.6.7.8.9.10];

// Array high-order function iteration implementation
const sum = arr= > arr.reduce((cur, next) = > cur + next, 0);
// console.log(sum(arr)); / / 55

// Recursive implementation
const sumRecursive = (arr, i = 0) = > {
  //1 find repeated sum
  //2 to find the change in the index of the change, so we need to think of adding parameters, without parameters can not be implemented
  //3 Recursive exit
  // if (i == arr.length) return 0;
  if (i == arr.length - 1) return arr[i];
  // Repeat is the value of the current item + the value of other items (recursive implementation)
  return arr[i] + sumRecursive(arr, i + 1);
};

console.log(sumRecursive(arr)); / / 55

Copy the code

6 Flipping strings

The subscript decreases gradually from the length of the string until it reaches zero. Because if you flip the string, this is the recursive exit of the change sum to zero, and the repetition is the subproblem of taking the character of the current subscript and adding it to the others.

let str = "hello";

// The subscript decreases from the length of the string until it reaches zero. Because we're flipping strings
const reverseStr = (str, i = str.length) = > {
  // Change the subscript, the subscript can change from the end, so we need to add arguments here
  // Exits with subscripts less than 0 are no longer processed
  // Repeat is the next item in the current item + recursive subproblem
  if (i == 0) {
    return str.charAt(i) + "";
  }
  return str.charAt(i) + reverseStr(str, i - 1);
};

console.log(reverseStr(str)); //olleh
Copy the code

Implementation without charAt:

let str = "hello";

const reverseStr = (str, i = str.length - 1) = > {
  if (i == 0) return str[i];
  return str[i] + reverseStr(str, i - 1);
};
console.log(reverseStr(str)); //olleh
Copy the code

Fibonacci series

/ / recursion
const fib = n= > {
  console.count();
  if (n <= 1) return 1;
  return fib(n - 1) + fib(n - 2);
};
// 1 1 2 3 5 8 13
// Subproblems can be divided into current value + small size subproblems
// Can also be divided into small subproblems such as FIB
// n = 1 || n =2 2
// n>2 f(n) = f(n-1) + f(n-2)
fib(5);

//recursive with cache //recursive with cache
const fibonacci = (n, memo = {}) = > {
  console.count();
  //has cache return it
  if (memo[n]) return memo[n];
  if (n <= 1) return 1;
  return (memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo));
};

// fibonacci(8);
/ / iteration
function fibonacciIter(num) {
  var a = 1,
    b = 0,
    temp;

  while (num >= 0) {
    temp = a;
    a = a + b;
    b = temp;
    num--;
  }

  return b;
}

fibonacciIter(5);

// The general formula
let fib09 = n= >
  Math.round(
    (Math.pow((1 + Math.sqrt(5)) / 2, n) -
      Math.pow((1 - Math.sqrt(5)) / 2, n)) /
      Math.sqrt(5));//js is strictly tail-recursive
("use strict");
function fibonacci10(n, n1, n2) {
  if (n <= 1) {
    return n2;
  }
  return fibonacci(n - 1, n2, n1 + n2);
}
// select * from table
const fib11 = n= > {
  let table = [
    0.1.1.2.3.5.8.13.21.34.55.89.144.233.377.610.987.1597.2584.4181.6765.10946.17711.28657.46368.75025.121393.196418.317811.514229.832040
  ];
  return table[n] || "Current data is too large to find in table!";
};
// Matrix multiplication is too complex to write

Copy the code

8 Greatest common divisor

Toss and turn and divide

// subproblem f(m,n) = f(n, m%n)
// recursive exit n= 0
const gdc = (m, n) = > {
  if (n == 0) return n;
  return gdc(n, m % n);
};

Copy the code

9 Hanoi


const hano = (n, from, to, help) = > {
  if (n == 1) {
    console.log(`move ${n} from The ${from} to ${to}`);
    return;
  } else {
    hano(n - 1.from, help, to); // Add the first n-1 disk to the auxiliary disk
    console.log(`move ${n} from The ${from} to ${to}`);
    hano(n - 1, help, to, from); // Let n-1 go from the secondary disk to the destination disk using the source disk}}; hano(3."A"."B"."C");
/ / step 7
// move 1 from A to B
// move 2 from A to C
// move 1 from B to C
// move 3 from A to B
// move 1 from C to A
// move 2 from C to B
// move 1 from A to B
Copy the code