Infinite Recursion

One potential pitfall when writing recursive functions is to ensure you're not calling the recursive function infinitely. This can happen if your base case is missing or incorrectly defined.

For example, this program attempts to count down from a given integer, two numbers at a time:

def count_down_by_two(n):
    if n == 0:
        # base case
        print(n)
    else:
        print(n)
        count_down_by_two(n - 2)

Say that we call count_down_by_two(8). Everything works as expected:

count_down_by_two(8):
  print(8)
  call count_down_by_two(6)

  count_down_by_two(6):
    print(6)
    call count_down_by_two(4)

    count_down_by_two(4):
      print(4)
      call count_down_by_two(2)

      count_down_by_two(2):
        print(2)
        call count_down_by_two(0)

        count_down_by_two(0):
          print(0)
          return (base case)

All of the recursive calls then return, and the overall output is:

8
6
4
2
0

Check your understanding of the execution of this code by stepping through it yourself using Python Tutor:

But what if we call count_down_by_two(5)? Before playing the video below, try to predict what the result will be by tracing the execution of the count_down_by_two() function defined above. Only proceed to the video and code below after making your prediction.

Clearly, we need a more comprehensive base case -- one that is more robust to the different patterns of execution. Here's one way you could correct the issue (by using <= in the base case):

def count_down_by_two(n):
    if n <= 0:
        # base case
        # if we've gone negative, just print 0 and stop
        print(0)
    else:
        print(n)
        count_down_by_two(n - 2)

Now that we know a bit about writing recursive methods, let's learn about how to trace their execution to gain a better understanding of how they work.