Probably a lot of you have recursion in your first year of college, but I’m sure a lot of you, when you first get recursion, you don’t know what to do, and I did, and I was like, recursion is amazing!
There are probably a lot of people who know recursion, who understand recursion, but don’t know how to use recursion in practice, and sometimes get confused by recursion. I’ve had a few people ask me if THERE’s a quick way to learn recursion. To be honest, there are not so many shortcuts. However, I would like to write an article about my experience, which may be of some help to you.
For the sake of beginners, I will start with the simplest problem!
The three elements of recursion
The first element: figure out what your function wants to do
One of the things that I think is really important about recursion is what the function does, what it’s trying to accomplish, and that’s completely up to you to define. In other words, we don’t care what the code in the function is, but we need to understand what the function is for.
For example, I define a function
Int f(int n){}Copy the codeThis function is going to take n factorial. Ok, now that we’ve defined a function and defined what it does, let’s look at the second element.
Second element: find the recursive end condition
Recursion is calling the function itself from inside the function code, so we have to figure out the end condition of the recursion, otherwise we’ll just keep calling ourselves into a bottomless pit. In other words, we need to figure out what the recursion ends when the argument is, and then we need to return the result directly. Note that at this point we need to be able to directly know what the result of the function is, based on the value of the argument.
For example, in the example above, when n is equal to 1, then you should know what f of n is, right? So f of 1 is equal to 1. To improve the code inside our function, add a second element to the code as follows
Int f(int n){if(n == 1){return 1; }}Copy the codeOne might say, well, when n is equal to 2, then we can immediately know what f of n is equal to, so can I use n equals 2 as my end condition for recursion?
Of course, as long as you know the result of the function directly when you think the argument is what it is, then you can use that argument as a closing condition, so the following code is also ok.
Int f(int n){if(n == 2){return 2; }}Copy the codeNotice the comments I wrote in the code, assuming n >= 2, because if n = 1, it will be missed, and f(n) = n when n <= 2, so to be more precise, we can write it like this:
Int f(int n){if(n <= 2){return n; }}Copy the codeThe third element: find the equivalent relation of the function
The third element is that we need to keep narrowing down the range of parameters, and after narrowing down, we can use some auxiliary variables or operations to keep the result of the original function unchanged.
For example, if f(n) is a big range, we can set f(n) = n times f(n-1). So now the range goes from n to n minus 1, the range gets smaller, and in order to keep the function f of n constant, we need f of n minus 1 times n.
To put it bluntly, we want to find an equivalence relation of the original function, and the equivalence relation of f(n) is n times f(n-1), that is
F of n is equal to n times f of n minus 1.
Finding this equivalence relation is arguably the most difficult step, and it doesn’t matter if you don’t understand it, because you are not a genius. You still need to learn more problems. I will find 10 recursion problems in the next article, so that you can gradually get familiar with them.
We figured out this equivalence, and we went on to refine our code, and we wrote this equivalence into the function. As follows:
Int f(int n){if(n <= 2){return n; } // return f(n-1) * n; }Copy the codeAt this point, all three elements of the recursion have been written into the code, so we’ve already written the internal code for the f(n) function.
Those are the three most important elements of recursion, and every time you do recursion, you force yourself to try to find those three elements.
Still don’t understand? It doesn’t matter. Let me do a couple more of the problems that follow this pattern.
Those of you who are a little bit basic might think I’m too easy to read, right? Keep reading, Shaoxia, and I’m going to show you how to optimize recursion. Of course, big guy please feel free, you can directly pull the bottom message to give me some suggestions, thank you!
Case 1: Fibonacci sequence
The Fibonacci sequence is a sequence like this: 1, 1, 2, 3, 5, 8, 13, 21, 34…. , that is, the first term f(1) = 1 and the second term f(2) = 1….. , the NTH item is f(n) = F (n-1) + f(n-2). What is the value of the NTH term.
1. The first recursive function
Suppose the function of f(n) is to evaluate the NTH term as follows:
int f(int n){
}Copy the code2. Find the conditions under which recursion ends
Obviously, when n is equal to 1 or n is equal to 2, we can easily tell that f of 1 is equal to f of 2 is equal to 1. So the end condition can be n <= 2. The code is as follows:
int f(int n){ if(n <= 2){ return 1; }}Copy the codeThe third element: find the equivalent relation of the function
They gave us the equivalence, so we can easily tell that f of n is equal to f of n minus 1 plus f of n minus 2. I said that the equivalence relation is the hardest one to find, and this problem gives us the equivalence relation, which is too easy. Well, I’m trying to appeal to the reader who has almost zero base.
So the final code looks like this:
Int f(int n){if(n <= 2){return 1; Return f(n-1) + f(n-2); }Copy the codeDone, isn’t that easy?
Zero foundation of the possibility or not quite understand, it doesn’t matter, after slowly in accordance with this mode of practice! Okay, some big shot might be teasing too easy.
Case 2: Young frog jumping step
A frog can jump up one step or two at a time. Find out how many ways the frog can jump up n steps.
1. The first recursive function
Suppose the function of f(n) is to find the total number of ways a frog can jump up an n step. The code is as follows:
int f(int n){
}Copy the code2. Find the conditions under which recursion ends
I said, to find the conditions for ending recursion, you just compress n down to very, very small, because the smaller n is, the easier it is to intuitively figure out what f of n is, so when n is 1, you know what f of 1 is, right? Is that intuitive? F of 1 is equal to 1. The code is as follows:
int f(int n){ if(n == 1){ return 1; }}Copy the codeThe third element: find the equivalent relation of the function
Each time he jumped, he could jump one step or two steps. That is to say, he could jump in two ways.
The first way to jump: The first time I jump a step, then there are n-1 steps left to jump, the remaining N-1 steps can jump f(n-1).
Second jump: the first jump of two steps, then there are n-2 steps left, the remaining N -2 steps can jump f(n-2).
So, the total jump of the frog is the sum of these two jumps, that is, f(n) = F (n-1) + F (n-2). So now we have the equivalence. Write the code:
int f(int n){
if(n == 1){
return 1;
}
ruturn f(n-1) + f(n-2);
}Copy the codeDo you think the above code is correct?
Well, that’s not quite true. When n is equal to 2, obviously f of 2 is equal to f of 1 plus f of 0. We know that f of 0 is equal to 0, so we don’t have to call it all the way down, but in our code logic, we’re going to keep calling f of 0 is equal to f of -1 plus f of -2. This leads to infinite calls and an infinite loop.
And that’s what I want to talk to you about, in terms of whether or not the end condition of recursion is rigorous enough, a lot of people, when they use recursion, because the end condition is not rigorous enough, they end up in an endless loop. That is to say, when we are at the end of the second step is to find a recursive conditions, can write the ending condition into the code, and then to the third step, but please note, when we step 3 to find equivalent function, still have to return to the second step, according to the third step function call relations, will appear a few missed the end of the conditions. Just like above, the call to f(n-2), it’s possible to get f(0), which will cause an infinite loop, so let’s fill it in. The code is as follows:
Int f (int n) {/ / f (0) = 0, f (1) = 1, equivalent to n < = 1, f (n) = n. if(n <= 1){ return n; } ruturn f(n-1) + f(n-2); }Copy the codeSome people might say, I don’t know if I missed my closing conditions. Don’t be afraid. Just practice a little and you’ll know what to do.
See here someone may want to ridicule, these two questions are too easy? Can’t be so perfunctory. Don’t go, Sonny. It’s gonna be a little harder.
The following is actually not difficult, just a little bit more difficult than the above problem, especially the third step equivalent search.
Case 3: Reverse singly linked lists.
Reverse a single linked list. For example, the linked list is 1->2->3->4. The reverse is 4->3->2->1
The nodes of the linked list are defined as follows:
class Node{
int date;
Node next;
}Copy the codeAlthough it is Java language, but even if you have not learned Java, I think it is not a big impact, can understand.
It’s the same old routine, three elements one at a time.
1. Define recursive function functions
Suppose the function reverseList(head) functions as an inverted but linked list, where head represents the head node of the list. The code is as follows:
Node reverseList(Node head){
}Copy the code2. Look for end conditions
If the list has only one node, or if it’s empty, you should know the result, right? I don’t have to do anything. I just return head. The code is as follows:
Node reverseList(Node head){ if(head == null || head.next == null){ return head; }}Copy the code3. Find equivalence relationships
The equivalence of this is not as easy to find as n is a number. But I’m telling you, one of the equivalence conditions is that the range is getting smaller and smaller, and in the case of a linked list, the number of nodes is getting smaller and smaller, so if you can’t figure it out, just go through the reverseList(head.next) recursively and see what it looks like. For example, the linked list nodes are as follows
Let’s narrow it down and try recursion 2->3->4
Node reverseList(Node head){ if(head == null || head.next == null){ return head; } // Let's save the result of the recursion and not return it, because we don't know if the recursion is right or wrong. , Node newList = reverseList(head.next); }Copy the codeIn the first step, we defined the function reverseLis t to reverse a single list, so the result of the 2->3->4 reverse should look like this:
We recurse 2->3->4 to 4->3->2. However, the node 1 is not touched, so the next node of 1 is still connected to the 2.
What’s next? What to do?
Next on node 2 points to 1, and next on node 1 points to null. The result of changing the newList is as follows:
In other words, reverseList(head) is equivalent to reverseList(head. Next)** + change the direction of the 1,2 nodes. Ok, the equivalence relation is found, the code is as follows (with detailed explanation) :
Public static Node reverseList2(Node head){// 1 The if condition of recursive end (head = = null | | head. The next = = null) {return head; } // Node newList = reverseList2(head.next); // change the direction of 1,2 nodes. Node t1 = head. Next; T1. Next = head; // next of 1 points to null.head. Next = null; // Return the adjusted list. return newList; }Copy the codeThe third part of this problem is confusing, right? Normal, because you do too little, may not have thought that can be so, more practice a few can. However, I hope that these three problems have given you some ideas for doing recursion problems in the future, so that you can follow my model when doing problems in the future. It is impossible to master recursion through an article, but also more practice, I believe that as long as you seriously look at my article, read a few times, will be able to find some ideas!!
I’ve emphasized that many times, practice a few more, so I will also find about 10 recursion exercises for you to learn, but I may find some difficulty. Not like today, more simple, so it, beginners have to find their own practice, believe me, master recursion, your thinking abstract ability will be stronger!
So let me talk about some optimizations for recursion.
Some optimization ideas about recursion
1. Consider whether to double count
I’ll tell you what, if you don’t optimize when you use recursion, there are very, very, very many subproblems that are double-counted.
What is a subproblem? f(n-1),f(n-2)…. It’s a subproblem of f(n).
For example, in case 2, f(n) = f(n-1) + f(n-2). The recursive call state diagram looks like this:
See, when we recursively calculated, we repeated f(5) twice, f(4) five times… And this is scary, because the bigger n is, the more we double count, so we have to optimize.
How to optimize? In general, we can guarantee the result of our calculation, for example, the result of f(4), and when we do the calculation of F (4) again, we check whether we have calculated it before, and if we have, we just take out the result of f(4), and if we haven’t, we recurse.
With what? We can store it in arrays or hashmaps, we store it in arrays, we use n as our array subscript, f(n) as the value, for example arr[n] = f(n). When f(n) has not been evaluated, we set arr[n] equal to a special value, such as arr[n] = -1.
When we decide, if arr[n] = -1, we prove that f(n) has not been evaluated, otherwise, f(n) has already been evaluated, and f(n) = arr[n]. I’m just going to take the value out. The code is as follows:
// Our implementation assumes that the ARR array is already initialized. int f(int n){ if(n <= 1){ return n; } // if(arr[n]! Return arr[n]; return arr[n]; }else{arr[n] = f(n-1) + f(n-1); reutrn arr[n]; }}Copy the codeIn other words, when using recursion, it is necessary to consider whether there is a double calculation, and if there is a double calculation, be sure to save the calculated state.
2. Consider whether you can work bottom-up
For recursion problems, we usually recurse from the top down until we get to the bottom, and then we return the value layer by layer.
However, sometimes when n is large, such as when n = 10000, you have to recurse down 10000 levels until n <=1 to slowly return the result. If n is too large, you may run out of stack space.
In this case, we can actually think about the bottom-up approach. For example, I know
f(1) = 1;
f(2) = 2;
So we can say that f of 3 is equal to f of 2 plus f of 1 is equal to 3. So you can derive f of 4,f of 5, all the way to f of n. Therefore, we can consider using a bottom-up approach instead of recursion, as follows:
public int f(int n) {
if(n <= 2)
return n;
int f1 = 1;
int f2 = 2;
int sum = 0;
for (int i = 3; i <= n; i++) {
sum = f1 + f2;
f1 = f2;
f2 = sum;
}
return sum;
}Copy the codeThis method, in fact, is called recursion.
The final summary
In fact, recursion doesn’t always go from top to bottom, there are a lot of recursions that go from bottom to top, such as n = 1, to n = 1000, such as sorting combinations. There are also optimization techniques for this kind of bottom-up, but I’m not going to write it, and I’ll write it later. This article has been written for a long time, the neck can not stand ，，，， cervical spondylosis? Be afraid of…
To tell you the truth, recursion is a relatively abstract idea, it is very difficult to explain him, especially to beginners, which is why I spent a long time on this article, but as long as you can read it and gain something, I think it is worth it! Some of you might think it’s a little bit easy, but I’ll do a couple of things that aren’t that easy. Finally, if you feel good, please forward or give me a thumbs-up!
Finally, promote my public number: helpless and painful code farmers: Stamp I can pay attention to, the article will be first in my public number, looking forward to the attention of all heroes exchange.