Log in / Register
Home arrow Computer Science arrow Data Structures and Algorithms with Python
< Prev   CONTENTS   Next >

3.4 Writing a Recursive Function

A recursive function is simply a function that calls itself. It's really very simple to write a recursive function, but of course you want to write recursive functions that actually do something interesting. In addition, if a function just kept calling itself it would never finish. Actually, it would finish when run on a computer because we just learned that every time you call a function, an activation record is pushed on the run-time stack. If a recursive function continues to call itself over and over it will eventually fill up the run-time stack and you will get a stack overflow error when running such a program.

To prevent a recursive function from running forever, or overflowing the runtime stack, every recursive function must have a base case, just like an inductive proof must have a base case. There are many similarities between inductive proofs and recursive functions. The base case in a recursive function must be written first, before the function is called recursively.

Now, wrapping your head around just how a recursive function works is a little difficult at first. Actually, understanding how a recursive function works isn't all that important. When writing recursive functions we want to think more about what it does than how it works. It doesn't pay to think too hard about how recursive functions work, but in fact even that will get much easier with some practice.

When writing a recursive function there are four rules that you adhere to. These rules are not negotiable and will ensure that your recursive function will eventually finish. If you memorize and learn to follow these rules you will be writing recursive functions in no time. The rules are:

1. Decide on the name of your function and the arguments that must be passed to it to complete its work as well as what value the function should return.

2. Write the base case for your recursive function first. The base case is an if statement that handles a very simple case in the recursive function by returning a value.

3. Finally, you must call the function recursively with an argument or arguments that are smaller in some way than the parameters that were passed to the function when the last call was made. The argument or arguments that get smaller are the same argument or arguments you examined in your base case.

4. Look at a concrete example. Pick some values to try out with your recursive function. Trust that the recursive call you made in the last step works. Take the result from that recursive call and use it to form the result you want your function to return. Use the concrete example to help you see how to form that result.

We'll do a very simple example to begin with. In the last chapter we proved the following.

So, if we wanted to compute the sum of the first n integers, we could write a Python program as shown in Sect. 3.4.1.

3.4.1 Sum of Integers

1 def sumFirstN(n):

2 return n * (n+1) // 2


4 def main():

5 x = int(input("Please enter a non-negative integer: "))


7 s = sumFirstN(x)


9 print("The sum of the first", x, "integers is", str(s)+".")


11 if name == " main ":

12 main()

In this case, this would be the best function we could write because the complexity of the sumFirstN function is O(1). This means the time it takes to execute this function is not dependent on the size of the data, n. However, to illustrate a recursive function, let's go back to the definition of summation. The definition for summation has two parts. First, the base case of the definition.

The recursive part of the definition is as follows. This is what we call a recursive definition because it is defined in terms of itself. Notice that the recursive definition is defined in terms of a smaller n, in this case n − 1. The summation to n − 1 is our recursive call and it will work. If we want to compute the sum of the first 5 integers, then the recursive call computes 1 + 2 + 3 + 4 to give us 10. Adding n will give use 15, the result we want.

The two parts of this recursive definition can be translated directly into a recursive function in Python. The recursive definition is given in Sect. 3.4.2.

3.4.2 Recursive Sum of Integers

1 def recSumFirstN(n):

2 if n == 0:

3 return 0

4 else:

5 return recSumFirstN(n-1) + n


7 def main():

8 x = int(input("Please enter a non-negative integer: "))


10 s = recSumFirstN(x)


12 print("The sum of the first", x, "integers is", str(s)+".")


14 if name == " main ":

15 main()

The recSumFirstN function in the code of Sect. 3.4.2 is recursive. It calls itself with a smaller value and it has a base case that comes first, so it is well-formed. There is one thing that we might point out in this recursive function. The else is not necessary. When the Python interpreter encounters a return statement, the interpreter returns immediately and does not execute the rest of the function. So, in Sect. 3.4.2, if the function returns 0 in the then part of the if statement, the rest of the function is not executed. If n is not zero, then we want to execute the code on the else statement. This means we could rewrite this function as shown in Sect. 3.4.3.

3.4.3 No Else Needed

1 def recSumFirstN(n):

2 if n == 0:

3 return 0


5 return recSumFirstN(n-1) + n

The format of the code in Sect. 3.4.3 is a common way to write recursive functions. Sometimes a recursive function has more than one base case. Each base case can be handled by an if statement with a return in it. The recursive case does not need to be in an else when all base cases result in a return. The recursive case comes last in the recursive function definition.

Found a mistake? Please highlight the word and press Shift + Enter  
< Prev   CONTENTS   Next >
Business & Finance
Computer Science
Language & Literature
Political science