recursive

I believe this is a common concept in mathematics, and it’s actually a common concept in programming. Recursion, in layman’s terms, is the process of solving a problem by constantly breaking it down, going back to the end and then working backwards.

Easy to interpret

Case one: I don’t know what row the movie is in

If you don’t know what row you are in, you can ask the people in the previous row to find out and add one. So this is what it looks like to solve the code recursively.

function fn = (n) {
    if(n< = 0) return 'Seat does not exist'
    if(n>1) {
    return fn(n-1)+1
    } else {
    return1}}Copy the code

Case two: how many ways to walk the grid

There are n squares, 1 or 2 squares per step. How many ways are there? First of all, the decomposition problem is that the NTH cell can go n-1 or n-2. So fn of n is equal to f of n minus 1 plus f of n minus 2. And you also know that the termination condition is only 1, so you could have only 1 left, you could have 2 left.

function fn = (n){
  if(n>2){
return fn(n-1) + fn(n-2)
} else if(n==2)   {
return2}else {
return1}}Copy the code

Key Points analysis

You can break it down into subproblems

That is, the logical disassembly of the returned recursive subproblem from the current problem

This problem is the same as the subproblem after decomposition, except for the data size

That is, the solution of the subproblem is exactly the same as the current problem, so there is no need to write it differently

Termination condition

No recursive judgment conditions are performed, and special values of critical conditions are known to be computable

The actual problem

Stack overflow

When the recursion level is too deep, because temporary variables are constantly encapsulated as stacks pushed into the memory stack during recursion, if pushed into the memory stack, it will overflow and cause the service to crash. The usual solution is to set a recursion depth to limit it. For example, the following code assumes a memory depth of 1000 and raises an exception if it exceeds 1000.

let depth = 0 
let f = (n) => {
++depth
if(depth>1000) throw error()
if(n===1) return 1
return fn(n-1) + 1 
}
Copy the code

Note: this is not very practical, because memory is generally dynamic change, with a fixed value does not make sense, and if the dynamic access to memory, and a storm in a teacup.

Double counting

In the case of recursive calculation of moves above, it is not difficult to find that some intermediate steps will be repeated, resulting in waste. Of course, this kind of problem doesn’t necessarily have to do with the decomposition of the problem.

The optimization method is to use the path meter directly in the Map cache for the results already obtained.

let  f  = ( n) => {
  if (n == 1) return 1;
  if (n == 2) return2; // hasSolvedList can be understood as a Map with key n and value F (n)if (hasSolvedList.containsKey(n)) {
    return hasSovledList.get(n);
  }
  ley ret = f(n-1) + f(n-2);
  hasSovledList.put(n, ret);
  return ret;
}
Copy the code

Infinite recursion

That is, there is no way to find the termination condition to take into account, mainly to avoid the effects of endless loops or dirty data

conclusion

This paper mainly introduces the common recursion cases, the core points that can be used for recursion and the possible problems of recursion.

Easter egg ~~ Magic coin challenge

Small easy is ready to go to the kingdom of Magic to purchase magic artifacts, the purchase of magic artifacts need to use magic coins, but small easy now have no magic coins, but small easy has two magic machines can produce more magic coins by putting X (X can be 0) magic coins. Magic Machine 1: If you put in X magic coins, the magic machine will change it into 2X +1 magic coins Small easy to purchase magic artifact a total of N magic coins, so small easy can only produce just n magic coins through two magic machines, small easy needs you to help him design an investment plan so that he finally just have N magic coins

If you are interested in the solution to this game, please jump to the link below to introduce the code and the truth.

  • Magic coins play recursively