For beginners in programming, recursion is often a stumbling block. At first glance, it's like viewing flowers through a fog, and even upon second glance, it remains unclear. Today, I will use a visual approach to break down and thoroughly explain recursion, helping you fully grasp its essence.
In one sentence: recursion is when a function calls itself. Since in the real world, a person cannot lift themselves up, it's initially difficult to understand the concept of calling itself. So, let's remove this concept and focus solely on the idea of function calls.
When introducing recursion, the most common example is calculating the nth value in the Fibonacci sequence. The characteristics of this sequence are that the zeroth value (in coding, we usually start from zero) is fixed at 0, the first value is fixed at 1, and starting from the second term, each term's value is the sum of the two preceding terms.
A simple code implementation looks like this:
When we call fibonacci(0), since 0 <= 1, the function directly returns 0.
When we call fibonacci(1), since 1 <= 1, the function directly returns 1.
Thus, we obtain the values of the first two terms.
However, when we call fibonacci(2), things start to get a bit different. Since 2 > 1, the if condition is skipped, and we reach the dreaded recursive line, which not only contains one recursion but two!
No worries, we can simply remove them, like this:
I imagine some students might be completely baffled by this code:
Don't worry, let me explain what's happening. First, look at the bottom function, still named fibonacci. The difference is that the line that previously called itself twice has been replaced with calls to two other functions, fibonacci1 and fibonacci2. These two new functions are identical to the original fibonacci function; I simply copied the original function with ctrl + c, ctrl + v, and renamed them.
After this modification, we find that the recursion in the fibonacci function has disappeared. It no longer calls itself but calls other functions, which happen to have the exact same functionality as itself. >_<
If you run this modified version, you'll find that it functions exactly the same as the original recursive version and correctly calculates the desired values.
Sharp-eyed students might immediately notice that while fibonacci no longer contains code that calls itself, fibonacci1 and fibonacci2 still do. The recursion hasn't been entirely removed. Yes, that's true, but it's okay because when we call fibonacci(2), you'll see that during execution, the lines inside fibonacci1 and fibonacci2 that call themselves are never actually executed. They are there but never truly participate.
Let's go step by step to see what exactly happens:
Step 1:
Call fibonacci(2)
Step 2:
Enter the fibonacci function, where n = 2
Step 3:
Start the if judgment. Since 2 <= 1 is false, skip the if.
Step 4:
Execute the line fibonacci1(n - 1) + fibonacci2(n - 2). First, execute the left side of the plus sign, i.e., call fibonacci1(n - 1). Here, n = 2, so we're actually calling fibonacci1(1).
But don't forget, there's still code on the right side of the plus sign. After we finish calling fibonacci1(1), we'll return here to call fibonacci2(n - 2). Since n = 2, we'll actually call fibonacci2(0). Yes, no matter what happens inside fibonacci1, it won't affect the value of n. On this line, here, when calling fibonacci1, n = 2, and when calling fibonacci2, n is still 2.
Step 5:
Enter the fibonacci1 function, where n = 1
Step 6:
Start the if judgment. Since 1 <= 1 is true, enter the if and directly return the value of n, which is 1.
Step 7:
Since fibonacci1 has finished executing, proceed to execute the right side of the plus sign, i.e., fibonacci2(n - 2). Remember, we're back here, and n = 2, so we're actually calling fibonacci2(0).
Step 8:
Enter fibonacci2, where n = 0
Step 9:
Start the if judgment. Since 0 <= 1 is true, enter the if and directly return the value of n, which is 0.
Step 10:
We're back to the starting point, inside the fibonacci function. Now, both functions on the left and right sides of the plus sign have been executed. The left side's result is 1, and the right side's result is 0. Therefore, we perform the addition.
According to advanced mathematics, we calculate:
0 + 1 = 1
So, the result of this step is 1, meaning the fibonacci function ultimately returns 1.
Finally, we assign the returned result to result.
At this point, we've completed the calculation of fibonacci(2) and obtained the desired result, all without using recursion.
So, what is recursion? Let's return to the concept of recursion and restore the code to its original form:
Then, let's execute it again and see the final result:
Look closely, look closely.
We find that, apart from the function names, the original version and our modified non-recursive version are identical in every way. Their calling methods, the values of n inside the functions, and their returned results are all the same.
Think carefully, think carefully.
Have you realized that recursion is simply calling a function, but it just so happens that the function it calls is itself? We can imagine it as calling another function that has the exact same functionality as itself, and this function happens to have the same name.
Termination Condition
Due to the peculiarity of calling itself, you can imagine a cat chasing its own tail. Therefore, compared to functions that don't call themselves, we need to pay special attention to one thing when using recursion: the termination condition.
Just as a cat chasing its tail will eventually stop—perhaps because it's tired or distracted by a more interesting ball of yarn—without these, the cat might chase its tail forever.
When using recursion, it's especially important to focus on the termination condition; otherwise, the calls will continue indefinitely, eventually leading to a stack overflow.
Taking the fibonacci function as an example, we can see that where it calls itself, the parameters are n - 1 and n - 2, both of which are smaller than n. In the if condition, our judgment is if (n <= 1). Therefore, as the calls continue, n will get smaller and smaller, and eventually, n will be less than or equal to 1. At this point, we enter the if block, where we no longer call itself, and the infinite process is terminated.
I hope this helps!
Top comments (0)