Recursive Functions

Functions can call themselves!  This is dangerous because a function can call itself forever or use up the available stack space -- a special kind of memory that Python uses to keep track of who is calling whom.

Example

Python
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)
    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:

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

or even more simply:

Python
import math
print(math.factorial(6))

Python has a recursion limit of 1000 by default.

Example

Python
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