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\$``````