What is a recursion? Why and when use a recursion? How to write recursive function easily? Take this in control!

Recursion is when type is defined by itself.

OK, let's proceed to another topi-... What, what do I hear? Not extensive enough? Right!

## What is recursion?

Recursion is when a type is defined by itself.

OK, let’s proceed to another topi-… Wait, what was that? That explanation wasn’t extensive enough? Right! Ok then, let’s expand a little…

When talking about recursions, people usually mean either recursive type or recursive function (which calls itself in its body). We’ll focus mostly on recursive functions here.

Let’s start with the loop. Everybody knows that loop means “execute a set of operations the given number of times, N.”

Now take a look at recursion. A function is a set of operations, and if the function calls itself, then the function is recursive. Therefore, we execute a set of operations a given number of times. The number of “iterations”, N, is defined by the “recursion base”, which is a condition branching into case without recursion, which effectively stops the function execution.

These definitions of loop and recursion basically overlap. This somehow shows that each loop can be implemented as recursion, and vice-versa.

## When to use recursion?

When I ask this question in tech interviews, I usually receive the answer: tree traversing (sometimes Fibonacci sequence). While this answer is correct, it doesn’t explain *why* the recursion is more intuitive than using a loop for the same purpose.

A more generalized answer would introduce the definition of sequence (which is recursive in case of Fibonacci sequence) or recursive types (like in case of a tree). Let’s take a look at the latter:

```
interface Node<T> {
nodes: Node<T>[];
value: T;
}
```

We defined `Node`

type which holds the value of type T, and a reference to child nodes (nodes by themselves). This is a typical tree structure from which we can travel from root to child node using recursive function:

```
/** Aggregate values of nodes in a tree */
const aggregateValues = <T>(node: Node<T>): T[] => [
node.value
...node.nodes.map(n => aggregateValues(n)), // no recursion base, because `map` has it's natural base (not executed callback for empty array)
];
```

So it looks like the recursive way is a one-liner. Let’s take a look at loop implementation:

```
/** Aggregate values of nodes in a tree */
const aggregateValues = <T>(rootNode: Node<T>): T[] => {
const result: T[] = [];
let nodes = [rootNode];
while(nodes.length !== 0) {
result.push(...nodes.map(n => n.value));
const nextNodes = nodes.flatMap(n => n.nodes);
nodes = nextNodes;
}
return result;
}
```

For starters, loop implementation is much more complicated, because it has to **track intermediate values**, that are processed. It’s fairly typical for imperative solutions. Regarding complexity they are exact (each node is accessed only once). The recursive function may reach the maximum call stack size exceeded problem (just like any recursive function in languages, that don’t have tail recursion).

We proved that for recursive types, it’s nice to have a recursive function, because they naturally match each other. We’ll talk more about examples later on.

Since loops and recursion are interchangeable, **the best answer** to *“When to use recursion?”* would be:

Use recursion whenever it’s more readable than loop, and use loop whenever it’s more readable than recursion. The definition of “readable” depends on the code being written (sometimes a certain function can be treated as a black box, and then it doesn’t matter), and team familiarity with recursion. Recursion tends to be more declarative and readable when used with recursive types and definitions, but this isn’t a golden rule. People are taught using loops from the beginning of their career, which is why loops are more natural to them, but it’s only a matter of a habit.

At some point in my life, when I got used to recursion, it became **more natural** to me to solve problems than with old-school loops. For me, recursion is more *sexy*.

## When not to use recursion?

The primary problem with recursion is its inability to track state because usually recursive functions are stateless (due to each execution being scoped). This implies passing an intermediate state as function parameters, which clutters the solution and makes function’s API dirty, which we will see later in examples.

If there is an absolute need for a set of operations to be stateful, then the recursion is probably not a good idea.

During (self) code reviews, I’ve often asked myself how a person without recursion experience will read the function, and if the implementation would be clear for them. More than once the answer was “just rewrite this using loop…”, even if I preferred recursion better. After all, **it’s more important** to leave code readable to others than to ourselves.

## Why to practice recursion?

Recursion is just another tool in a programmer’s tool belt. It is also a great mind exercise, which may improve abstract thinking in more obvious situations, and lead to better skills in solving algorithms or writing clearer code.

## How to practice recursion?

Since any loop can be replaced with recursion, the best way to learn it would be to throw away all the loops and solve everything with recursion. It will be problematic at the beginning, but a few nice exercises given at the end of this article should speed up the learning process of how to do this.

You don’t need to publish the recursive implementation to a code review if you have time to rewrite the solution to loop before actually submitting it.

### Practice – forEach

Let’s take a look at `Array.prototype.forEach`

function, and reimplement that (the basic usage only, with first argument present). It takes an array, a callback, and calls the callback once for each item in the array, passing this item as the callback’s argument.

The first thing we need to do is to determine whether the function can be recursive. My definition above says:

execute some set of operations some number of times N

`forEach`

executes some set of operations (calls a callback) some number of times N (where N = array.length). It seems, that it can be written using recursion.

First thing we want to do is **finding repetitive pattern**:

- Call callback for first item in array
- Call callback for second item in array
- Call callback for third item in array
- …

Hm… not very repetitive. Let’s change the approach:

- Take array’s first item, and “rest” as a new array
- Call callback for first item.
- Take array’s (previous rest) first item, and “rest” as a new array
- Call callback for first item.
- Take array’s (previous rest) first item, and “rest” as a new array
- …

Now that’s better! Taking the “first” item from the list and leaving the rest for later is a very common approach in recursive functions. It’s so common, in fact, that it’s supported as pattern matching destruction in Haskell and many functional languages.

The second thing we need to take care of is the **recursion base**. In this case, we want to stop executing whenever the array we process is empty (**because we cannot take the first item from an empty array**).

On to the implementation:

```
const forEach = <T>(array: T[], cb: (v: T) => void): void => {
// Recursion base
if (array.length === 0) {
return;
}
// Taking first item, and "rest" from array
const [first, ...rest] = array;
// Executing callback on first item
cb(first);
// Processing "rest" in a loop - if rest is empty, then it will hit base in next iteration
forEach(rest, cb);
}
```

This implementation lacks side effects and doesn’t modify any variables. Therefore, it can be read entirely from top to bottom without remembering any intermediate state. Remember, functions without an intermediate state are *sexy*.

### Practice – map

Use the procedure:

**Can map be recursive?**Yes, for the same reason`forEach`

can.**What is a repetitive pattern?**The same as in`forEach`

, but value returned from callback needs to be returned as map result.**What is a recursion base?**Empty input array should stop recursion.**What is an expected result of recursion base?**If we receive empty array as input, we want to return empty array, because there was nothing to iterate over.

**Hint**: Writing types first is very helpful in determining point 4., and keeping implementation in-place.

```
const map = <T, P>(array: T[], cb: (v: T) => P): P[] => {
// Recursion base
if (array.length === 0) {
return [];
}
// Taking first item, and "rest" from array
const [first, ...rest] = array;
return [
// Executing callback on first item
cb(first),
// Processing "rest" in a loop - if rest is empty, then it will hit base in next iteration
...map(rest, cb), // spread operator flattens result, and joins it with result of cb(first)
];
}
```

Therefore for identity callback (which returns unchanged input: `const id = a => a`

):

Iteration | Input | First | Rest | Result |
---|---|---|---|---|

1 | [1,2,3,4] | 1 | [2,3,4] | [1, …map([2,3,4])] |

2 | [2,3,4] | 2 | [3,4] | [1, 2, …map([3,4])] |

3 | [3,4] | 3 | [4] | [1, 2, 3, …map([4])] |

4 | [4] | 4 | [] | [1, 2, 3, 4, …map([])] |

5 | [] | x | x | x |

Which finalizes with `[1, 2, 3, 4, ...([])]`

(recursion base), which is simply `[1,2,3,4]`

.

As a bonus, let’s take a look at language which is much better suited for writing recursive functions. Since in Haskell there are no loops, all problems need to be solved using recursion. Language provides utilities to work with: pattern matching and destruction. Map implementation in Haskell would look like this:

```
-- type definition
map :: (a -> b) -> [a] -> [b]
-- recursion base - pattern matching for empty array
map cb [] = []
-- `:` operator normally joins item and list
-- here it can be used to extract first item from array
map cb (first : rest) = cb first : map cb rest
```

### Practice – map with index

Wait, whoa! But `Array.prototype.map`

passes the currently processed index as the callback’s second argument! That’s right, I avoided this implementation detail because that’s one of the pitfalls of recursive functions. Since by default we avoid an intermediate state, it becomes bothersome to suddenly start working with state.

For recursive `map`

, there is no difference between processing original input array, and some array with few items already processed. Therefore there is no way to determine on which position of original array we are.

This usually is overcome by passing the intermediate state as the second argument. Normally, this pollutes function API, so it’s good habit to adopt to create some internal `process`

function like so:

```
const map = <T, P>(originalArray: T[], cb: (v: T, i: number) => P): P[] => {
const process = (array: T[], index: number) => {
if (array.length === 0) {
return [];
}
const [first, ...rest] = array;
return [
cb(first, index),
...process(rest, index + 1),
];
}
return process(originalArray, 0);
}
```

I think that this is the moment when using recursive implementation should be reconsidered. The function has already become complicated, and a for-loop implementation may be better because it has state built-in.

My personal opinion though is that `map`

function should not support `index`

. If callback needs `index`

for whatever, then probably it should not use `map`

at all, but some other dedicated function (like `times`

with number of iterations to perform).

For fun: using a clever technique we can “cleanup” this implementation by playing with the execution order (iterate items from last):

```
const mapRight = <T, P>(array: T[], cb: (v: T, i: number) => P): P[] => {
if (array.length === 0) {
return [];
}
const [rest, [last]] = [array.slice(0, -1), array.slice(-1)];
return [
cb(last, rest.length),
...mapAndReverse(rest, cb),
];
}
```

## Summary before exercises

- Loop is a tool
- Recursion is a tool
- Any loop can be replaced by recursion, any recursion can be replaced by loop
- Recursion is sometimes more readable than loop, and loop is sometimes more readable than recursion
- Recursion doesn’t play good if there is an intermediate state, that has to be tracked
- Recursion tends to be better for work with recursive types, and writing types first helps with implementing recursion
- Recursion requires some practice to be easy to write and read
- Recursion tends to be more declarative, but it’s not a value by itself
- It’s best if recursion is a pure function (doesn’t modify variables outside of its scope, and doesn’t rely on non-const values outside of its scope), otherwise the code will be dirty
- Think before writing recursion: find repetitive pattern, find recursion base and its return value,
**ask yourself how to join this processing result with next recursion result**. And you are done.

### Exercises

Each exercise will challenge your mind to think in a recursive way. Sometimes finding recursive pattern may be really hard, but don’t give up. As I’ve already said – it can learned by practice.

- Reimplement
`Array.prototype.reduce`

(without index support) - Implement
`times(n: number, cb: (n: number) => void) => void`

function which executes given callback N times, passing current iteration as argument. - Implement
`isEven(n: number) => boolean`

which verifies whether the number is even or not. It should support natural numbers without support for zero. - Implement
`fibonacci(n: number) => number[]`

which returns list of N numbers from Fibonacci sequence (e.g. for N = 4 it would return [1, 1, 2, 3]) - Implement
`pascal(n: number) => number[]`

which returns N’th row from Pascal triangle. Hint: Pascal triangle definition is recursive

Next, compare your solutions with solutions, that are allowed to use loop.

Author: Mateusz Koteja