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.

xkcd 244: Tabletop Roleplaying

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).

Meme by u/SingleWalnut

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.

Photo by Sara Sperry on Unsplash

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.