Recursion

Sometimes we’ll view a problem as being composed of (usually smaller or simpler) problems of the same type. This leads to a recursive approach for solving the problem: assume (by abstraction) that we can solve the smaller problems, then use the solution for the bigger one. In this way, we would continue to break a problem down to smaller and smaller versions of the same problem until we reach a version that is so small, we can easily solve it. These easily solved problems are called base cases.

When we solve a problem recursively, then, we need to think about two situations:

1. Base case(s): An input that is so small that it can easily be solved.

2. Recursive case(s): An input whose solution is composed of solutions to inputs of the same problem.

In this chapter, we’ll focus on recursive definitions of functions: the definition of a function will include an invocation to the same function. You may be thinking that this can quickly lead to very unfortunate behavior – can’t the function keep calling itself forever? It can! If it does, we have what’s called an “infinite recursion.” To avoid this, we need to think very carefully about the design of our recursive approach. To avoid an infinite recursion, we need each recursive function call to somehow be moving closer to the base case(s). This is similar to how we try to avoid an infinite while loop: at each iteration, we want to make sure we are moving towards the loop condition becoming false.

In fact, the iteration (loops) and recursion are so closely tied to each other that anything you can implement iteratively can also be implemented recursively and anything you can implement recursively can also be implemented iteratively. For this course, we will focus mostly on the mechanics of recursion, working through simple examples and tracing the code to get an idea of how Python is interpreting the recursion. If you continue in CS, you’ll find recursive techniques arise in many more advanced topics, including Data Structures and Algorithms. You’ll also find the mathematical proof technique of “proof by induction” to be analogous to recursion; this is something you would see in Discrete Mathematics or a Proof Techniques course.

To get started, we’ll work with a simple mathematical function that can be defined recursively. The factorial, denoted mathematically as n!, is the product of all numbers from n down to 1. By expanding the definition, we can observe a recursive definition for the function. Since n! = n(n-1)(n-2)(n-3)…1, we can define it recursively as n! = n[(n-1)!], with a base case of 1! = 1. This leads to a recursive implementation of the factorial:

def factorial( n ) -> int:

# base case: n is 1

if n == 1:

return 1

# recursive case

else:

# n! = n*(n-1)!

smallerFactorial:int = factorial( n-1 )

return n*smallerFactorial

print( factorial( 4 ) )

Tracing through the execution of the recursive function will help you gain an understanding of how the recursion “unravels.” You’ll notice that Python treats a function invocation the same, regardless of whether the function being invoked is the same as the function whose body is being executed. For us as humans, it may seem confusing to invoke a function from within its own definition, because we tend to start thinking of the next invocation and the next invocation, quickly getting overwhelmed. But, Python just executes one line of code at a time; if the line requires a function execution, it creates the function execution frame and moves “program control” to the body of the function.

Certain inputs will result in an infinite recursion, since the base case will never be “hit.” In other words, the recursive case will always be the part of the conditional that is executed, resulting in an infinite sequence of function invocations. Which of the following inputs will result in an infinite recursion?

• -3

• -1

• 0

• 1

• 3

How can we modify the code to avoid an infinite recursion, no matter the input?

Think about how you’d like to handle “invalid” input. One common way is to return a “flag” value, one that would never be a valid output. When the output type is a number, typical flag values are -1, 0 or 1. Since factorial will never evaluate to -1 or 0, either would be candidates as a flag. Between the two, -1 is “further” from the values we would expect to see, so it’s the “flag” value I would choose.

Let’s see another example of recursion, where we would have more than one base case and more than one recursive case. Apologies that this is a bit contrived, but hopefully it helps unpack the topic a bit.

Suppose we needed to multiply two numbers without using the * operator. It turns out there are several ways we could do this recursively. One way is to mirror what we did with factorial. Another is to break the problem in half.

Now that we have the approach outlined, let’s move to the implementation!

Here is the code, modified to include a check for invalid input.

def mult( x, y ) -> int:

""" Multiply two numbers. For simplicity, assumes x and y are both positive.

Returns a flag value of -1 if an invalid input is given. """

# invalid input

if x < 0 or y < 0:

return -1

# base cases

# base case 1: y is 0

if y == 0:

return 0

# base case 2: y is 1

elif y == 1:

return x

# recursive case

else:

# recursive case 1: y is even

if y % 2 == 0:

halfProb:int = mult( x, y//2 )

return halfProb + halfProb

# recursive case 2: y is odd

else:

halfProb1:int = mult( x, y//2 )

halfProb2:int = mult( x, y//2 + 1 )

return halfProb1 + halfProb2

print( mult( 5, 3 ))

print( mult( 5, 4 ))

Tracing out the recursion can be a little more complicated when we have more than one recursive call (recursive case 2), but is still helpful in understanding the mechanics of the recursion. Remember, you can also use Python Tutor to help.

Sometimes tracing the code can be a little too close to see the bigger picture. Particuarly with recursion, we often want to analyze the recursive calls from a higher level. We’ll draw out something called a “recursion tree,” which you would see in more depth in courses such as Data Structures and Algorithms.

This somewhat contrived recursive approach has two base cases and two recursive cases. Let’s consider what would happen if we missed one base case.

def mult( x, y ) -> int:

""" Multiply two numbers. For simplicity, assumes x and y are both positive.

Returns a flag value of -1 if an invalid input is given. """

# invalid input

if x < 0 or y < 0:

return -1

# base case

if y == 1:

return x

# recursive case

else:

# recursive case 1: y is even

if y % 2 == 0:

halfProb:int = mult( x, y//2 )

return halfProb + halfProb

# recursive case 2: y is odd

else:

halfProb1:int = mult( x, y//2 )

halfProb2:int = mult( x, y//2 + 1 )

return halfProb1 + halfProb2

Which of the following would result in an infinite recursion?

A. mult(3,0)

B. mult(0,3)

C. mult(5,2)

D. mult(6,7)

E. mult(2,8)

You may be wondering when you would choose recursion over iteration or vice versa. They have equivalent “power” in solving problems, so why are both available? Is there one that is better than the other? The answer to this is not something we can cover in the course, but here are a few things to keep in mind. First, especially when doing something for the first time, use the approach that is most intuitive to you. This will reduce the number of mistakes you make and therefore lead to more robust code (and less debugging time!). Remember that you can always revise your approach! If you continue on in computer science, you’ll hear about the “brute force” approach or a “naive approach.” Both are often the first pass we take at solving a problem, to make sure we have somewhere to start. Once we’ve done the first pass, we consider how to improve it.

In computer science, we are often concerned with efficiency and conservation of resources. Again, you would learn more about the topics I’m about to mention next in subsequent courses (such as Intro to Computing Systems, Data Structures and Algorithms). For now, let me give a tiny bit of intuition for how we would evaluate efficiency of an approach. We will generally consider two factors: how much space a program is using (e.g., how many variables, lengths of lists, etc.) and how much time it takes (how many operations are used). It turns out that invoking functions uses up both – operations to set up an execution frame as well as space (for example, to track the parameters, where to return control to, etc.). Therefore, we often would, purely from an efficiency perspective, favor an iterative approach over a recursive one.

Let’s look at the factorial function as a case study. We could:

1. implement it using a for loop, tracking the accumulated product as we move from n down to 1

2. implement it using a list, storing at index i the value i!

3. implement it recursively (as we saw at the beginning of this topic)

These approaches are listed in order of efficiency.

However, as you get to more complex schemes to break down a problem, you may find that the recursive approach is much more intuitive and sometimes it can be hard to envision an iterative approach at all. Trying to directly create an iterative approach can cause you to go off-track and end up making mistakes. Therefore, especially at this point in your learning journey, you should pick the approach that makes the most sense to you. You can always revise it after you have a working version. This is probably similar to how you write a long research paper – you make a draft, then revise.

Many "divide-and-conquer" approaches break a problem in half, much like the multiplication approach we saw previously. This can lead to an improvement in the amount of "time" required. The code below compares the time (in terms of function calls) between the "linear" approach of peeling one value of x off at a time versus breaking the problem in half.

def multLin( x, y ) -> int:

""" Multiply two numbers. For simplicity, assumes x and y are both positive.

Returns a flag value of -1 if an invalid input is given. """

global numInvocations

numInvocations += 1

# invalid input

if x < 0 or y < 0:

return -1

# base case: y is 0

if y == 0:

return 0

# recursive case

else:

return x + multLin(x,y-1)

def mult( x, y ) -> int:

""" Multiply two numbers. For simplicity, assumes x and y are both positive.

Returns a flag value of -1 if an invalid input is given. """

global numInvocations

numInvocations += 1

# invalid input

if x < 0 or y < 0:

return -1

# base cases

# base case 1: y is 0

if y == 0:

return 0

# base case 2: y is 1

elif y == 1:

return x

# recursive case

else:

# recursive case 1: y is even

if y % 2 == 0:

halfProb:int = mult( x, y//2 )

return halfProb + halfProb

# recursive case 2: y is odd

else:

halfProb1:int = mult( x, y//2 )

halfProb2:int = mult( x, y//2 + 1 )

return halfProb1 + halfProb2

numInvocations:int = 0

print( f"Computing 5*16 by peeling off a single addition produces {multLin( 5, 16 )} " + \

f"in {numInvocations} function calls." )

numInvocations = 0

print( f"Computing 5*16 by breaking it in half produces {mult( 5, 16 )} " + \

f"in {numInvocations} function calls." )

Outputs

Computing 5*16 by peeling off a single addition produces 80 in 17 function calls.

Computing 5*16 by breaking it in half produces 80 in 5 function calls.