Recursion in Functional Programming

The dinosaur taxonomy is a tree: Dinosauria split into two great groups, those into smaller ones, and species hang at the ends of the branches. You do not know in advance how many levels such a tree has, so you do not know how many loops to nest. What you need is a function that handles one node and deals with its children by calling itself.

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

Every call follows the same pattern: check the base case and, if it holds, return the result right away, and if it does not, simplify the problem and call the function again on a smaller part. The classic example is factorial, the product of the numbers from 1 to n:

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

The condition n <= 1 stops the descent, and every call decreases n by one, so we always reach it. Let's trace what happens on the call stack for factorial(5):

1// Visualization of calls:
2// factorial(5)
3//   5 * factorial(4)
4//     4 * factorial(3)
5//       3 * factorial(2)
6//         2 * factorial(1)
7//           return 1     <- base case
8//         return 2
9//       return 6
10//     return 24
11//   return 120

No multiplication happens until we reach the base case, and the earlier calls wait on the stack, each with its own value of n. Without a base case the function would call itself forever, until the engine stops the program with a stack overflow error: in Chrome and Node.js it is RangeError: Maximum call stack size exceeded, in Firefox InternalError: too much recursion.

Recursion with Tree Structures

Recursion is natural when processing tree data structures - like a species hierarchy. Every node has a name and a children array, and a leaf is a node with an empty array of children:

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

The tree has four levels, but the functions we are about to write do not need to know that. Searching for a species works like this: if the current node is the target, we return it, and if not, we ask each child in turn:

1// Recursive tree search
2function findSpecies(node, target) {
3  if (node.name === target) return node;
4  for (const child of node.children) {
5    const found = findSpecies(child, target);
6    if (found) return found;
7  }
8  return null;
9}
10
11findSpecies(dinoTaxonomy, 'Velociraptor');
12// { name: 'Velociraptor', children: [] }

There are two base cases here: a hit (node.name === target) and a leaf, for which the loop does not run even once, so the function returns null. The tree stays untouched, because the function only reads. Recursion also combines nicely with reduce, for example when counting nodes:

1// Recursion + reduce: counting all nodes of the tree
2function countNodes(node) {
3  return 1 + node.children.reduce((sum, child) => sum + countNodes(child), 0);
4}
5
6countNodes(dinoTaxonomy); // 10

The base case is hidden here: for a leaf, reduce on an empty array returns the initial value 0, so the leaf counts as 1 and the recursion ends. The same skeleton will serve you for collecting the names of leaves or building the path from the root to a species. Pass the path on as a new array ([...path, node.name]), not with push, so that branches do not spoil each other's results.

Recursion vs Iteration

In FP, recursion replaces loops. Every loop can be written recursively. Compare two versions of summing the dinosaurs' weights:

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

The notation const [head, ...tail] = arr is destructuring: head gets the first element, and tail a new array with the rest. The base case is an empty array whose sum is 0, and weights stays untouched. JavaScript is not built for deep recursion, though: every call takes up a stack frame, and tail is a new copy of the array each time, so with a few thousand elements the stack may run out. My advice: sum flat lists with reduce, and save recursion for nested structures such as trees.

Tail Call Optimization

Recursion can lead to stack overflow with deep calls. Tail recursion is recursion in which the recursive call is the last operation of the function. After it returns there is nothing left to do, so the engine could release the current stack frame - that is what tail call optimization (TCO) is about. Compare both forms of factorial:

1// Regular recursion - each call waits for the result of the next
2function factorialNormal(n) {
3  if (n <= 1) return 1;
4  return n * factorialNormal(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}

In factorialNormal, after returning from the recursion we still have to multiply the result by n, so the call is not the last operation. factorialTail carries the partial result in the accumulator, which puts the call at the very end. To be honest, though: the ES2015 specification provides for such calls in strict mode, but only Safari's engine has implemented them. In Chrome, Node.js and Firefox, factorialTail(100000) still overflows the stack, so in JavaScript tail recursion is above all a readable accumulator pattern, not a protection against the error.

The accumulator pattern is useful beyond numbers too. flattenDeep flattens an arbitrarily nested list, passing the same results array down the levels:

1// Practical example - flattening a nested structure
2function flattenDeep(arr, result = []) {
3  for (const item of arr) {
4    if (Array.isArray(item)) {
5      flattenDeep(item, result);
6    } else {
7      result.push(item);
8    }
9  }
10  return result;
11}
12
13const nested = [['Rex', ['Blue', 'Charlie']], 'Brachio', [['Stego']]];
14flattenDeep(nested);
15// ['Rex', 'Blue', 'Charlie', 'Brachio', 'Stego']

Array.isArray recognizes a nested array, and then we go one level down. This is not tail recursion, because the call sits inside a loop, and push changes the result array. It is, however, a local accumulator: the default parameter creates a new array on every call from the outside, so nested stays untouched. In modern JavaScript, nested.flat(Infinity) gives the same effect. In the next lesson we will copy nested structures without mutation.

Remember: recursion is a walk through a family tree - every step brings you one generation closer to the goal, and the base case tells you when to stop.

1// Recursion in functional programming
2console.log("=== Jurassic Park - Species Family Tree ===\n");
3
4// --- EXAMPLE 1: Basic recursion ---
5console.log("--- Factorial ---");
6
7function factorial(n) {
8  if (n <= 1) return 1;
9  return n * factorial(n - 1);
10}
11
12console.log("5! =", factorial(5));
13console.log("10! =", factorial(10));
14
15// --- EXAMPLE 2: A taxonomic tree ---
16console.log("\n--- Taxonomic tree ---");
17
18const taxonomy = {
19  name: "Dinosauria",
20  children: [
21    {
22      name: "Saurischia",
23      children: [
24        { name: "Theropoda", children: [
25          { name: "T-Rex", children: [] },
26          { name: "Velociraptor", children: [] },
27          { name: "Spinosaurus", children: [] },
28        ]},
29        { name: "Sauropoda", children: [
30          { name: "Brachiosaurus", children: [] },
31          { name: "Diplodocus", children: [] },
32        ]},
33      ],
34    },
35    {
36      name: "Ornithischia",
37      children: [
38        { name: "Triceratops", children: [] },
39        { name: "Stegosaurus", children: [] },
40        { name: "Ankylosaurus", children: [] },
41      ],
42    },
43  ],
44};
45
46// Printing the tree recursively
47function printTree(node, indent = 0) {
48  console.log(" ".repeat(indent) + "- " + node.name);
49  node.children.forEach((child) => printTree(child, indent + 2));
50}
51
52printTree(taxonomy);
53
54// Recursive search
55function findSpecies(node, target) {
56  if (node.name === target) return node;
57  for (const child of node.children) {
58    const found = findSpecies(child, target);
59    if (found) return found;
60  }
61  return null;
62}
63
64console.log("\nFound:", findSpecies(taxonomy, "Velociraptor") ? "YES" : "NO");
65console.log("Nonexistent:", findSpecies(taxonomy, "Dragon") ? "YES" : "NO");
66
67// Counting leaves recursively
68function countLeaves(node) {
69  if (node.children.length === 0) return 1;
70  return node.children.reduce((sum, child) => sum + countLeaves(child), 0);
71}
72console.log("Number of species:", countLeaves(taxonomy));
73
74// --- EXAMPLE 3: A recursive sum ---
75console.log("\n--- Recursive sum vs iteration ---");
76
77function sumRecursive(arr) {
78  if (arr.length === 0) return 0;
79  const [head, ...tail] = arr;
80  return head + sumRecursive(tail);
81}
82
83const weights = [8000, 150, 56000, 2500, 9000];
84console.log("Recursive sum:", sumRecursive(weights));
85
86// --- EXAMPLE 4: Flattening a structure ---
87console.log("\n--- Flattening a structure ---");
88
89function flattenDeep(arr) {
90  return arr.reduce((result, item) => {
91    if (Array.isArray(item)) {
92      return [...result, ...flattenDeep(item)];
93    }
94    return [...result, item];
95  }, []);
96}
97
98const nested = [["Rex", ["Blue", "Charlie"]], "Brachio", [["Stego"]]];
99console.log("Flattened:", flattenDeep(nested));
100
101// --- EXAMPLE 5: Tail recursion ---
102console.log("\n--- Tail recursion ---");
103
104function factorialTail(n, acc = 1) {
105  if (n <= 1) return acc;
106  return factorialTail(n - 1, n * acc);
107}
108
109console.log("Tail 10! =", factorialTail(10));
110console.log("Tail 20! =", factorialTail(20));