Recursion in Python

Recursion in Python means that functions can call themselves (self-reference).

Let’ take for example the factorial function: 5! = 5 * 4 * 3 * 2 * 1 where 5! is called “5 factorial”. Let’s take the formula again!

5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1

We can conclude that n! = n * (n-1)!

Example:

def factorial(x):
	if x == 1:
		return 1
	else: 
		return x * factorial(x-1)

print(factorial(5))

The terminal output will be 120.

Note:
The base case acts as the exit condition of the recursion. If you forget to implement the base case the recursion functions can be infinite.

def factorial(x):
	return x * factorial(x-1)

print(factorial(5))

The result will be RuntimeError: maximum recursion depth exceeded

Recursion can also be indirect. One function can call a second, which calls the first, which calls the second, and so on. This can occur with any number of functions.

Example:

def is_even(x):
	if x == 0:
		return True
	else:
		return is_odd(x-1)

def is_odd(x):
	return not is_even(x)

print(is_odd(11))
print(is_even(39))

The terminal output will be:

ddn_ro@linux:~/Desktop$ python file.py
True
False
ddn_ro@linux:~/Desktop$

Leave a Reply