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)!
def factorial(x): if x == 1: return 1 else: return x * factorial(x-1) print(factorial(5))
The terminal output will be 120.
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.
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$