Reading Recursive Code

It takes time and practice to get used to recursion, and you’ll ultimately learn two sets of skills: reading recursive code and writing recursive code. Reading recursive code is somewhat easier, so let’s get some practice with that first.

We’ll do this by looking at another example: calculating factorials.

A factorial is best illustrated with some examples.

The factorial of 3 is:

3 * 2 * 1 = 6

The factorial of 5 is:

5 * 4 * 3 * 2 * 1 = 120

And so on and so forth.

Here’s a recursive implementation that returns a number’s factorial:

	def factorial(number):
	if number <= 1:
	return 1
	else:
	return number * factorial(number - 1)

This code can look somewhat confusing at first glance. To walk through the code to see what it does, here’s the process I recommend:

Identify the base case.
Walk through the function for the base case.
Identify the next-to-last case. This is the case just before the base case, as I’ll demonstrate momentarily.
Walk through the function for the next-to-last case.
Repeat this process by identifying the case before the one you just analyzed and walking though the function for that case.

Let’s apply this process to the preceding code. If we analyze the code, we’ll quickly notice that there are two paths. One path is where number is less than or equal to 1, and the other path is where number is greater than 1:

	if number <= 1: # Path 1
	...
	else: # Path 2: number is greater than 1
	...

We can see that the recursion happens inside the else path, since factorial calls itself:

	else:
	return number * factorial(number - 1)

So it must be that the base case is the first path, since it’s the path where no recursion is taking place:

	if number <= 1:
	return 1

We can conclude, then, that the base case is when number is less than or equal to 1.

Next, let’s walk through the factorial method assuming it’s dealing with a base case, such as factorial(1). Again, the relevant code from our method is the following:

	if number <= 1:
	return 1

Well, that’s pretty simple—it’s the base case, so no recursion actually happens. If we call factorial(1), the method simply returns 1. Okay, so grab a napkin and write this fact down:

Next, let’s move up to the next case, which would be factorial(2). The relevant line of code from our method is:

	else:
	return number * factorial(number - 1)

So calling factorial(2) will return 2 * factorial(1). To calculate 2 * factorial(1), we need to know what factorial(1) returns. If you check your napkin, you’ll see that it returns 1. So 2 * factorial(1) will return 2 * 1, which just happens to be 2.

Add this fact to your napkin:

/books/45079/OEBPS/recursively_recurse_with_recursion/napkin_2.png

Now, what happens if we call factorial(3)? Again, the relevant line of code is:

	else:
	return number * factorial(number - 1)

So that would translate into return 3 * factorial(2). What does factorial(2) return? You don’t have to figure that out all over again, since it’s on your napkin! It returns 2. So, factorial(3) will return 6 (because 3 * 2 = 6). Go ahead and add this wonderful factoid to your napkin:

/books/45079/OEBPS/recursively_recurse_with_recursion/napkin_3.png

Take a moment and figure out for yourself what factorial(4) will return.

As you can see, starting the analysis from the base case and building up is a great way to reason about recursive code.