What is Recursion?
You can think of recursion as breaking something down into smaller, simpler parts. We recurse something when we apply the same function to an even simpler case. You can think of this as a function that calls itself. A really famous example of recursion is the Mandelbrot Set
This looks a bit psychedelic, I know! But as you see here, as we keep on zooming into the picture, we see that the original base image is composed of thousands of miniature function calls, and each of those function calls has its own thousand + function calls. There is a lot of complexity when it comes to this image!
But now onto the important stuff… How do we implement recursive functions in python?
Function Architecture
Before writing any code, let’s start with some pseudocode of the architecture of a basic recursive function.
def recursiveFunction(inputParam):
# Base case. If this case is met, we then break out of the function and return
if(base case is met):
return
# Write the function call
change the inputParam such that eventually, the base case will be met
recursiveFunction(inputParam)
Function Examples
Now, let’s see how we can actually implement a recursive functions
def recursiveElimination(inputNum):
#our base case
if(inputNum == 0):
return
print(inputNum)
inputNum -= 1
recursiveElimination(inputNum)
# Call the function
recursiveElimination(10)
10
9
8
7
6
5
4
3
2
1
We can see how this function has similar output as a for loop. The beauty of this is that every for loop can be written recursively. For simple problems like this, the time complexity of both the for loop and a recursive function are the same. However, with more advanced algorithms and functions, recursion really does reduce the time complexity!
Let’s look at how we can recursively eliminate the last 5 elements of a list.
numTracker = 5
myList = [500 , 400 , 300 , 1000 , 400 , 700 , 450]
def listRecursiveElimination(numTracker, inputList):
# Base case. We also check that the inputList is not empty
if(numTracker == 0 or len(inputList) == 0):
return
# Do the elimination
inputList.pop(len(inputList) - 1)
print(inputList)
# increment our counter
numTracker -= 1
# call the function again
listRecursiveElimination(numTracker , inputList)
listRecursiveElimination(numTracker , myList)
[500, 400, 300, 1000, 400, 700]
[500, 400, 300, 1000, 400]
[500, 400, 300, 1000]
[500, 400, 300]
[500, 400]
This sort of list elimination function forms the foundation of a popular machine learning method called Recursive Feature Elimination.
Recursive Backtracking
Recursive backtracking is an exhaustive method that has the computer attempt many different solutions. If it reaches a dead end, then it backtracks or goes back to a previous state. A good analogy is imagine yourself stuck in a maze. You may pursue one path, but then realize you’re at a dead end. What you then do is backtrack, or retrace your steps, to a prior fork in the maze, where you then take a different turn instead of the turn that led to a dead-end.
Recursive Backtracking in a Maze
This function here will show you how to use backtracking to solve a maze problem using the same logic we discussed above. First, let’s write some pseudocode.
# Our base Case
If the final destination is reached:
print the solution matrix with our path
Else
1. Mark the current index of our matrix as 1. This means that we have visited this index and that it is part of the solution path.
2. Move forward in the horizontal direction (to the right of our current index) Recursively check if this move leads to a solution.
3. If the horizontal moves don't lead to a solution, then try moving down and again recursively check if this new move leads to a solution.
4. If neither these horizontal nor vertical moves lead to a solution, then we know that the index we are at is not part of the solution path. We then mark this index as being 0. This means it is not a part of the solution path.
Now that we have our pseudocode, let’s actually set up our algorithm. We first should initialize our maze matrix. In this maze, 0s represent walls and 1s represent clear areas that we can walk through.
# This is the maze size. We will always be working with square mazes, so N represents both the height and width of the maze
N = 4
maze = [ [1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1] ]
Note that the end of the maze (final destination) is defined as the index at the lowermost right corner. If there is a solution to the maze, it will always be 1.
Now, let’s write a helper function that will print our solution.
def printSolMatrix( sol ):
# A nested for loop
for i in sol:
for j in i:
print(str(j) + " ", end = "")
print("")
We also will include a helper function that will check for edge cases such that we avoid index out of bound errors. It also checks if the index is a part of the path (i.e. maze[x][y] == 1)
def isValidIndex(maze , x , y):
if x >= 0 and x < N and y >= 0 and y < N and maze[x][y] == 1:
return True
return False
Now we can write our function. We will also include a recursive helper function, as we don’t want our entire parent function to be recursed over.
#This is our main function for solving the maze
def mazeSolver(maze , N):
#begin by initializing an N*N matrix of 0s. This is our initial condition.
sol = [ [ 0 for j in range(N) ] for i in range(N) ]
if mazeSolverHelper(maze , 0 , 0 , sol, N) == False:
print("Sorry there was no solution")
return False
printSolMatrix( sol )
return True
#Our helper function
def mazeSolverHelper(maze , x , y , sol , N):
#We have reached our destination index (This is the lowermost right corner index)
if x == N - 1 and y == N - 1:
sol[x][y] = 1
return True
# Now first check if the point we are at is validate
if isValidIndex(maze , x , y) == True:
#Gamble that the current index is part of the solution. So set it equal to 1.
sol[x][y] = 1
#Check the horizontal direction and recurse
if mazeSolverHelper(maze , x + 1 , y , sol , N) == True:
return True
#If increasing x does not yield a solution, the increase y.
if mazeSolverHelper(maze, x, y + 1, sol , N) == True:
return True
# The default case is to backtrack and mark our point if both recursing horizintally and vertically don't work!
sol[x][y] = 0
return False
Now let’s put our algorithm into action!
#Make a maze
N = 4
maze = [ [1, 0, 1, 0],
[1, 1, 1, 1],
[0, 1, 0, 1],
[1, 1, 1, 1] ]
mazeSolver(maze , N)
We then get an output with our solution:
1 0 0 0
1 1 1 1
0 0 0 1
0 0 0 1
Note that this algorithm can yield many alternative solutions depending on the initial maze condition.
Sudoku Solver Assignment
You can click on the button below to complete an assignment related to building a Sudoku solver using a recursive backtracking algorithm. It’s been set up for you. Solutions for this assignment are posted!