Here’s a video if you need further explanation!
The Visual Explanation
The image above may seem a little bit confusing, but after a quick explanation it will make perfect sense. At the very top, in the purple box, is the function itself. Let’s focus on that for a moment.
On line 1, we create a function called rec that takes one parameter which we’ll call param.
On line 3, there is an if statement that checks to see if our parameter is less than three. You can see that on line 9, we are passing 0 into the parameter.
If the parameter is less than three, line 4 runs, and line 4 is where the function runs itself, again, recursively. Make note that one is added to the parameter being passed into the recursive function.
After the recursive function runs, line 5 is run, line 7, and finally the function finishes.
The Base Level (Blue Box)
Take a quick look at the blue boxes. The blue boxes are basically what I just explained above. They represent the normal function. It does what you think it would. It goes from line 1 to 7 without a hitch. In between the blue boxes is where things get interesting.
The First Recursion (Pink Box): Level 1
Try to visually see what is going on in your head. The function runs lines 1-3 as you would expect, but on line 4, the function calls itself. You can think of it like this. On line 4, the base level function pauses, and control is given to the function being run on line 4 which is identical to itself except for the parameter. We are, now, one level deep in the recursive function.
Let’s take a look at the pink boxes. Focus on the first pink box. It looks almost identical to the blue box above, except for line 3 where 0 becomes 1. This makes sense because we added one to the parameter when we ran the function on line 4 of the base level function. Each time the function runs itself, the parameter is the only thing that changes. The rest of the code is exactly the same.
On line 4 of the pink box, the same thing happens that happened on line 4 of the blue box. That is because it is the same function except for the parameter changing from 0 to 1. The pink-box function pauses on line 4, and control is given to the function on line 4.
The Second Recursion (Yellow Box): Level 2
We are, now, two levels deep in the recursive function. Take a look at the first yellow box. It is identical to the previous boxes except for the parameter. The function reaches line 4, pauses, and gives control to that function.
The Third Recursion (Green Box): Level 3
At this level of the recursion, the if statement does not pass because the parameter is not less than three. The if statement is skipped, some code is run on lines 5 and seven, and the function finishes.
Now, remember how I said that the functions were pausing? Now that this level of the recursion has finished, the rest of the functions begin starting, again, or “un-pausing.”. Here’s what I mean.
Breaking Out of the Recursion
Take a look at the yellow box right after the green box. The yellow-box, Level 2 recursion picks up right where it left off when it paused to run the green-box recursive function. It picks up on line 5, runs some code, runs some more code on line 7, and finishes.
Once Level 2 of the recursion finishes, control is given back to Level 1 of the recursion, and Level 1 picks up right where it left off on line 5. Interesting, right?
Can you guess what will happen when Level 1 finishes? That’s right. It exits, and the base level picks up right where it left off.
Look at it this way. The function is really just like any other function. It runs from line 1 to 8. The only difference is that it pauses on line 4 to run the recursive functions. Once the recursive functions finish, the function picks up right where it left off on line 5.