PythonRecursion
Recursion
Recursion is when a function calls itself.
Recursion is a common mathematical and programming concept. It means that a function calls itself. This has the benefit of meaning that you can loop through data to reach a result.
The developer should be very careful with recursion as it can be quite easy to slip into writing a function which never terminates, or one that uses excess amounts of memory or processor power. However, when written correctly recursion can be a very efficient and mathematically-elegant approach to programming.
Example
A simple recursive function that counts down from 5:
if n<= 0:
print("Done!")
else:
print(n)
countdown(n - 1)
countdown(5)
Base Case and Recursive Case
Every recursive function must have two parts:
- Abase case - A condition that stops the recursion
- Arecursive case - The function calling itself with a modified argument
Without a base case, the function would call itself forever, causing a stack overflow error.
Example
Identifying base case and recursive case:
# Base case
if n == 0 or n == 1:
return 1
# Recursive case
else:
return n * factorial(n - 1)
print(factorial(5))
The base case is crucial. Always make sure your recursive function has a condition that will eventually be met.
Fibonacci Sequence
The Fibonacci sequence is a classic example where each number is the sum of the two preceding ones. The sequence starts with 0 and 1:
0, 1, 1, 2, 3, 5, 8, 13, ...
The sequence continues indefinitely, with each number being the sum of the two preceding ones.
We can use recursion to find a specific number in the sequence:
Example
Find the 7th number in the Fibonacci sequence:
if n<= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(7))
Recursion with Lists
Recursion can be used to process lists by handling one element at a time:
Example
Calculate the sum of all elements in a list:
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 maximum value in a list:
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
Python has a limit on how deep recursion can go. The default limit is usually around 1000 recursive calls.
If you need deeper recursion, you can increase the limit, but be careful as this can cause crashes:
Example
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())
Increasing the recursion limit should be done with caution. For very deep recursion, consider using iteration instead.
