16: Recursion

We have seen that functions allow us to organize and re-use parts of our code. We have also seen that functions can be defined in terms of other functions. In this lesson we learn that a function can be defined in terms of itself! This very useful approach is called recursion. Legend has it that “to understand recursion, you must first understand recursion.”

Example

In our lesson on loops, we used a while loop to create the following output.

5
4
3
2
1
Blastoff!
Here is a program that uses recursion to achieve the same effect.

Example
A countdown using recursion

Let's add some extra print statements to help us understand how the program works. This version of the program also reads the time limit from input.

Example
A countdown using recursion
You may enter input for the program in the box above.

If you like, use Enter input with the above program to try other input values. Try 0 first and see what happens, and then 1.

When the input is 5, the program first calls a copy of the countdown function with n=5, which prints 5 and calls countdown(4). This continues until countdown(0), which prints "Blastoff!" and does not call countdown any more. When Python finishes executing the n=0 call of the countdown function, Python returned to the function that called it, which is the n=1 call of the countdown. Then we return to the n=2 call, and so on.

Now it's your turn to write some code. Modify the countdown function so that it counts up instead of down.

Coding Exercise: Blast Up
Write a recursive function countup(n) which prints 'Blastoff!' followed by the numbers 1 to n on separate lines. Hint
Enter testing statements like print(myfunction("test argument")) below.

Next, let's modify our countdown program to count in increments of 2. The output should be 5, 3, 1, Blastoff! We will change the function argument from n-1 to n-2. Is there anything else that we need to change?

Example
Trying to count down in increments of 2

You can see that this program did not work as we intended. It printed 5, 3, 1, like we wanted, but instead of stopping it continued with -1, -3, -5 and ran forever. (More precisely, it runs out of time and also memory, because each recursive call takes up a little more working memory.)

When designing a recursive function, we must be careful that its sequence of calls does not continue forever! Modify the countdownBy2 program above so that it correctly stops at 1 (or 2, if n is even) and prints 'Blastoff!'.

Coding Exercise: Double Time
Modify this recursive program to correctly count down in increments of 2.
Enter testing statements like print(myfunction("test argument")) below.

Designing recursive functions

A recursive function just means a function that calls itself. But there must be some occasions when the function does not call itself, or else the program will run forever, like we saw above. A base case is the part of a recursive function where it doesn't call itself. In the example above, the base case was n<=0. Designing a recursive function requires that you carefully choose a base case and make sure that every sequence of function calls eventually reaches a base case.

In the next exercise, the base case has been programmed for you, but you will write the rest of the recursive function.

Coding Exercise: Digital Sum
The digital sum of a number n is the sum of its digits. Write a recursive function digitalSum(n) that takes a positive integer n and returns its digital sum. For example, digitalSum(2019) should return 12 because 2+0+1+9=12. Hint #1 Hint #2
Enter testing statements like print(myfunction("test argument")) below.

Now you will write a recursive function that calls digitalSum as a subroutine.

Coding Exercise: Digital Root
The digital root of a non-negative integer n is computed as follows. Begin by summing the digits of n. The digits of the resulting number are then summed, and this process is continued until a single-digit number is obtained. For example, the digital root of 2019 is 3 because 2+0+1+9=12 and 1+2=3. Write a recursive function digitalRoot(n) which returns the digital root of n.
Assume that a working definition of digitalSum will be provided for your program.
Enter testing statements like print(myfunction("test argument")) below.

Exercises

Short Answer Exercise: GCD
What is the output of the following recursive program? 
def gcd(a, b):
  if b == 0: return a
  return gcd(b, a % b)
print(gcd(20, 12))
Correct!

Coding Exercise: Hailstone
The hailstone sequence starting at a positive integer n is generated by following two simple rules. If n is even, the next number in the sequence is n/2. If n is odd, the next number in the sequence is 3*n+1. Repeating this process, we generate the hailstone sequence. Write a recursive function hailstone(n) which prints the hailstone sequence beginning at n. Stop when the sequence reaches the number 1 (since otherwise, we would loop forever 1, 4, 2, 1, 4, 2, ...)
For example, when n=5, your program should output the following sequence: 
5
16
8
4
2
1
Enter testing statements like print(myfunction("test argument")) below.

Mathematicians believe that every hailstone sequence reaches 1 eventually, no matter what value of n we start with. However, no one has been able to prove this yet.

Recursion is also related to fractals — images which contain multiple smaller copies of themselves. The banner at the top of this webpage is one example. The next exercise creates a simple repeating pattern using recursion.

Scramble Exercise: Fractal Ruler
Unscramble the lines to create a program that produces a recursive ruler-like design. For example, when n=3 the program should output the following design. 
-
--
-
---
-
--
-
  • print('-')
  • def ruler(n):
  • print(n * '-')
  • ruler(n - 1)
  • if n == 1:
  • else:
  • ruler(n - 1)

Congratulations! You are ready to move to the next lesson.