Recursion
The simplest way of thinking about recursion is a function that calls itself until the problem is solved. This usually involves what is refereed as a base case. The base cave is the point at which the problem is solved and recursion stops.
For example, this function foo()
takes a n
argument, and each time it calls itself, it add n-1
, until n
is 1
.
function foo(n: number): number {
// Base case
if (n === 1) {
return 1
}
// Recursion happens
return n + foo(n - 1)
}
const total = foo(5) // Result is 15
There are three values that can help visualize this a little more easily:
- rA
- return Address. When a function finishes its work, it needs to go back to the place where it was called, and return a value.
- rV
- return Value. The value that is actually returned when the function is over needs a space in memory.
- A
- Arguments. To pass values inside the function, some memory is allocated.
Now what happens when the previous function foo
is called with 5
as an argument is called:
- The return address is whatever called
foo(5)
. - The return value is unknown, but it can be assumed it is at least
5
or more. - The argument is
5
.
whatever called foo(5)
\
\ rA | rV | A |
|-------|\----|-----|---|
|foo(5) | | 5+ | 5 |
As the argument is not equal to 1
, the function will call itself again after decreasing the value of the argument by 1
:
- The return address is now
foo(5)
, since it calledfoo(4)
. - The return value is unknown, but it can be assumed it is at least
4
or more. - The argument is
4
.
The cycle continues to repeat itself until the argument is 1:
whatever called foo(5)
\
\ rA | rV | A |
|-------|\-------|------|---|
|foo(5) | | 5+ | 5 |
|foo(4) | foo(5) | 4+ | 4 |
|foo(3) | foo(4) | 3+ | 3 |
|foo(2) | foo(3) | 2+ | 2 |
|foo(1) | foo(2) | 1 | 1 |
Now that the argument is equal to 1 and returns 1, the addition of return n + foo(n - 1)
can actually happen, from the bottom to the top of the stack of foo()
executions:
whatever called foo(5)
\
\ rA | rV | A |
|-------|\-------|------|---|
|foo(5) | | 5+10 | 5 |
|foo(4) | foo(5) | 4+6 | 4 |
|foo(3) | foo(4) | 3+3 | 3 |
|foo(2) | foo(3) | 2+1 | 2 |
|foo(1) | foo(2) | 1 | 1 |
Knowing all this, a recursive function can be broken into 3 steps:
- 1.
pre
- doing something before the recursion. In the example before:
n +
. - 2.
recurse
- calling the function. In the example before:
foo(n - 1)
- 3.
post
- doing something after the recursion. Not in the example.
Example: doing something before returning the value of the recursion.
function foo(n: number): number {
if (n === 1) {
return 1
}
const out = n + foo(n - 1) // pre + recursion
console.log(n) // post
return out
}
const total = foo(5) // Result is 15
Exercise: Maze Solver
Using recursion, find the exit in a maze made with a two-dimensional array and return the path used.
Theoretical approach
The maze is a square, with an entry and an exit:
↑
xxxxxxxxxx x
x x x
x x x
x xxxxxxxx x
x x
x xxxxxxxxxx
↑
We can move in four directions: up, right, down, left.
↑
← ♜ →
↓
But these movement options can create issues:
- Going off the map
- Hitting a wall
- Finding the exit
- Retracing one's steps
Those issues need to be used as the base cases. If the program detects them, it should not try to move in the incoming direction, and try another direction.
Code implementation
The main function takes four arguments that serve to describe our maze and its working conditions:
maze
- the actual two-dimensional array representing the maze
wall
- the character that designates a wall (ex:
*
) start
- the starting position as
x
andy
coordinates end
- the exit as
x
andy
coordinates
And looks like this:
export default function solve(
maze: string[],
wall: string,
start: Point,
end: Point): Point[] {}
Avoid errors for base cases
A walk()
function is created, which returns a boolean and uses those arguments:
maze
- the same two-dimensional array representing the maze
wall
- the same character that designates a wall (ex:
*
) curr
- the current moving position of the function as
x
andy
coordinates end
- the exit as
x
andy
coordinates seen
- a two-dimensional array of booleans informing if the position was already visited
The base cases are added before handling recursion:
function walk(maze: string[], wall: string, curr: Point, end: Point, seen: boolean[][]): boolean {
// Off the map
if (curr.x < 0 || curr.x >= maze[0].length || curr.y < 0 || curr.y >= maze.length) {
return false
}
// Hit a wall
if (maze[curr.y][curr.x] === wall) {
return false
}
// Found the exit
if (curr.x === end.x && curr.y === end.y) {
return true
}
// Avoid retracing one's steps
if (seen[curr.y][curr.x]) {
return false
}
}
Build the path with recursion
A new argument is added:
path
- an array of
x
andy
coordinates that retraces all successful movements and allows to retracce the path
First, add the current position inside the path before recursion, and remove the last item of the path if the recursion finishes, as it means the path employed was not the right one.
function walk(maze: string[], wall: string, curr: Point, end: Point, seen: boolean[][], path: Point[]): boolean {
// ... previous base cases
// Pre
seen[curr.y][curr.x] = true
path.push(curr)
// Recurse
// Post
path.pop()
return false
}
Then, create an array of directions (left, right, down, up) that will be used to move inside the maze:
const dir = [
[-1, 0],
[1, 0],
[0, -1]
[0, 1]
]
Then, loop over each direction to test if it's allowed to move, and if walk()
returns true, it means the exit has been found:
// Recurse
for (let i = 0; i < dir.length; i++) {
const [x, y] = dir[i]
if (walk(maze, wall, { x: curr.x + x, y: curr.y + y }, end, seen, path)) {
return true
}
}
The base case for finding the exit returns true, which means the recursion with the last position is not registered inside the path. To add it:
// Finding the exit
if (curr.x === end.x && curr.y === end.y) {
.push(end)
return true
}
Finally, create the seen as the maze with values of false
, then use the walk()
function, in the main function:
export default function solve(maze: string[], wall: string, start: Point, end: Point): Point[] {
const seen: boolean[][] = []
const path: Point[] = []
for (let i = 0; i < maze.length; i++) {
seen.push(new Array(maze[0].length).fill(false))
}
walk(maze, wall, start, end, seen, path)
return path
}
The completed exercise:
const dir = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1]
]
function walk(maze: string[], wall: string, curr: Point, end: Point, seen: boolean[][], path: Point[]): boolean {
// 1. Base cases
// Off the map
if (curr.x < 0 || curr.x >= maze[0].length || curr.y < 0 || curr.y >= maze.length) {
return false
}
// Hit a wall
if (maze[curr.y][curr.x] === wall) {
return false
}
// Finding the exit
if (curr.x === end.x && curr.y === end.y) {
path.push(end)
return true
}
// Avoid retracing one's steps
if (seen[curr.y][curr.x]) {
return false
}
// 2. Recursion
// Pre
seen[curr.y][curr.x] = true
path.push(curr)
// Recurse
for (let i = 0; i < dir.length; i++) {
const [x, y] = dir[i]
if (walk(maze, wall, { x: curr.x + x, y: curr.y + y }, end, seen, path)) {
return true
}
}
// Post
path.pop()
return false
}
export default function solve(maze: string[], wall: string, start: Point, end: Point): Point[] {
const seen: boolean[][] = []
const path: Point[] = []
for (let i = 0; i < maze.length; i++) {
seen.push(new Array(maze[0].length).fill(false))
}
walk(maze, wall, start, end, seen, path)
return path
}
Generated: November 14th, 2022