We have seen many instances where one function calls some other function, in fact, most of the programs we have written have included a main() function that calls upon other functions. It’s also possible for a function to call itself!

A function that calls itself is known as a recursive function. Recursion is a fairly advanced area of study in computer science. In my Java Tutorial, we’ll spend more time analyzing and writing recursive functions. For now, I just want you to appreciate the basic characteristics of recursive functions.

Here is an example of a recursive function:

def main():
    countdown()
  
def countdown():
    print('Blast-off!')
    countdown()
  
# Call the main function.
main()

def main():

countdown()

def countdown():

print('Blast-off!')

countdown()

# Call the main function.

main()

The countdown() function displays a message, then calls itself so it is a recursive function. But if you run this you’ll see that there’s a problem. There is no way to stop the recursive calls. Like an infinite loop, this code demonstrates infinite recursion, which means that the function will continue calling itself indefinitely (or until we run out of memory).

Like a loop, a recursive function must have some sort of condition to control the number of times it repeats. Let’s revise the program:

def main():
    countdown(5)
  
def countdown(n):
    if n <= 0:
        print("Blast-off!")
    else:
        print(n)
        countdown(n-1)
  
# Call the main function.
main()

def main():

countdown(5)

def countdown(n):

if n <= 0:

print("Blast-off!")

else:

print(n)

countdown(n-1)

# Call the main function.

main()

Now the countdown() function includes a condition that controls the repetition. As long as parameter n is greater than zero, the message will be displayed, and the function will call itself again, but with a smaller argument.

If you trace this out on paper you’ll see that the countdown() function is called six times. Once by the main() function, then 5 times recursively by the countdown() function until the times parameter equals 0. The number of times that a function calls itself recursively is called the depth of recursion. In this example, the depth of recursion is 5.

Problem Solving With Recursion

Recursion can be a powerful tool for solving repetitive problems and is often useful for computing competitions like the Waterloo CCC. It takes a lot of practice to become proficient at using recursion to solve problems.

To solve a problem with a recursive function we first need to identify at least one case in which the problem can be solved without recursion, this is called the base case. Second, we need to determine a way to solve the problem in all other circumstances using recursion, called the recursive case. The recursive case must always reduce the problem to a smaller version of the original problem. By reducing the problem with each recursive call, the base case will eventually be reached and the recursion will stop.

There are many well-defined problems in mathematics that lend themselves to recursive solutions. Consider the definition of a factorial:

The definition above clearly lays out the base case, where the result is 1 if n <= 1. This tells us how to solve the problem without recursion when n is 1. The recursive case is when n >1. Notice how the recursive call works on a reduced version of the problem, n – 1. Translating a definition like this into code is very straightforward:

def main():
    # Get a number from the user.
    number = int(input('Enter a non-negative integer: '))
  
    # Get the factorial of the number.
    fact = factorial(number)
  
    # Display the factorial.
    print('The factorial of', number, 'is', fact)
  
def factorial(num):
    """This function uses recursion to calculate and return the factorial 
    of its argument, which is assumed to be non-negative."""
    if num <= 1:
        return 1
    else:
        return num * factorial(num - 1)
  
# Call the main function.
main()

def main():

# Get a number from the user.

number = int(input('Enter a non-negative integer: '))

# Get the factorial of the number.

fact = factorial(number)

# Display the factorial.

print('The factorial of', number, 'is', fact)

def factorial(num):

"""This function uses recursion to calculate and return the factorial

of its argument, which is assumed to be non-negative."""

if num <= 1:

return 1

else:

return num * factorial(num - 1)

# Call the main function.

main()

Try tracing this out on paper if you enter a value of 4. You’ll see that after the first call to the factorial() function from main(), the factorial() function will call itself 3 more times. Thus, the depth of the recursion would be 3.

Usually, making the value of one or more parameters smaller with each recursive call reduces a problem. In our factorial()function, the value of the parameter num gets closer to 1 with each recursive call. When the parameter reaches 1, the function returns a value without making another recursive call.

Using Lists With Recursion

Let’s look at another recursive function that takes a list of numbers as a parameter and returns the sum of all the numbers. In this case, the base case would be if the function is passed an empty list [ ]. The sum of the items in an empty list is obviously 0. The recursive case would add the value of the first item in the list with the sum of the items in the rest of the list.

Here’s the code:

def main():
    # Create a list of numbers.
    numbers = [1, 2, 3.14, 4, 5, 6.125, 7, 8, 9]
  
    # Get the sum of all the elements
    my_sum = range_sum(numbers)
  
    # Display the sum.
    print('The sum of items in the list is', my_sum)
  
def range_sum(num_list):
    """This function accepts a list as a parameter and returns the sum of all
    numbers in the list.  It is assumed that this list contains only integer
    or float values."""
    if num_list == []:
        return 0
    else:
        return num_list[0] + range_sum(num_list[1:])
  
# Call the main function.
main()

def main():

# Create a list of numbers.

numbers = [1, 2, 3.14, 4, 5, 6.125, 7, 8, 9]

# Get the sum of all the elements

my_sum = range_sum(numbers)

# Display the sum.

print('The sum of items in the list is', my_sum)

def range_sum(num_list):

"""This function accepts a list as a parameter and returns the sum of all

numbers in the list. It is assumed that this list contains only integer

or float values."""

if num_list == []:

return 0

else:

return num_list[0] + range_sum(num_list[1:])

# Call the main function.

main()

Recursion vs. Looping

Any algorithm that can be coded with recursion can also be coded with a loop. Both approaches achieve repetition, but which is best to use?

There are several reasons not to use recursion. Recursive function calls are certainly less efficient than loops. Each time a function is called, the system incurs overhead that is not necessary with a loop. Overhead is the memory required to store the parameters variables and local variables each time a function is called. Also, in many cases, a solution using a loop is more evident than a recursive solution. In fact, the majority of programming tasks are best done with loops.

However, some (often mathematical) problems, are more easily solved with recursion and with a loop. If a recursive solution is evident for a particular problem, then recursion would be a good design choice. If a problem is more easily solved with a loop, then you should take that approach.

You Try!

Start a new page in your Learning Journal titled “3-10 Recursive Functions“. Carefully read the notes above and in your own words summarize the key ideas from each section.
It is said that a recursive algorithm has more overhead than an iterative algorithm. What does this mean?

Try to figure out what the following code will display, then check your hypothesis using the Python interpreter.

def main():
    num = 0
    show_me(num)
  
def show_me(arg):
    if arg < 5:
        show_me(arg+1)
    else:
        print(arg)
  
main()

def main():

num = 0

show_me(num)

def show_me(arg):

if arg < 5:

show_me(arg+1)

else:

print(arg)

main()

Try to figure out what the following code will display, then check your hypothesis using the Python interpreter.

def main():
    num = 0
    show_me(num)
  
def show_me(arg):
    print(arg)    
    if arg < 5:
        show_me(arg+1)
  
main()

def main():

num = 0

show_me(num)

def show_me(arg):

print(arg)

if arg < 5:

show_me(arg+1)

main()

The following function uses a loop. Rewrite it as a recursive function that performs the same operation.

def main():
    traffic_sign(5)
      
def traffic_sign(n):
    while n > 0:
        print('No Parking')
        n = n - 1
  
main()

def main():

traffic_sign(5)

def traffic_sign(n):

while n > 0:

print('No Parking')

n = n - 1

main()

Hacker Level Question: Write a recursive function that accepts an integer argument and returns the sum of all the integers from 1 up to the number. For example, if 9 is passed as an argument the result returned should be 45. Write a main() function to demonstrate how it works.
Hacker Level Question: Write a recursive function that raises a number to a power. The function should accept two arguments, the number and the exponent. Assume that the exponent is a non-negative integer. Write a main() function to demonstrate how it works.
Hacker Level Question: Write a recursive function that accepts two arguments into parameters x and y. The function should return the value of x times y. Hint: multiplication can be performed as repeated addition (5 x 4 = 4 + 4 + 4 + 4 + 4). Write a main() function to demonstrate how it works.