Function Recursion in Python

Recursion happens when a function calls itself.

The concept of a function calling itself is present in both math and programming.

A recursive call prevents the use of while and for loops.

Beware of Recursion

Of course, as with any tool, recursion is not a silver bullet and a programmer should be aware of the common mistakes when dealing with this programming technique:

• Resource use: if not used properly, a recursive code can eat up all of your RAM and CPU in no time.

• Endless recursion: a badly written code can easily fall into a never-ending loop, which will not only lock your program but also exhaust the computer resources.

• Complex recursive code can be tricky to debug if there is an error.

Code Example

The general form of a recursive call is:

def my_function():
    # any instructions
    my_function()
    # any instructions

my_function()

Factorial

To obtain the factorial of a number you multiply the number from 1 up until the given number.

There is no factorial of negative numbers.

The factorial of 0 is 1.

For instance, the factorial of 7 is 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040.

Using plain math, the recursive factorial works like this:

n! = n x (n−1)!
n! = n x (n−1) x (n−2)!
n! = n x (n−1) x (n−2) x (n−3)!
.
...

Illustrating this with the number 4, we have:

4! = 4 x (4−1)!
4! = 4 x (4−1) x (4−2)!
4! = 4 x (4−1) x (4−2) x (4−3)!
--------------------------------
4! = 4 x (3) x (2) x (1)!
4! = 4 X 3 x 2 x 1
4! = 24

To achieve this in code using recursion we have the function below.

def factorial(n):
   if n < 0:
       raise ValueError("There is no factorial of negative numbers.")
   if n == 0:
       return 1
   return n*factorial(n-1)

numbers = [0, 1, 3, 4, 7, 10]

for number in numbers:
    print(f"Factorial of {number}: {factorial(number)}")

Factorial of 0: 1
Factorial of 1: 1
Factorial of 3: 6
Factorial of 4: 24
Factorial of 7: 5040
Factorial of 10: 3628800

To see the function calling itself, let’s modify it a bit and add two prints().

def factorial(n):
   print(f"Calling for {n}")
   if n < 0:
       raise ValueError("There is no factorial of negative numbers.")
   if n == 0:
       return 1
   partial = n*factorial(n-1)
   print(f"Partial for {n} * factorial({n-1}) = {partial}")
   return partial

factorial(4)

Calling for 4
Calling for 3
Calling for 2
Calling for 1
Calling for 0
Partial for 1 * factorial(0) = 1
Partial for 2 * factorial(1) = 2
Partial for 3 * factorial(2) = 6
Partial for 4 * factorial(3) = 24
24

Notice how I raise an exception when the user tries to input a negative number.

>>> factorial(-5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in factorial
ValueError: There is no factorial of negative numbers

Fibonacci

The Fibonacci is a sequence of numbers with the following pattern:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

The index 0 of the sequence is 0 and the index 1 is 1.

Starting from the index 3 in the sequence, the Nth index is equals to the sum of the previous two numbers.

The number at index six is 8, which is the sum of the two previous values 5 (index five) and 3 (index four).

This function will give you the Nth Fibonacci number:

def fibonacci(n):
    if n < 0:
        raise ValueError("There is no fibonacci of negative numbers.")
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(9))

34

Adding a print function to visualize the recursive calls.

def fibonacci(n):
    print(f"Calling fibonacci({n})")
    if n < 0:
        raise ValueError("There is no fibonacci of negative numbers.")
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(4))

Calling fibonacci(4)
Calling fibonacci(3)
Calling fibonacci(2)
Calling fibonacci(1)
Calling fibonacci(0)
Calling fibonacci(1)
Calling fibonacci(2)
Calling fibonacci(1)
Calling fibonacci(0)
3