# Recursion

Useful when a normal loop approach does not work well. Especially if there is a branching factor.

1. Create a base case
2. recurse a. pre operation b. do recurse c. post operation

As you recurse you are placing functions on the stack who have a return address to the function above them that called them.

Biggest tip is to move everything you possibly can into the base case. Don't try and prevent function calls, just exit early in base case logic.

Example: Maze Solver

type Point = {
  x: number;
  y: number;
};

const directions = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];

function walk(
  maze: string[],
  wall: string,
  curr: Point,
  end: Point,
  seen: boolean[][],
  path: Point[],
): boolean {
  // Base Case
  // 1. Off the map
  if (
    curr.x < 0 ||
    curr.x >= maze[0].length ||
    curr.y < 0 ||
    curr.y >= maze.length
  ) {
    return false;
  }
  // 2. On a wall
  if (maze[curr.y][curr.x] === wall) {
    return false;
  }
  // 3. Already seen
  if (seen[curr.y][curr.x]) {
    return false;
  }
  // 4. At the end
  if (curr.x === end.x && curr.y === end.y) {
    // end point needs to be pushed in order for path to be complete
    path.push(end);
    return true;
  }

  // Recurse
  // 1. pre operation
  seen[curr.y][curr.x] = true;
  path.push(curr);
  // 2. do recurse
  for (let i = 0; i < directions.length; i++) {
    const [x, y] = directions[i];
    if (
      walk(
        maze,
        wall,
        {
          x: curr.x + x,
          y: curr.y + y,
        },
        end,
        seen,
        path,
      )
    ) {
      // exit because we found the end
      return true;
    }
  }
  // 3. post operation
  path.pop();
  return false;
}

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;
}