Python Projects for Beginners a ten-Week Bootcamp Approach to Python Programming

Writing a Factorial Function

Factorials are one of the easier examples of recursion because they are the result of a given number multiplied by all previous numbers until zero is reached. Let’s try programming it:

# writing a factorial using recursive functions def factorial(n): # set your base case! if n <= 1:
return 1 else:
return factorial( n – 1 ) * n print( factorial(5) ) # the result of 5 * 4 * 3 * 2 * 1

Go ahead and run the cell. As we know from the example previously, we’ll get an output of 120. The recursive call occurs within the else block. The return statement calls the factorial function within itself because in order to get the result of factorial(5), it must calculate “factorial(4) ∗ 5”. Then it must calculate “factorial(3) ∗ 4” in order to get the result of factorial(4) as shown in the following:

1. 
   factorial(5) = factorial(4) ∗ 5
   
2. 
   factorial(4) = factorial(3) ∗ 4
   
3. 
   factorial(3) = factorial(2) ∗ 3
   
4. 
   factorial(2) = factorial(1) ∗ 2
   
5. 
   factorial(1) = 1
   

ChapteR 8 advanCed topICs I: eFFICIenCy
This occurs until the base case is reached at factorial(1), which does not have a recursive call and returns the value 1. As soon as the base case is reached, it can begin to return all the calculated values back to the original call, as shown in the following:

1. 
   factorial(1) = 1
   
2. 
   factorial(2) = 1 ∗ 2 = 2
   
3. 
   factorial(3) = 3 ∗ 3 = 6
   
4. 
   factorial(4) = 9 ∗ 4 = 24
   
5. 
   factorial(5) = 24 ∗ 5 = 120
   

Recursive functions work their way down until the base case is reached. Once a single value is returned, it can then work its way back to the previous calls and return a result.

The Fibonacci Sequence

The Fibonacci sequence is one of the most famous formulas in mathematics. It’s also one of the most well-known recursive functions in programming. Each number in the sequence is the sum of the previous two numbers, such that fib(5) = fib(4) + fib(3). The base case for the Fibonacci sequence is 0 and 1 because the result of fib(2) is “fib(2) = fib(1) + fib(0)”. In order to create the recursive sequence, we’ll need to return the respective value once below the value of two:

# writing the recursive fibonacci sequence def fib(n): if n <= 1:
return n else:
return fib( n – 1 ) + fib( n – 2 ) print( fib(5) ) # results in 5

Go ahead and run the cell. We get 5 as the output. Remember that it’s not the result of 3 + 4 but rather the result of fib(3) + fib(4). The Fibonacci sequence utilizes two recursive calls in a single return, which makes it much more complex than our factorial function. In order to calculate fib(5), fib(1) must be calculated five times. This is because of the two-part recursive call. When these recursive calls occur, they essentially break out into a pyramid-like structure. Let’s look at Figure 8-1, for instance.

Figure 8-1. Fibonacci sequence recursive sequence tree
This figure represents all the recursive calls that need to occur in order to calculate the result of fib(5). As the number passed in grows, so to does the structure and number of recursive calls. It’s exponential, which can slow down the program dramatically. Even trying to execute fib(40) can take a couple minutes, and fib(100) will generally break because of maximum recursion depth issues. Which leads us to our next topic on how to solve this issue… memoization.