Recursion in Python

Today, we will discuss how to use the Recursion technique in Python.

Recursion is a very useful tool that involves a program to repeat a certain step until a desired result is achieved. The most famous are the Fibonacci numbers. The Fibonacci numbers are a list of numbers that have a rule where the current number is based of the sum of the previous two numbers, where the first two numbers in the list are zero and one.

To make a program that can do this, first open a new Python window and make a function named fib(n), where n is the nth Fibonacci number:

In the function, make an if-else statement that checks if n is less than or equal to one. If so, just return n. Otherwise, return fib(n-1)+fib(n-2). This return statement is the recursive call, because the function is calling itself. That is, it is repeating the same thing. Once done, simply call the function while passing in a number:

However, as good as this program is, if you enter bigger values for n, we have a much slower program:

If we enter 40, we have to wait twenty six seconds for the output! This is not an efficient program, because when it calls itself, it ends up doing the same calculations over and over again. There is a solution, fortunately. If a person was asked to calculate a Fibonacci number, he or she would write the previous numbers when calculating the number.

 Like that, we can tell the computer to remember what it did by using the technique Memoization (not to be confused with memorisation, which means to learn to remember something). Memoization is the process of the computer to record what it did for the purpose of the next calculation (think that the computer is leaving a note for itself).

 To do Memoization in this function, we can use a list with two starting values already placed, zero and one (since they are constant). To do this, start with creating a function fib in the same way we did above, but make a list in the function with two starting values, zero and one:

The next step is to create a for loop that runs from two to n+1. Inside the loop, we will append the value fibList[i-1]+fibList[i-2] into fibList to make a list of values (note that i is the iterator of the for loop):

Finally, we add a return statement that returns fibList[n+1] to get the desired output. We then test the program using a function call:

The program gives the same output. However, the output this time took less than one second. That is a huge improvement! This is how you use recursion in Python.