A function that calls itself is using recursion.
The idea appears throughout both mathematics and programming. Its benefit is that a function can loop through data until it arrives at a result.
Take care when you write one, because it's easy to end up with a function that never stops, or one that eats up too much memory or processor power. Done right, though, recursion is an efficient and mathematically elegant way to program.
Example
A recursive countdown starting at 5:
Output: complete Python program
def countdown(n):
if n <= 0:
print("Done!")
else:
print(n)
countdown(n - 1)
countdown(5)
Base Case and Recursive Case
Two parts are required in any recursive function:
- The base case - The condition that ends the recursion
- The recursive case - The point where the function calls itself with a changed argument
Take away the base case and the function keeps calling itself until Python stops it with a recursion error.
Nothing matters more here than the base case, so always check that its condition will be reached sooner or later.
Example
Spotting the base case and the recursive case:
Output: complete Python program
def factorial(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case
else:
return n * factorial(n - 1)
print(factorial(5))
Fibonacci Sequence
A classic recursion example is the Fibonacci sequence. It begins with 0 and 1, and every later number is what you get by adding the two before it:
0, 1, 1, 2, 3, 5, 8, 13, and so on.
The sequence has no end, and the same addition rule applies all the way along.
With recursion, we can work out any chosen number in the sequence:
Example
Find the number at position 7 in the Fibonacci sequence, counting from 0:
Output: complete Python program
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(7))
Recursion with Lists
A list can be processed recursively by dealing with just one element on each call:
Example
Add up all the elements of a list:
Output: complete Python program
def sum_list(numbers):
if len(numbers) == 0:
return 0
else:
return numbers[0] + sum_list(numbers[1:])
my_list = [1, 2, 3, 4, 5]
print(sum_list(my_list))
Example
Find the largest value in a list:
Output: complete Python program
def find_max(numbers):
if len(numbers) == 1:
return numbers[0]
else:
max_of_rest = find_max(numbers[1:])
return numbers[0] if numbers[0] > max_of_rest else max_of_rest
my_list = [3, 7, 2, 9, 1]
print(find_max(my_list))
Recursion Depth Limit
Recursion in Python can only go so deep. By default, the limit is usually around 1000 recursive calls.
You can raise that limit if you need more depth, but doing so could crash your program.
So raise it with care, and for very deep recursion think about using iteration instead.
Example
Print the current recursion limit:
Output: complete Python program
import sys
print(sys.getrecursionlimit())
import sys
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())