Kevin De Baerdemaeker

Recursion

Modified 2023-07-23

Recursion is important to understand for some of the more complex data structures. Rules to understand recursion:

  1. develop a solid base case base case, before even thinking about the recursive one (really important!!) => stops the recursion
  2. then you implement the recursive step, which includes 3 phases
    pre

    the code ran before calling the recursive call, that isn't part of the base case

    recursive call

    calling the function recursively

    post

    the code ran after, when the recursion starts unrolling again

Typescript

Recursion is usually explained when calculating factorial, but the example too simple. Better with maze solver. 

XXXXXXXXEXXXX
X        XXXX
XSXXXXXXXXXXX

Base Case

  1. it's a wall => invalid state
  2. out of bounds => invalid state
  3. it's the end => valid state
  4. seen the tile before => invalid state

Recursive Case

Checking every direction

Code

const dir = [
    [0, 1], // top
    [1, 0], // right
    [0, -1], // down
    [-1, 0] // left
]

function walk(pos: Point, maze: string[], wall: string, end: Point, seen: boolean[][], path: Point[]): boolean {
    // base case
    if (pos.x < 0 || pos.x >= maze[0].length || // string.length
        pos.y < 0 || pos.y >= maze.length) {
        return false
    }
    if (maze[pos.y][pos.x] == wall) return false
    if (pos.x == end.x && pos.y == end.y) {
        path.push(end) // the last tile doesn't get added by the pre-step, since the recursion
        // unrolls before it can push the lost value
        return true
    }
    if (seen[pos.y][pos.x]) return false

    // recursive case
    // 1. pre => reaching this point means the point is valid
    seen[pos.y][pos.x] = true
    path.push(pos)

    // 2. recurse => look for a new direction
    for (let i = 0; i < dir.length; i++) {
        const [x, y] = dir[i]
        if (walk({
            x: pos.x + x,
            y: pos.y + y
        }, maze, wall, end, seen, path)) {
            return true
        }
    }

    // 3. post => reaching this, after recursion unrolls, means the base case was hit
    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 = 1; i < maze.length; ++i) {
        seen.push(new Array(maze[0].length).fill(false))
    }

    walk(start, maze, wall, end, seen, path)
    return path
}

References