Recursive Functions

When a function calls itself, it is known as a Recursive Function. This is like for loops. However, sometimes it allows you to write more elegant and terse functions than can be achieved with a loop.

You can imagine that a function that calls itself might end up in an infinite loop; it is true that you can write a recursive function that will keep running indefinitely:

def print_the_next_number(start):

        print(start + 1)

        return print_the_next_number(start + 1)

print_the_next_number(5)

You should get the following output:

6

7

8

9

10

11

Note

The output mentioned above is truncated.

If you run this code in a Python shell, it will continue printing integers until you interrupt the interpreter (Ctrl + C). Take a look at the preceding code and ensure you understand why it behaves in this manner. The function executes the following steps:

• The function is called with start = 5.
• It prints 6 to the console, that is (5 + 1 = 6).
• It then calls itself, this time passing in the argument start = 6.
• The function starts again, this time printing 7, that is (6 + 1 = 7).

A Terminating Case

To avoid being stuck in an infinite loop, a recursive function will typically have a Terminating Case, such as a point where the chain of recursion is broken. In our previous example, you could make it stop once the start parameter is greater than or equal to 7:

def print_the_next_number(start):

    print(start + 1)

    if start >= 7:

        return "I'm bored"

    return print_the_next_number(start + 1)

print_the_next_number(5)

You should get the following output:

Figure 3.24: Terminating the loop

Exercise 50: Recursive Countdown

In this exercise, you will create a countdown function that recursively counts down from integer n until we hit 0:

1. In Jupyter Notebook, enter the function definition. Note that the tab spacing needs to match the output that follows:

   def countdown(n):

       if n == 0:

           print('liftoff!')

       else:

           print(n)

           return countdown(n - 1)

2. Test the function:

   countdown(3)

3. You should get the following output:

Figure 3.25: Counting down with recursion

In this exercise, you successfully implemented a termination statement after number 1, with the term liftoff. This shows us that the recursive countdown has ended.

Exercise 51: Factorials with Iteration and Recursion

In this exercise, you create a factorial_iterative function that takes an integer and returns the factorial using both an iterative and a recursive approach. Recall that a factorial is the product of all integers up to and equal to the number.

For instance, the factorial of 5 is calculated as 5! = 5 * 4 * 3 * 2 * 1 = 120.

1. In a Jupyter Notebook, enter the following function to compute factorials using iteration:

   def factorial_iterative(n):

           result = 1

           for i in range(n):

               result *= i + 1

           return result

2. Test the function:

   factorial_iterative(5):

   You should get the following output:

   120

3. Note that you can express n! = n * (n – 1)!; for instance, 5! = 5 * 4!. This means we can write the function with recursion as follows:

   def factorial_recursive(n):

           if n == 1:

               return 1

           else:

               return n * factorial_recursive(n - 1)    

4. Test the function:

   factorial_recursive(5):

   You should get the following output:

   120

In this exercise, you successfully implemented and used both iteration and recursion to find the factorial of n numbers.

Activity 11: The Fibonacci Function with Recursion

Suppose that your colleague has told you that the iterative function you designed in Activity 10, The Fibonacci Function with an Iteration, is not elegant and should be written with fewer lines of code. Your colleague mentions that a recursive solution will be able to achieve this.

In this activity, you will use recursion to write a terse (but inefficient) function for computing the nth term of the Fibonacci sequence.

The steps are as follows:

1. Open the fibonacci.py file created in Activity 10, The Fibonacci Function with an Iteration.
2. Define a fibonacci_recursive function, which takes a single positional argument representing which number term in the sequence we want to return.
3. Try running a few examples in a Python shell:

   from fibonacci import fibonacci_recursive

   To find the fibonacci recursive for the value 3.

   fibonacci_recursive(3)

   You should get the following output:

   2

   You can run the following code and find the fibonacci recursive for the value 10.

   fibonacci_recursive(10)

   You should get the following output:

   55

   Note

   The fibonacci.py file can be found on GitHub at https://packt.live/35yKulH.

   The solution for this activity is available on page 531.