While building a simple JSON parser from scratch recently, I gained a few insights into recursion.
JSON[1] (JavaScript Object Notation) is a lightweight data-interchange format and is widely used on the Internet. For instance, a book information in JSON format looks like:
{
"name": "Introduction to Computer Science",
"ISBN": "978-1-5566-904",
"price": 19.99
}
The syntax for JSON is simple and intuitive, making it seems easy to parse. A
JSON object starts with an opening brace { and ends with a closing brace },
containing key-value pairs separated by a colon :. Some parsing pseudocode
as follows:
func parseJSONObject(data)
if not findOpeningBrace(data) then
//Error
return;
fi
do
key = parseKey(data)
if not findColon(data) then
// Error
return;
end
val = parseValue(data)
if findComma(data) then
continue;
else if findClosingBrace(data) then
break;
else
//Error
return;
fi
while(1)
end
func parseValue(data)
if findQuotation(data) then
// value is string
...
else if findDigit(data) then
// number
....
else
// Error
fi
end
However, it becomes increasingly difficult as more nested objects are added, for example:
{
"name": "Introduction to Computer Science",
"ISBN": "978-1-5566-904",
"price": 19.99,
"author": {
"name": "David",
"ages": 35,
"address": {
"country": "USA",
"city": "New York"
}
}
}
I have to admit, it took me days to realize that recursion is the key to
parsing nested structures. The solution is simply to call the parseJSONObject
function itself whenever the value is a JSON object. The revised parseValue
function:
func parseValue(data)
if findQuotation(data) then
// value is string
...
else if findDigit(data) then
// number
....
else if findOpeningBrace(data) then
// object
parseJSONObject(data)
else
// Error
fi
end
Quite simple, right? That's the magic of recursion -- both easy and powerful. The full source code can be found here.
I wondered why recursion didn't occur to me at the very beginning. Although I learned recursion before and even wrote recursive programs, I hadn't fully understand when to use it or what it was truly meant to accomplish.
Recursion is the best approach for solving problems with nested structures. Whenever you encounter a situation where solving the main problem requires solving a smaller version of it first, and that process continues with even smaller problems, recursion is the right tool. In short, *whenever a problem requires repeating similar steps, consider recursion*.
This also explains why recursive programs are often simple. Recursion breaks down the problem into smaller parts until it’s easy to solve. The recursive function only needs to handle the simplest case.
Another insight I gained about recursion is that it's a clear and concise way to describe problem-solving, as recursive programs tend to be simple.
Consider the famous "Tower of Hanoi" problem:
You have three rods and a number of disks of different sizes, which can be moved onto any rod. You start with the disks in a neat stack in ascending order of size on one rod. The objective of the game is to move all the disks over to Tower 3. But you can move only one disk at a time and cannot place a larger disk onto a smaller disk.
Even if you know how to address this problem, it's hard to describe your steps. But with the help of recursion, things become easy, I'll just give leave the final code below, you can find more details here
function move(n, src, aux, dest) {
if (n === 1) {
dest.push(src.pop());
} else {
move(n - 1, src, dest, aux);
dest.push(src.pop());
move(n - 1, aux, src, dest);
}
}
1 JSON offical site 2 Indepth.dev Dijkstra was right — recursion should not be difficult
Written by Songziyu @China Oct. 2024