# 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

**E**xit: Define your exit condition.

**A**ct: Do whatever it is you want to do in this iteration.

**R**ecurse: 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;

}// ACTanswer *= (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 & RECURSEreturn 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.