A Trick For Writing Recursive Code
I recently had a conversation with someone struggling with writing recursive code, so I thought I’d share this trick that my university professor taught me. The trick is simply to assume someone already wrote a solution to the algorithm that solves 98% of the problem, and you just have to write the remaining 2%: The first 1% of the work is to check if you’re in the “base case” situation. If so, great, you’re done, and you return the base case solution. If not, then the other 1% of the work is that you must prepare the arguments for the “base case + 1” scenario and then invoke the solution function provided to you, which solves the remaining 98% of the problem for you.
I’ll explain in more detail after the break.
Let’s say you have a binary tree where each node contains an integer, and you want to sum up the integers in all the nodes.
What you do is assume someone already wrote the function that solves this 98% of the problem for you. Let’s call it magic_function(tree)
, which takes a tree as a parameter and returns the sum as an integer. The only thing missing is handling the “base case” situation and setting up the arguments for the “base case + 1” situation.
Let’s start with the base case. For our problem, the base case is an empty tree with zero nodes. In this case, we define the sum to be zero. So if we know we’re in the base case, we just have to return 0.
sum_tree(tree) {
if (tree.isEmpty()) {
return 0;
}
TODO
}
Now the “base case + 1” situation is that the tree isn’t empty, which means you have a node with some value, and two sub-trees. All you have to do is invoke your magic_function
on the two sub-trees, and add that to the value in your current node. You’re handling the “base case + 1” situation, and the magic function is handling the “base case + 2” situation, the “base case + 3” situation, and so on.
sum_tree(tree) {
if (tree.isEmpty()) {
return 0;
}
return tree.value + magic_function(tree.left_sub_tree) + magic_function(tree.right_sub_tree);
}
Now here’s the secret: That magic function is actually the function that you just wrote. So just update the code so that all references to the magic function is instead a reference to your own function:
sum_tree(tree) {
if (tree.isEmpty()) {
return 0;
}
return tree.value + sum_tree(tree.left_sub_tree) + sum_tree(tree.right_sub_tree);
}
That’s it. You’re done.
Recursion is like a superpower where you ask a time-traveling future version of yourself to solve 98% of the problem for you, and you just solve the remaining 2% — and then by solving that last 2%, you’ve fulfilled your obligation to your past self of solving 98% of the problem for them.