Recursion solves a difficult problem by breaking it into smaller versions of the same problem. Instead of managing a loop directly, a function handles one small piece and calls itself with a smaller input until it reaches a case with a definite answer. section 3.5
A recursive function needs two parts:
- A base case: an input that returns a concrete result without another call. section 3.5
- A recursive case: a call that performs one step and passes a necessarily smaller input back to the function. section 3.5
- A guaranteed path to the base case; otherwise calls continue until the program crashes. section 3.5
Adding an array recursively
To sum an array, return 0 for an empty array. Otherwise, add the first number to the sum of the remaining numbers. Each call receives a shorter array, and once the array is empty the pending additions can finish. section 3.5
Listing 3.10. Performing recursive addition
function sum(arr) {
if(_.isEmpty(arr)) { #1
return 0;
}
return _.first(arr) + sum(_.rest(arr)); #2
}
sum([]); //-> 0
sum([1,2,3,4,5,6,7,8,9]); //->45
The empty-array check is the base case. The second return statement is the recursive case: it keeps the first value and recurs on the rest. section 3.5
Recursive thinking fits nested or recursively defined data because the same task occurs at every level. It can traverse a deep-frozen object structure, parse XML or HTML, work with graphs, or visit every node in a tree. A tree mapping operation can process a node, then repeat the operation for each child in preorder. section 3.5
Each JavaScript function call creates an execution context, including a recursive call. Deep recursion therefore grows the context stack with the input size. A tail-recursive function puts its recursive call last and carries needed state in arguments; tail-call optimization can flatten that work into a single reused frame. section 7.1 section 7.4
const factorial = (n, current = 1) =>
(n === 1) ? current
: factorial(n - 1, n * current);
This factorial keeps the running result in current. Its recursive call is the final action, so the next call has all the state it needs. section 7.4
Use recursion when a problem is naturally self-similar and each step can make measurable progress toward a base case. For ordinary sequential data work, map, reduce, and filter also remove manual loops while keeping control flow separate from transformation logic. section 3.0 section 3.6
