Recursion solves a problem by applying the same procedure to smaller or nested values. For AST processing, recursive calls follow containment relations until reaching values that need no further traversal. section 3.3.1
A recursive AST function handles each value according to its representation:
- For an AST object, recursively process its settings and combine the returned results. section 3.3.2
- For an AST reference, return the value appropriate to a reference rather than descending into it. section 3.3.2
- For an array, recursively process each element and combine the results; return a neutral result for other values. section 3.3.2
- Use the return statement to backtrack after a recursive call, letting the execution engine maintain the traversal path. section 3.3.1
Counting AST leaves
The recursive numberOfLeaves function counts child results for an AST object. If those results total zero, the object itself is a leaf; references contribute zero, and arrays sum their elements. Calling numberOfLeaves(astRoot) computes the total, producing 4 for the demonstrated rental AST. section 3.3.2
const { isAstObject, isAstReference } =
require("../common/ast") #1
const numberOfLeaves = (value) => { #2
if (isAstObject(value)) { #3
const sub = sum(Object.values(value.settings)
.map(numberOfLeaves)) #4
return sub === 0 ? 1 : sub #5
}
if (isAstReference(value)) { #6
return 0
}
if (Array.isArray(value)) { #7
return sum(value.map(numberOfLeaves))
}
return 0 #8
}
Inspect the complete recursive dispatch pattern for AST objects, references, arrays, and other values. section 3.3.2
