Recursion in Functional Programming

Recursion is a technique where a function calls itself. In Jurassic Park, recursion is like exploring the genealogical tree of dinosaurs - to learn the full lineage of a species, you must go back generation by generation until you reach the oldest ancestor.

Basics of Recursion

Every recursive function needs two elements:

1. Base case - the condition that stops the recursion
2. Recursive case - the function call with a simplified problem

1// Classic example - factorial
2function factorial(n) {
3  // Base case
4  if (n <= 1) return 1;
5  // Recursive case
6  return n * factorial(n - 1);
7}
8
9factorial(5); // 5 * 4 * 3 * 2 * 1 = 120
10
11// Visualization of calls:
12// factorial(5)
13//   5 * factorial(4)
14//     4 * factorial(3)
15//       3 * factorial(2)
16//         2 * factorial(1)
17//           return 1     <- base case
18//         return 2
19//       return 6
20//     return 24
21//   return 120

Recursion with Tree Structures

Recursion is natural when processing tree data structures - like a species hierarchy:

1const dinoTaxonomy = {
2  name: 'Dinosauria',
3  children: [
4    {
5      name: 'Saurischia',
6      children: [
7        { name: 'Theropoda', children: [
8          { name: 'T-Rex', children: [] },
9          { name: 'Velociraptor', children: [] },
10        ]},
11        { name: 'Sauropoda', children: [
12          { name: 'Brachiosaurus', children: [] },
13        ]},
14      ],
15    },
16    {
17      name: 'Ornithischia',
18      children: [
19        { name: 'Triceratops', children: [] },
20        { name: 'Stegosaurus', children: [] },
21      ],
22    },
23  ],
24};
25
26// Recursive tree search
27function findSpecies(node, target) {
28  if (node.name === target) return node;
29  for (const child of node.children) {
30    const found = findSpecies(child, target);
31    if (found) return found;
32  }
33  return null;
34}
35
36findSpecies(dinoTaxonomy, 'Velociraptor');
37// { name: 'Velociraptor', children: [] }

Recursion vs Iteration

In FP, recursion replaces loops. Every loop can be written recursively:

1// Iteration - summing an array
2function sumIterative(arr) {
3  let total = 0;
4  for (const num of arr) {
5    total += num;
6  }
7  return total;
8}
9
10// Recursion - summing an array
11function sumRecursive(arr) {
12  if (arr.length === 0) return 0;
13  const [head, ...tail] = arr;
14  return head + sumRecursive(tail);
15}
16
17// Both give the same result
18const weights = [8000, 150, 56000, 2500];
19sumIterative(weights); // 66650
20sumRecursive(weights); // 66650

Tail Call Optimization

Recursion can lead to stack overflow with deep calls. Tail recursion solves this problem:

1// Regular recursion - each call waits for the result of the next
2function factorialNormal(n) {
3  if (n <= 1) return 1;
4  return n * factorial(n - 1); // must wait for the result
5}
6
7// Tail recursion - accumulator carries the result
8function factorialTail(n, accumulator = 1) {
9  if (n <= 1) return accumulator;
10  return factorialTail(n - 1, n * accumulator); // last operation
11}
12
13// Practical example - flattening a nested structure
14function flattenDeep(arr, result = []) {
15  for (const item of arr) {
16    if (Array.isArray(item)) {
17      flattenDeep(item, result);
18    } else {
19      result.push(item);
20    }
21  }
22  return result;
23}
24
25const nested = [['Rex', ['Blue', 'Charlie']], 'Brachio', [['Stego']]];
26flattenDeep(nested);
27// ['Rex', 'Blue', 'Charlie', 'Brachio', 'Stego']