# 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.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

`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.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.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.length).fill(false))
}

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

return path
}
``````

Initially published: November 14th, 2022
Generated: November 14th, 2022