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:

1. The return address is whatever called foo(5).
2. The return value is unknown, but it can be assumed it is at least 5 or more.
3. 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:

1. The return address is now foo(5), since it called foo(4).
2. The return value is unknown, but it can be assumed it is at least 4 or more.
3. 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

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 and y coordinates

end

the exit as x and y 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 and y coordinates

end

the exit as x and y 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 and y 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
}