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

Thursday: Recursive Functions and Memoization
Recursion is a concept in programming where a function calls itself one or more times within its block. These types of functions can often run into issues with speed, however, due to the function constantly calling itself. Memoization helps this process by storing values that were already calculated to be used later. Let’s first understand more about recursive functions.
To follow along with this lesson, let’s continue from our previous notebook file
“Week_08” and simply add a markdown cell at the bottom that says, “Recursive
Functions and Memoization.”

Understanding Recursive Functions

All recursive functions have what is known as a “base case,” or a stopping point. Like loops, you need a way to break out of a recursive call. Without one you create an infinite loop that will eventually crash. For example, let’s imagine we set a base case of 1 for the following questions:

1. 
   Can you calculate the sum of 5?
   
2. 
   Can you calculate the sum of 5 ∗ 4?
   
3. 
   Can you calculate the sum of 5 ∗ 4 ∗ 3?
   
4. 
   Can you calculate the sum of 5 ∗ 4 ∗ 3 ∗ 2?
   
5. 
   Can you calculate the sum of 5 ∗ 4 ∗ 3 ∗ 2 ∗ 1?
   
6. 
   Yes, we reached our base case; the result is 120.
   

In this example, we started our recursive call at 5 and wanted to reach our base case before we calculated the total. On each new call, we add a number to the expression, which was the previous number minus one. This was an example of a factorial function performing a recursive call. Depending on the task, functions could perform two recursive calls at once. The most obvious example of this is the Fibonacci sequence.
We’ll program both together.
You may be asking yourself, how are these useful? In general, you can program a loop to perform the same task that a recursive call can. So why use them? In certain instances, recursive functions are easier to understand rather than programming a loop. They’re used often in searching and sorting algorithms because of the repetitive tasks that occur.
Imagine you needed to search through a 4-dimensional array, otherwise known as a list within a list within a list within a list. Rather than writing a bunch of for loops to iterate through each list, you could write a recursive function that calls itself every time a new dimension is found. The code would produce far less lines and be easier to read. Let’s check out some examples!