Article summary
Recursion (solving smaller and smaller sub-problems until arriving at the base case) has always intrigued me. The first recursive function I ever wrote computed the factorial for n, and it looked like this:
def recur_factorial(n):
if n == 1:
return n
else:
return n*recur_factorial(n-1)
- The base case is when n is equal to one. On hitting the base case, no more recursion is necessary. The function must always hit the base case. (Otherwise, it would go on forever.)
- Each call to
recur_factorialis a sub-problem that is one step closer to the base case.
These types of recursion problems came up a lot in algorithms classes, but I rarely needed to write my own recursive functions in web development. However, in my current web project, recursion enabled us to crack some otherwise hard-to-solve problems.
Just as I did when writing the factorial function, I asked myself:
- What is the base case?
- How can this problem be expressed in terms of a sub-problem (that eventually will lead to the base case)?
Recursive String Parsing
We were working on a data importer and wanted to clean up the data we were importing. We needed a function that, given an arbitrarily deep nested object, would return an object with all the extra spaces parsed out.
The function would take something like this:
const object = {
thing1: "blah ",
otherThing: {
otherThingChild: " hey",
},
list: [
{
listThing: " hi",
},
{
listThing2: " hi",
},
],
};
And turn it into this:
const object = {
thing1: "blah",
otherThing: {
otherThingChild: "hey",
},
list: [
{
listThing: "hi",
},
{
listThing2: "hi",
},
],
};
It only makes sense to parse out the spaces when we are looking at a value that is not an object. If that value is null, we don’t need to do anything. If the value is a string, we can call a function to remove its spaces. So our base case is when an object is not deeply nested but has a value that is either a string or null.
In order to get to the base case, we need to go from a deeply nested object to an object where the values are either string or null. To do this, we can break the problem of parsing out spaces from the whole deeply nested object into the sub-problem of parsing out spaces from a value object. So the sub-problem is parsing the extra spaces off one of the values in a deeply nested object.
Our code ended up looking like this:
export function removeSpacesFromObject(obj: T): T {
for (let k in obj) {
if (typeof obj[k] === "object" && obj[k] !== null) {
removeSpacesFromObject(obj[k]);
} else if (typeof obj[k] === "string" && obj[k] !== null) {
(obj as any)[k] = removeWrappingSpaces((obj as any)[k]);
}
}
return obj;
}This function is checking for two base cases: the value is null, or the value is a string. If the object is null or or if the type of the object is a string, it does not recurse. Otherwise, it continues to recurse until it hits the base case, while removing the spaces from the inner object (the value).
Recursive SQL
Our system had a hierarchy of organizations. Given an organization, we wanted to be able to go up the hierarchy and find all ancestor organizations, and we wanted to be able to do this at a database level.
For each organization in the organizations table, we were already storing its (nullable) parent organization ID. If the parent ID for an organization is null, we know that there are no more ancestors to be found. So, the base case is when an organization has a null parent ID.
If the parent ID of an organization is not null, we want to find all ancestors associated with its parent organization. This defines the sub-problem: finding the ancestor organizations given an organizations’s parent ID.
To do recursion in SQL, we used a recursive Common Table Expression (CTE). This defines a temporary result set that can be used by a larger query. For more information, see SQL CTEs. A recursive CTE references itself.
In our recursive CTE, the UNION ALL is where the recursion happens. The UNION ALL references the CTE defined as ‘ans’ and will be executed until it returns no more rows.
Though recursion looks a bit different in SQL, it is still just breaking a problem into sub-problems until it hits the base case. The sub-problem of finding the ancestors for an organization’s parent is executed until hitting the base case where an organization has no parent ID and the join returns no rows.
CREATE OR REPLACE FUNCTION ancestors (x integer)
RETURNS TABLE (
"leafId" integer, id integer, level integer)
AS $function$
WITH RECURSIVE ans (
"leafId",
id,
"parentId",
level
) AS (
SELECT
id,
id,
"parentId",
0
FROM
"Organization" o
WHERE
o.id = x
UNION ALL
SELECT
ans. "leafId",
o. "id",
o. "parentId",
ans.level + 1
FROM
"Organization" o
INNER JOIN ans ON ans. "parentId" = o. "id"
AND ans. "leafId" = x
)
SELECT
"leafId",
id,
level
FROM
ans
Recursive Type Definitions
Recursion can even be used for type annotations. We use recursive type definitions in multiple places throughout our project.
For example, one of the libraries we are using (Lodash) defines a recursive array.
interface RecursiveArray extends Array<T|RecursiveArray> {}
Here, the base case is not an array, but instead type T. The sub-problem is, when given an array, the elements in the array must be of type RecursiveArray.
Recursion was a great fit for each of the above problems because in each of these cases, the initial problem could be broken down into a smaller instance of the same problem. We broke problems down from parsing a string out of a whole object to parsing strings out of part of an object, from finding all ancestors of an organization to only finding ancestors of the parent for that organization, and from defining something about an array to only defining something for each object in the array.
Once we correctly identified the sub-problem, most of the hard work was already done, and recursion handled the rest.