Recursive understand

Recursion is essentially “recursion” and “return”

Recursion: Finds the termination condition

“Return” : returns to the previous level according to the given expression

We don’t need to know exactly how the machine works, just whether the problem we’re trying to solve can be recursed and how

Recursion needs to satisfy three conditions

  1. You can break it down into multiple subproblems
  2. The subproblems of disassembly are solved in the same way
  3. There are recursive termination conditions

How do I write recursion

  1. Write the recursive formula
  2. Find the termination condition (initial value)

The key to writing recursive code is that whenever we encounter recursion, we abstract it into a recursive formula, instead of thinking about layers of calls and trying to break down each step of the recursion with our brains.

Recursive code is wary of stack overflows

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

Solution: if the recursive call goes beyond a certain depth, we do not recurse further and return an error.

Be wary of double counting in recursive code

Solution: Store the solved f(k) in a data structure (such as a hash table)

Rewrite recursive code to non-recursive code

Pros and cons of recursion

  • The upside: It looks simple and easy to understand
  • Disadvantages: High space complexity and stack overflow risk

Change to a non-recursive method

Recursion is digging up and down to the bottom, then working the other way up and back up. Iteration is basically starting at the bottom and working your way up. The essence is the same. Iteration can change recursion to non-recursion but does not address the shortcomings of recursion, which increases implementation complexity.

Leetcode topic

[70. Take the stairs]

The title

Suppose you’re climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top?

Note: given n is a positive integer.

Thinking a

  1. Determine if recursion is available
    • Can be broken down into multiple subproblems ✅ — n can be broken down into multiple and solved separately in several ways
    • Disassembly subproblems are solved in the same way ✅ – add one or two at a time
    • There are recursive termination conditions ✅ — n=1 or n=2
  2. Using a recursive

    • Write the recursive formula

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

    • Find the termination condition — n=1 or n=2

A code

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

But!!!!!! N =44 when submitting leetCode.

[206. Reverse linked list]

The title

Reverse a single linked list.

Train of thought

  1. Determine if recursion is available
    • It can be broken down into multiple sub-problems ✅ – each node’s next points to its previous node
    • The solution of the subproblem of disassembly is consistent ✅
    • There is a recursive termination condition ✅ – next for the node is empty
  2. Using a recursive
    • Write the recursion formula — head->next->next = head;
    • Find the termination condition – next of the node is empty

code

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL || head->next == NULL) return head;
    struct ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;// Avoid forming loops
    return newHead;
}
Copy the code