“Little knowledge, big challenge! This article is participating in the creative challenge of “Essentials for Programmers”.
Learn some summaries of recursion
1 What is recursion
Recursion, in mathematics and computer science, is the method of using the function itself in the definition of a function. In other words, a recursive algorithm is an algorithm that calls its own function or method directly or indirectly. In layman’s terms, the essence of recursive algorithms is to decompose a problem into smaller sub-problems of the same kind, and then recursively call methods to represent the solution of the problem.
The basic principle of recursion
- Each level of function call has its own variable.
- There is a return for every function call.
- In a recursive function, the statement preceding the recursive call has the same execution order as the level of the function being called.
- In a recursive function, the order in which the statements following a recursive call are executed is reversed from the order in which each function is called.
- Although each level of recursion has its own variable, the function code is not copied.
Pros and cons of recursion
3.1 the advantages
- Implement a simple
- Read well
3.2 disadvantages
- Recursive call, take up a lot of space
- The recursion is too deep, prone to stack overflow
- There may be double counting
The three elements of recursion
4.1 What does your function want to do
No matter what the code inside the function, but to understand first, what is the function of your function, to accomplish what kind of a thing. For example, I define a function that looks like this
func jieshen(n int) int{ // How to calculate the factorial } Copy the code
4.2 Finding recursive end conditions
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. We need to figure out when the argument is what, the recursion ends, and then we 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.
func jieshen(n int) int { if n<=2 { return n } // General method of f(n) } Copy the code
4.3 Find out the equivalent relation of the function
We’re going to keep narrowing down the range of parameters, and when we do that, we can use some auxiliary variables or operations to keep the result of the original function unchanged. This is the hardest part of finding this equivalence relation, and if you don’t know it, it doesn’t matter, because you’re not a genius, you need to learn a few more problems. The final result of the factorial above is coded as follows
func jieshen(n int) int { if n <= 2 { return n } return n * jieshen(n- 1)}Copy the code
Common recursion exercises
A frog can jump up one step or two at a time. Find out how many ways the frog can jump up n steps. Step by step analysis according to the three elements is as follows
5.1 Functions of the first recursive function
func f(n int) int{}Copy the code5.2 Find the end condition of recursion
To find the condition that this recursion ends, 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:
func f(n int) int {
if n==1 {
return 1}}Copy the code5.3 Find out the equivalence relation of functions
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:
func f(n int) int {
if n==1 {
return 1
}
return f(n- 1)+f(n2 -)}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:
func f(n int) int {
//f(0) = 0,f(1) = 1, equivalent to f(n) = n when n<=2.
if n<=2 {
return n
}
return f(n- 1)+f(n2 -)}Copy the code5.4 thinking
Some 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.