Recursion is a process where a function calls itself directly or indirectly. It is a powerful programming technique which makes it possible to express operations in terms of themselves.
Recursion like loops, allows us to achieve repetition, however, the internal working between loops and recursion is entirely different.
In Python, a function is recursive if it is defined to call itself either directly or indirectly through another function within its body. Well, what does that mean ?, let me start by showing you a bad example to demonstrate recursion:
def func():
func()
The reason why the above is a bad example is because if you run the above function it would never terminate normally . I only wanted to show you what we mean by a function calling itself. The closest thing to the above example is an infinity loop.
Indirect recursion is when a function is called by another function within its body, example:
def func1():
#statements
func2()
def func2():
#statements
func1()
func1()
Define recursive functions that terminate
We will start with a working example before describing what is going on.
The factorial of a given number is the product of all positive integers less than or equal to the given number. For example, the factorial of 5
is 5 x 4 x 3 x 2 x 1 = 120
. You should note that we can find the factorial of 5
by multiplying the factorial of 4
by 5
i.e 5 x (4 x 3 x 2 x 1) = 5 x 24 = 120
, in the same way that we can find the factorial of 4
by multiplying the factorial of 3
with 4
i.e 4 x (3 x 2 x 1) = 4 x 6 = 24
, and so on. Recursive functions utilize the same principle in order to compute a value cumulatively from smaller solutions.
The following function shows a recursive function to calculate the factorial of a number:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
print(factorial(5))
The Base Case
First and foremost, all recursive functions should have a base case in order for the function to terminate. The base case is the simplest case of a given problem that can be used as the starting point for an inductive argument, it is responsible for the function's termination.
During each recursion trace, the function advances closer and closer to the base case, until the base case is met stopping the recursion. Any recursive function which does not define a base case will not terminate normally. In our previous example, the base case is met when the value of n
becomes 0
.
To understand better how recursive functions work, you first need to be conversant with how functions work at low-level. Whenever a function is called in Python, a stack frame is created in the memory to store the parameters and local variables of the function. When the function returns, the stack frame is removed from the memory. Recursive functions work in a similar way, except they don't get removed from the stack after they return. Instead, they stay on the stack until their recursive calls have finished executing. Whenever a recursive call is made, a new stack frame is added to the stack, until all the recursive calls have finished and the initial call can be resolved. This keeps happening until the base case of the function is reached and the stack frames can be popped off one by one.
The following image demonstrates the recursion trace for the factorial function:
Recursion in the Fibonacci sequence
The Fibonacci series is a sequence of numbers in which each number is the sum of the two preceding numbers, starting from 0
and 1
. So the first few numbers in the series are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
The following is a recursive function to get the nth number in the Fibonacci series:
def fibonacci(n):
if n <= 1:
return n
else:
return( fibonacci(n-2) + fibonacci(n-1))
print(fibonacci(1))
print(fibonacci(4))
print(fibonacci(7))
In the above case, the base case is reached if n is less than or equal to 1.
The following example demonstrates the recursion trace for Fibonacci function with n as 5:
Use recursion to detect palindromes
A palindrome is a word or phrase that is the same forward as it is backward. Meaning that if the word or phrase is read from left to right, the same sequence of letters and words appears from right to left as well. Some examples of palindromes include "racecar", "madam", "level", etc.
The following example uses recursion to tell whether a word is a palindrome or not, it returns True
if so and False
otherwise.
Use recursion to detect palindromes
def is_palindrome(word):
if len(word) <= 1:
# Base case
return True
if word[0] != word[-1]:
#Another Base case
return False
# Recursive call
return is_palindrome(word[1:-1])
# Tests
print(is_palindrome('racecar'))
print(is_palindrome('wow'))
print(is_palindrome('level'))
print(is_palindrome('hello'))
The is_palindrome()
function above takes a single string argument and checks if it is a palindrome. It starts with two base cases. If the length of the word is less than or equal to 1, then it is a palindrome. If the first letter of the word is not equal to the last letter, then it is not a palindrome. For all other words, it checks if the first and last letters are equal and then calls itself with the word to repeat the process. The word argument is sliced to omit the first and last characters on each recursive call until either of the base cases is reached.
Recursion for traversing irregularly nested sequences
In cases where we are traversing a sequence, loops such as for and while
work well when the level of nesting in the sequence is regular, for example we can use nested for loop to traverse a regularly nested list such as [[1, 2], [3, 4], [5, 6, 7], [ 8, 9], [10, 11]]
use for loop to traverse a regularly nested list
L = [[1, 2], [3, 4], [5, 6, 7], [ 8, 9], [10, 11]]
for i in L:
for j in i:
print(j)
However, when the level of nesting becomes slightly irregular it becomes almost impossible to use loop in traversing the sequence. For example in
[[[1, 8, 9], [4, 6], [3, 2, 5]], [[7, 0], [4, 2, 6], [1, 3, 9]]]
.
This is one area where recursive functions triumph over loops.
def myfunc(lst):
for element in lst:
if isinstance(element, list):
#the recursive call
myfunc(element)
else:
print(element)
my_list = [[[1, 8, 9], [4, 6], [3, 2, 5]], [[7, 0], [4, 2, 6], [1, 3, 9]]]
myfunc(my_list)
The function iterates through each element, if the element is a list, it calls itself recursively, if the element is not a list, it prints out the element.
Maximum Recursion Depth
Maximum recursion depth is the maximum number of times a function can call itself before Python raises a RecursionError
. The default recursion limit in Python is usually set to 1000, but this limit can be updated depending on the needs of the program.
Typically, when a recursive function is called without a base case, it will keep calling itself until the maximum recursion depth is reached.
def func():
func()
func()
We can use the sys.getrecursionlimit()
function to check the current maximum recursion depth.
import sys
print(sys.getrecursionlimit())
To increase or decrease the limit, we can use sys.setrecursionlimit()
function with the prospective limit as the argument. Example:
import sys
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())
2000
However, it is not recommended to set the recursion limit too high as it can lead to stack overflow errors and cause your program to crash. Instead, you write your code in a way that avoids deep recursion if possible, or use other techniques such as iteration.
Common Uses of Recursion
Some computational tasks are naturally solved better using recursion. Some common such tasks includes:
-
Sorting Algorithms: Recursion is commonly used to implement sorting algorithms such as quicksort, merge sort and heap sort.
-
Search Algorithms: Recursive algorithms are often used to solve problems involving searching such as the binary search algorithm.
-
Tree Traversals: Recursion is widely used to traverse through the nodes in a tree structure.
-
Graph Algorithms: Recursive algorithms are used to solve graph problems such as depth-first search and breadth-first search.
Implementations of the above algorithms is beyond the scope of this article.
Downsides of using recursion
While recursion can be an efficient and powerful way of solving certain types of problems , it does have a large resource footprint. It requires creating a 'stack' of all the recursive calls, which requires additional memory and processor time. Recursive algorithms also tend to take up more memory as compared to iterative algorithms that solve the same problem. It is, therefore, a good programming practice to avoid using recursion in cases where it would be more straightforward to use loops. For example, the following is a recursive function to print integers from 1 to integer i:
def printNums(i):
if i == 0:
return
printNums(i-1)
print(i)
printNums(9)
Using recursion in cases like the one shown above is unnecessarily complex, and should be avoided.
Apart from being memory intensive, other downsides of recursion includes:
-
Recursive algorithms are often slower than iterative ones due to the extra overhead of saving and restoring states from the call stack.
-
Recursive solutions can be difficult to understand.
-
Risk of exceeding the maximum recursion depth.
-
Recursion can be difficult to debug and trace.