Chuancey, feel very good thinking, integration of learning

Conclusion 1: Basically,All recursive problems can be expressed by recursive formulas. With this recursive formula, we can easily change it to recursive code.. So, don’t be afraid of recursion. Think firstThe recursive formula.

Example 1: (More obvious recursion formula problem)

Question: Recursive formula for the NTH term of the Fibonacci sequence:

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

Among them, f (0) = 0, f (1) = 1

If (n <= 2) return 1;

Recursive code:int f(int n) {
  if (n <= 2) return 1;
  return f(n-1) + f(n-2);
}
Copy the code
Example 2:(less obvious problem with recursion formula)

Problem: Printing an array in reverse order

Recursive formula:

Suppose F(n)= is traversed in reverse order through an array of length n

So F(n)= print the element with subscript n in the array + F(n-1)

Termination Conditions:

if (n <0) return ;

Recursive code:public void Print(int[] nums,int n){
    if(n<0) return;
    System.out.println(nums[n]);
    Print(nums,n-1);
}
Copy the code

At this point, I don’t know if you know anything about writing recursions. You can’t write a recursion and try to lay out the recursion, so you’re going to loop in your head, layer by layer, layer by layer, and then layer by layer, trying to figure out how the computer is doing each step, so it’s easy to get caught up in it. When it comes to recursive code, trying to figure out the whole recursive process is a mental fallacy. Once we find the recursive formula, we can easily write recursive code.

Tree traversal problem

Problem: sequential traversal of binary trees

Recursive formula:

Let F(Root) be the problem: traverse the binary tree with Root as the Root node

Let F(root.left) be the problem: traverse the binary tree with F(root.left) as the Root node

Let F(root. right) be the problem: Traverse the binary tree with F(root. right) as the Root node

Then the recursion formula is:

F(Root)= traversal of Root node +F(root.left)+F(root.right)

Recursive code:public void preOrder(TreeNode node){
    if(node==null) return;
    System.out.println(node.val);
    preOrder(node.left);
    preOrder(node.righr);
}
Copy the code

Conclusion two.Recursion is a formal description of a repetitive action that performs a repetitive function. Specifically, if A problem A can be decomposed into subproblems B, C, and D,You can assume that subproblems B, C and D have been solved, and then think about how to solve problem A. Furthermore, you only need to think about the relationship between problem A and subproblems B, C, and D, rather than thinking about the relationship between subproblems and subproblems and subproblems (that is, recursion can only consider the relationship between the current level and the next level, not further down). We need to block out the recursive details and understand it as a formal description of what has been done.

All right, so let’s analyze this.

Problem: inversion of one-way linked lists

Recursive formula:

Let F(node) be the problem: reverse the one-way list with node as the head node;

In general, we need to think about the relationship between F(n) and F(n-1),

So here, if n represents a one-way list headed by Node, then n-1 represents a one-way list headed by Node.next.

So, we make F(Node.next) a problem: reverse the one-way list with Node.next as the head node;

So, what is the relationship between F(node) and F(Node.next)? Let’s draw a simple picture here. Suppose we reverse a linked list of three nodes:

1 -> 2 -> 3

So, F (node = 1) = F (node = 2) +?

Here we assume that the subproblem F(node=2) has been solved, so how do we solve F(node=1) :

Obviously, we need to reverse node=2 and node=1, i.e. Node.next-next =node; At the same time node. Next = null;

So, the problem can be: F(node=1)=F(node=2)+ reverse node=2 and node=1

Recursive code: public ListNode reverseList (ListNode head) {if (head = = null | | head. The next = = null) {/ / termination condition is not difficult to want to return the head; } ListNode node = reverseList(head.next); head.next.next = head; head.next = null; return node; // If F(node=1) and F(node=2) have the same head node}