Designing Recursively: a home-cooked recipe
Programming with recursion opens up countless opportunities for you as a developer. However, designing your first recursive function (one that isn’t factorials … my goodness is that the only example everyone is taught?) is easier said than done. Let’s learn how to construct a recursive function.
What is a recursive function?
A recursive function is one that calls itself. This can be immensely powerful for performing scalable tasks like tracing the contents of a tree.
void recursive() {
// ...
recursive();
}int main() {
recursive();
return 0;
}
At its basic level, we need to perform some action and then perform that same action to a related value or data structure, but not endlessly. If we do not define an exit condition on the recursive function, we will recurse forever (or until we reach the callback limit or run out of memory or a variety of bad things depending on the programming language of choice).
Cool… Now how do we do it?
In the past, I always struggled a bit to explain the process to peers since I always only understood it at a very hand-waving level. In full honestly, it was very much a compile-and-add-print-statements-until-it-works process in my early days. Those days are over for me, and starting today they are for you!
The Recipe
Remember to always listen here for my special recipe to your perfect recursive function: EAR
Exit: Define your exit condition.
Act: Do whatever it is you want to do in this iteration.
Recurse: Call the function within itself to trigger the next iteration.
It’s that easy. Let’s see it in practice.
Example #1: Binary Tree
We need to print all the leaves of a binary tree using preorder (TLR) traversal. Cool, let’s bake up a recursive function.
// C++struct Node {
int value;
Node * left;
Node * right;
}Node * createTree() {
// left as an exercise to the reader
// or magic. Doesn't matter too much
}void printTree(Node * node) {
// EXIT - when should the recursion stop?
if(node == NULL) {
return;
} // ACT - what should we do to this node?
std::cout << node->value << " " << std::endl; // RECURSE - where do we go from here?
printTree(node->left);
printTree(node->right);
}int main() {
Node * head = createTree();
printTree(head); return 0;
}
Example #2: Factorials (if we have to)
Okay fine, I’ll do the factorial example, too. Here is the recipe in action on the classic introduction to recursion problem: we’re given a positive non-zero integer, and we must calculate the factorial.
// C++int factorial(int n, int answer = 1) {
// EXIT
if(n == 1) {
return answer;
} // ACT
answer *= (n-1); // RECURSE
return factorial(n-1, answer);
}int main() {
int number = promptUserForNumber();
int answer = factorial(number);
std::cout << number << "! = " << answer << std::endl; return 0;
}
Once you use this recipe to brew up some of your own functions, you’ll be able to start free-styling it a bit and bending some rules; just like a real food recipe!
See how we use some of that flexibility here when we reduce the number of method arguments by doing the Act & Recurse steps at the same time.
// C++int factorial(int n) {
// EXIT
if(n == 1) {
return n;
} // ACT & RECURSE
return n * factorial(n-1);
}int main() {
int number = promptUserForNumber();
int answer = factorial(number);
std::cout << number << "! = " << answer << std::endl; return 0;
}
Voilà ! My home-cooked recipe for designing your own recursive functions. I hope it’s as helpful for you as it has been for me.