❝

Pay attention to the public code elder byte, set the star to get the latest push. “Add group” into the technical exchange group for more technical growth.

❞

“Abstract: Recursion is a very widely used algorithm (or programming technique). Later we will talk about a lot of data structure and algorithm coding implementation will use recursion, such as DFS depth-first search, front, middle, rear order binary tree traversal and so on. So, it’s really important to understand recursion, otherwise you’re going to have to struggle with more complicated data structures and algorithms“

Recommend users to register and receive commission many people have encountered, many apps are this routine when promoting. Xiao He introduced Han Xin to join Liu Bang’s camp, and Han Xin in turn introduced han Bold, his older brother from the upper bunk, to join. We can conclude that the final recommender of “Han Bold” is “Xiao He”, that of “Han Xin” is “Xiao He”, and that of “Xiao He” has no final recommender.

Soldier_id represents the ID of the soldier and referrer_id represents the ID of the referee.

soldier_id reference_id
Han xin main
Han Dadan Han xin

So the question comes, “Given a soldier ID, how to find the” final recommender “of the user”, with this question, we officially enter recursion.

Recursive three elements

Two of the most difficult things to understand are “dynamic programming” and “recursion”.

University military training, will have experienced the queue number, number in the process of their own deserting saw a beautiful primary school elder sister, do not know next to the elder brothers just said the number, so ask the left elder brothers just reported how much, as long as he said the number + 1 to know their tree several, The key is that now the elder brothers next to you see beautiful primary school elder sister actually forgot the number just said by themselves, also want to continue to ask his left old iron, so straight forward to ask, until the first count of the child, and then layer upon layer to pass the number to themselves.

This is a very standard recursive solution, the process of asking is called “recursion”, and the process of returning is called “return”. Convert to a recursive formula:

F (n)=f(n-1) + 1, f(1) = 1

F (n) is his own number, f(n-1) is the number of the preceding person, and f(1) is the number of the first person who knows he is the first person to report.

According to the recursive formula, it is easy to convert to recursive code:

public int f(int n) {
  if (n == 1) return 1;
  return f(n-1) + 1;
}
Copy the code

What kind of problem can be solved recursively? Summarize the three necessary elements, as long as the following three conditions are satisfied, you can use recursion to solve.

“1. A problem can be decomposed into multiple sub-problems“

It is possible to factor smaller problems with constant numbers, such as the subproblem of “previous person’s exponent” to know your own exponent.

“2. The problem itself and the decomposed sub-problems have the same solving algorithm except for different data sizes“

“Solve your own count” and the previous person “solve your own count” is the same idea.

“3. Recursive termination conditions exist“

You can’t have an infinite loop as the problem is broken down into subproblems, so you need a stop condition, just like the first row or any of the kids who knows how to count doesn’t need to ask for the last person’s number, so f(1) = 1 is the recursive stop condition.

How do I write recursive code

The key is to “write the recursive formula, find the termination condition”, and then translate the recursive formula into code is much easier.

Suppose there are n steps and you can jump one or two steps at a time. How many ways can you take n steps?

If you think about it a bit more, in fact, all moves can be divided into two categories based on the first step, the first step takes 1 step, and the second step takes 2 steps. So n steps is the same thing as n minus 1 steps plus n minus 2 steps after 2 steps.

f(n) = f(n-1) + f(n-2)
Copy the code

So let’s go ahead and analyze the termination condition, and we don’t need to continue recursing when there’s only one step, f (1) = 1. Seems not enough. What if there were two steps? Verify with n= 2 and n=3 respectively. F (2) = 2 is also one of the termination conditions.

So the termination condition for this recursion is f(1) = 1,f(2) = 2.

f(1) = 1;
f(2) = 2;
f(n) = f(n-1) + f(n-2);
Copy the code

The formula to code is

public int f(n) {
  if(n == 1) return 1;
  if(n ==2) return 2;
  return f(n-1) + f(n-2);
}
Copy the code

“The key to writing recursion is to find out how to break down big problems into small ones, write recursion formulas based on this, and then derive termination conditions, and translate the ground deduction formula and termination conditions into code after renting.”

For recursive code, we should not try to figure out the whole recursion sum problem, which is not suitable for our normal thinking, our brain is more suitable for the thinking of flat, when seeing recursion do not attempt to spread out the recursive process, otherwise it will fall into a cycle of layer by layer downward.

“When A problem 1 can be decomposed into several 2,3, and 4 problems, we just assume that 2,3, and 4 have been solved and think about how to solve A on this basis. That makes it a lot easier.“

So when it comes to recursion, the key to writing code is to “abstract the problem into a recursive formula, not to think of layers of calls, and find termination conditions.”

Preventing stack overflow

The biggest problem with recursion is preventing stack overflows and endless loops. Why is recursion prone to stack overflows? Let’s recall the stack data structure we talked about earlier, and if you don’t know, you can refer to the historical article. A function call will use a stack to store temporary variables. Each time a function is called, the temporary variables will be wrapped into a stack frame and pushed into the corresponding stack of the thread. When the method ends and returns, the stack will be removed. If the data size of the recursion is large, the call level is deep and the stack is pushed all the time, and the stack size is usually not large enough to cause stack overflow.

Exception in thread "main" java.lang.StackOverflowError
Copy the code

How to prevent it?

We can only limit the maximum depth in the code, return an error directly, use a global variable to indicate the depth of the recursion, + 1 for each execution, and return an error directly if the specified threshold has not been reached.

Beware of double counting

If we want to compute f(5), we need to compute f(4) and f(3) first. If we want to compute F (4), we also need to compute F (3). Therefore, F (3) is computed many times. To avoid double-counting, we can use a data structure (such as a HashMap) to store the solved f(k). When I recursively call f(k), let’s see if I’ve solved it. If it is, it returns the value directly from the hash table without double-counting, thus avoiding the problem we just described.

public int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;

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

The spatial complexity of recursion is O(N), not O(1), because each call holds a temporary variable on the stack once.

How do I convert recursion into non-recursive code

Recursion has its pros and cons, recursion is very simple to write, but the downside is that space complexity is O(n), stack overflow risk, double computation. The choice of recursion depends on the situation.

Or military training queue counting example, how to become non-recursive.

f(n) = f(n-1) +1;

public int f(n) {
  int r = 1;
  for(int i = 2; i <= n; i++) {
    r += 1;
  }
 return r; } Copy the code

Step problem can also be changed to circular implementation.

public int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;

  int ret = 0;
 int pre = 2;  int prepre = 1;  for (int i = 3; i <= n; ++i) {  ret = pre + prepre;  prepre = pre;  pre = ret;  }  return ret; } Copy the code

Find the best references

Now that the recursion is over, how do we answer the opening question: find the best references based on the soldier ID?

public int findRootReferId(int soldierId) {
  Integer referId = "select reference_id from [table] where soldier_id = soldierId";
  if (referId == null) return soldierId;
  return findRootReferId(referId);
}
Copy the code

Recursion is a very efficient and concise coding technique. Any problem that meets the “three conditions” can be solved by recursive code.

But recursive code can also be difficult to write and understand. The key to writing recursive code is not to get wrapped up in it. The correct posture is to write recursive formulas, figure out termination conditions, and then translate them into recursive code.

Although recursive code is simple and efficient, it also has many disadvantages. For example, stack overflows, double computations, time-consuming function calls, and spatial complexity are important side effects to control when writing recursive code.

Brother code byte

Recommended reading

1. Cross data structures and algorithms

2. Time complexity and space complexity

3. Best, worst, average and amortized time complexity

4. Array of linear tables

5. Introduction to linked lists – Mind method

6. The correct implementation of unidirectional linked lists

7. Bidirectional linked lists are implemented correctly

8. Stack to realize browser forward and backward

9. Queue-production and consumption mode

❝

Original is not easy, feel useful hope with “watching” “collection” “forward” three.

❞

This article is formatted using MDNICE