Recursive Functions in Python

Functions can call themselves! This is really handy, but can be really dangerous too, because a function can call itself forever, locking the process, or use up the available memory, reslting in the program crashing.

Example

def factorial(n):
    """ 
	Calculates the factorial of a number n (written 'n!').
	n! = n x n-1 x n-2 x ... x 2 x 1
	"""
	
    if n > 1:
        return n * factorial(n - 1)  # this function will call itself
    else:
        return n

print(factorial(6))

Output

720

Notes

While recursion can be useful, always consider how you implement the recursion with iteration instead. For example, computing factorials in the code above is not very efficient - it takes up stack space for every recursive function call and must return through all the calls. A couple better approaches are:

n = 6
factorial = 1
for i in range(1, n + 1):
    factorial *= i
	
print(factorial)

or even more simply:

import math
print(math.factorial(6))

Python has a recursion limit of 1000 by default.

Example

def factorial(n):
    if n > 1:
        return n * factorial(n - 1)
    else:
        return n

print(factorial(1000))

Output

Traceback (most recent call last):
File "Factorial.py", line 7, in <module>
print(factorial(1000))
File "Factorial.py", line 3, in factorial
return n * factorial(n - 1)
File "Factorial.py", line 3, in factorial
return n * factorial(n - 1)
File "Factorial.py", line 3, in factorial
return n * factorial(n - 1)
[Previous line repeated 995 more times]
File "Factorial.py", line 2, in factorial
if n > 1:
RecursionError: maximum recursion depth exceeded in comparison