In the Part 1 of this series, we set the tone for understanding recursion at a fundamental level. However, it would be nice to actually gain an intuition for practical problems that are easily solved by recursion and hardly solved otherwise.
In this part of the series, we will be solving an interesting problem with recursion. By the end of this series, you should have gained the following skills:
Identifying practical problems that can be solved by recursion
Computational thinking in a declarative manner
Identifying base and recursive cases for a given problem
The Problem
We are given an array of fixed-length strings which can be either an empty string or an x string which symbolises a wall. This data structure is illustrative of a maze where we have an entry and an exit. We are also given the entry point and the exist point. We are required to programmatically find the path from the entry point to the exit point and return it.
To help with incremental documentation, we will use Typescript to describe the structure of the data. Here is the function signature and expected output for the problem:
// denotes an index in a two dimensional array
type Point = {
x: number;
y: number;
}
function findPath(
maze: string[],
wall: string,
start: Point,
end: Point
): Point[] {}
const maze = [
"xxxxxxxxxx x",
"x x x",
"x x x",
"x xxxxxxxx x",
"x x",
"x xxxxxxxxxx",
];
const mazeResult = [
{ x: 10, y: 0 },
{ x: 10, y: 1 },
{ x: 10, y: 2 },
{ x: 10, y: 3 },
{ x: 10, y: 4 },
{ x: 9, y: 4 },
{ x: 8, y: 4 },
{ x: 7, y: 4 },
{ x: 6, y: 4 },
{ x: 5, y: 4 },
{ x: 4, y: 4 },
{ x: 3, y: 4 },
{ x: 2, y: 4 },
{ x: 1, y: 4 },
{ x: 1, y: 5 },
];
// there is only one path through
const result = findPath(maze, "x", { x: 10, y: 0 }, { x: 1, y: 5 });
// pseudo code
expect(result).toEqual(mazeResult);
The Solution
Before we dive into the code, we have to take note of some crucial things if we must solve the problem efficiently:
For every point in the maze, we need to visit all adjacent points (i.e we have to visit the point above, below and beside the current point) in order to determine the next valid step to take towards the end of the maze.
We need a way to traverse the maze without going in circles (i.e visiting places we have been to before). This prevents us from writing a non-terminating function.
Although not written in stone, it is usually best practice to write the recursive function as a helper function. It makes the code more readable as there are overarching concerns you would want to address in the top-level function, like the concerns we have above.
Bearing these concerns in mind, we can now write our solution.
function findPath(
maze: string[],
wall: string,
start: Point,
end: Point
): Point[] {
// In order to address the first concern, we need a way to navigate
// adjacent points from the current point. Here is a good technique.
// If you're familiar with CSS, this is akin to the margin CSS rule;
// margin: top right bottom left;
const adjacents = [[0, 1], [1, 0], [0, -1], [-1, 0]];
// To address the second concern, we need to keep track of points we
// have visited before. We can do this by using a data structure
// that contains a boolean in every point such that the value of a
// given point is set to True once we visit that point
const seen: boolean[][] =
Array.from(
{ length: maze.length },
// we ignore the first arg of the arrow function because
// it is always undefined and it's also not useful here
(_, i) => new Array(maze[i].length).fill(false)
);
const path: Point[] = [];
// To address the last concern, the recursive function will be a
// helper function which will take these variables as arguments
walk(maze, wall, start, end, seen, path, adjacents);
// JavaScript passes arrays by reference so we can count on the
// walk function to return the same path array we passed to it
return path;
}
We can now focus on the recursive helper function which finds the path from the start point to the end. We will walk through the code incrementally (pun intended😌) so that it will be easy to digest.
Like we covered earlier in the Part 1 of this series, we have to first address the base case(s) when writing a recursive function.
function walk(
maze: string[],
wall: string,
// in this context, the start point is our current point.
// this implies that we are going to change this point as we recurse
current: Point,
end: Point,
seen: boolean[][],
path: Point[],
adjacents: number[][]
): boolean {
// we want to stop recursing if we hit a wall
if (maze[current.y][current.x] === wall) {
return false;
}
// we want to stop recursing if we are out of bounds
if (
current.y < 0 || current.y >= maze.length ||
current.x < 0 || current.x >= maze[0].length
) {
return false
}
// we want to stop recursing if we have seen this point already
if (seen[current.y][current.x]) {
return false
}
// finally, we want to stop recursing if we've gotten to the end
if (current.y === end.y && current.x === end.x) {
// to make our solution correct, we need to add the current/end
// point to our path array.
path.push(current);
return true;
}
}
After addressing our base cases, we then enter the pre-recurse phase of the recursion. When the program gets here during execution, it means that none of the base cases were satisfied. We need to do some bookkeeping at this point because we are keeping track of the path as we progress to the next point.
We need to add the current point in the
patharray.We need to mark the current point as seen in the
seenarray.
function walk(
maze: string[],
wall: string,
// in this context, the start point is our current point.
// this implies that we are going to change this point as we recurse
current: Point,
end: Point,
seen: boolean[][],
path: Point[],
adjacents: number[][]
): boolean {
// ... base cases
// pre-recurse
path.push(current);
seen[current.y][current.x] = true;
}
We now get to the recursive case where we move to the next point. This is where we visit the adjacent points to the current point.
function walk(
maze: string[],
wall: string,
// in this context, the start point is our current point.
// this implies that we are going to change this point as we recurse
current: Point,
end: Point,
seen: boolean[][],
path: Point[],
adjacents: number[][]
): boolean {
// ... base cases
// ... pre-recurse
// recursive case
for (let i = 0; i < adjacents.length; i++) {
const [x, y] = adjacents[i];
// if any of the adjacent points represent the end point then
// we want to terminate the function here
if (walk(maze, wall, { x: current.x + x, y: current.y + y },
end, seen, path, adjacents)
) {
return true;
}
}
}
We then get to the post-recurse phase. When our program get to this phase during execution, it means none of the adjacents represent the end point. We also have to do some bookkeeping here but only to our path array.
function walk(
maze: string[],
wall: string,
// in this context, the start point is our current point.
// this implies that we are going to change this point as we recurse
current: Point,
end: Point,
seen: boolean[][],
path: Point[],
adjacents: number[][]
): boolean {
// ... base cases
// ... pre-recurse
// ... recursive case
// post-recurse
// while the call stack also keeps track of the path overall,
// we are only interested in that which directly leads to the
// end point hence we remove the walls that might have been added
// to the path array before moving to the next point
path.pop();
return false;
}
You can tell that this solution is quite declarative. We describe the desired state of our solution by relying on the mechanics of the call stack using recursion.
You can find the entire code written in Go, Python and Typescript in this Github Gist.
I hope you find this helpful in your quest to understand recursion and gain an intuition for when to make use of it. In Part 3 of this series, we will consider the performance implications of recursion and when to optimize it for better performance.