Recursion needs to satisfy three conditions

  • The solution of a problem can be broken down into several subproblems
  • The problem itself is the same as the sub-problem except the data scale
  • There are recursive termination conditions

Tips for writing recursive code

The key to writing recursive code is to figure out how to break a big problem into smaller problems, write a recursive formula based on that, then refine the termination conditions, and finally translate the recursive formula and termination conditions into code.

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

If A problem A can be decomposed into several sub-problems B, C and D, we can assume that the sub-problems B, C and D have been solved, and think about how to solve the problem A on this basis. What’s more, we only need to think about the relationship between problem A and sub-problem B, C and D, instead of thinking about the relationship between sub-problem and sub-problem and sub-problem and sub-problem and sub-problem. Block out recursive details.

The key to writing recursive code is to abstract a recursion whenever you encounter it as a recursive formula, instead of thinking about layers of calls and trying to break down each step of the recursion with your brain.

Considerations for writing recursive code

Beware of stack overflow

The function call uses a stack to hold temporary variables. Each time a function is called, the temporary variable is encapsulated as a stack frame and pushed onto the memory stack. When the function returns after execution, the stack is removed. System stack or virtual machine stack space is generally not large. If the data size of the recursive solution is very large, the call level is very deep, and the stack is pushed all the time, there will be the risk of stack overflow. Recursion is not suitable for deep calls.

Beware of double counting

  • To optimize the
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 (hasSolvedList.containsKey(n)) {
    return hasSolvedList.get(n);
  }
  
  int ret = f(n- 1) + f(n2 -);
  hasSolvedList.put(n, ret);
  return ret;
}
Copy the code

Rewrite recursive code to non-recursive code

Recursion has both advantages and disadvantages. The advantage is that recursive code is very expressive and very simple to write. The disadvantages are high space complexity, the risk of stack overflow, the existence of double calculation, too many function calls will be time-consuming and other problems.

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

In general, all recursive code can be changed to non-recursive writing of this iteration loop. The key to non-recursive transformation is to abstract the recursive formula, initial values, and boundary conditions, and then implement them in an iterative loop.

Recursive debugging methods

  1. Print log found recursive values.
  2. Debug with conditional breakpoints.

source

Time.geekbang.org/column/arti…