Skip to main content

Section 24.1 Intro to Recursion

A recursive function is simply one that calls itself. The function calls itself is called a recursive call.
Consider the following example of the recursive function countdown. If it is called with an n value of 0, it displays the word Blastoff!. Otherwise, it displays the number and then makes a recursive call to countdown, passing n - 1 as the argument.
Run the codelens to watch it execute:
Listing 24.1.1.
What happened when we invoked countdown(3) from main?
  • The execution of countdown begins with n == 3, and since n is not 0, it displays the value 3, and then invokes countdown(2)
  • countdown(2) begins, and since n is not 0, it displays the value 2, and then invokes countdown(1)
  • countdown(1) begins, and since n is not 0, it displays the value 1, and then invokes countdown(0)
  • countdown(0) begins, and since n is 0, it displays the word Blastoff!.
Now let’s swap lines 9 and 10. Run this new version:
Listing 24.1.2.

Checkpoint 24.1.1.

What is the output of countdown(3) in Listing 24.1.2 ?
  • 3 2 1 Blastoff!
  • 1 2 3 Blastoff!
  • Blastoff! 3 2 1
  • Blastoff! 1 2 3
What was different this time? The work of displaying the number was done after the recursive call. So level 3 did not print until after level 2 was done. And level 2 did not print until after level 1 was done...

Insight 24.1.1.

A recursive call breaks the execution of a function into two parts. The code before the recursive call runs before the next recursive call executes. The code after the recursive call runs after the recursive call completes.
We can more clearly see the timing in this final example. Notice this countdown prints both before and after the recursive call.
Listing 24.1.3.
What happened this time when we invoked countdown(3) from main?
  • The execution of countdown begins with n == 3, and since n is not 0, it displays the start message, and then invokes countdown(2)
  • countdown(2) begins, and since n is not 0, it displays the start message, and then invokes countdown(1)
  • countdown(1) begins, and since n is not 0, it displays the start message, and then invokes countdown(0)
  • countdown(0) begins, and since n is 0, it displays the word Blastoff!. It returns to where it was called (countdown(1)).
  • Back in countdown(1) execution resumes after the recursive call and displays the finish message. It then returns to where it was called (countdown(2)).
  • Back in countdown(2) execution resumes after the recursive call and displays the finish message. It then returns to where it was called (countdown(3)).
  • Back in countdown(3) execution resumes after the recursive call and displays the finish message. It returns to where it was called (main).
You have attempted of activities on this page.
PrevTopNext