Recursion isn’t the hardest principle to understand, but often is not a way of thinking that comes most naturally for developers. Personally, I have struggled with recursion in the past and try as I might to avoid it, sometimes it is the cleanest way! After using it a few times I have become more comfortable with it, and have developed a checklist of what to look for when writing a recursive function.
What is Recursion?
- When a function calls itself
- Often the most natural solution when involving data structures such as trees
The Recursion Checklist
The Base Case
- Prevents infinite recursion. We need to know that the function won’t infinitely call itself and that there is a state in which it will terminate that it is working towards.
- Kind of similar to a while loop condition for when to stop looping
The Recursive Call
- Moves towards the base case
- The defined method is called from within itself
Famous Recursion
Words are great, but rarely help you understand a problem… So now let’s take a look at a few common examples:
- Fibonacci e.g. find the nth element of the Fibonacci sequence, this is the sum of the 2 elements prior to it in the sequence. It is simply solved by recursion but is terribly inefficient with exponential time complexity.
- Trees e.g. finding the root of a tree given a specific node
Fibonacci
Fibonacci is simply written using recursion but also is incredibly inefficient this way. Nonetheless, consider the following:
public int fibonacci(int n) {
if(n <= 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}Lines 2 and 4 are the base cases we are working towards. They will terminate the recursive calls by returning 0 and 1 respectively. Meanwhile, if a base case is not met line 7 makes 2 recursive calls working towards the base case by reducing the parameter n by 1 and 2. Part of the inefficiency is that the function is evaluated repeatedly for the same value of n.
Calculating the nth element of the Fibonacci sequence is a classic algorithm that makes 2 recursive function calls and is exponentially large. Recursion is terminated when n is either 0 or 1. However, although it is most simply written recursively it can be much more efficiently written iteratively, as follows:
public int fibbonaci(int n) {
int current = 0;
int next = 1;
for (int i = 0; i < n; i++) {
int temp = current + next;
current = next;
next = temp;
}
return current;
}The above algorithm achieves the same output but with linear time complexity. There also benefits in terms of not having to be concerned about stack overflows, more on this later in the article.
Finding the root of a tree node
Let’s assume we are given the following class to represent a node of a tree, and that the values in the tree are populated appropriately:
public class Node {
private Node _parent;
private IList _children;
public Node getRoot() {
if (_parent == null) {
return this;
}
return _parent.getRoot()
}
}The getRoot method is recursive as it calls itself, and will keep calling itself until it gets to the root node. The root node is where recursion terminates due to the check if the parent is null. As the root node is the value returned in the base case, this value propagates all the way up through the recursive calls to the entry point of the method, and thus this is a simple way to get the root of the tree.
Alternatively, this same method can be written without recursion and this may be preferable for the reasons described later:
public Node getRoot() {
Node currentNode = this;
while(currentNode.getParent() != null) {
currentNode = currentNode.getParent();
}
return currentNode;
}
// With the addition of a getParent method to the Node class
public Node getParent() {
return this._parent;
}Iteration or Recursion?
When deciding whether to use recursion there are a few things you should consider:
- How much data are you working with?
- Is there a simple iterative solution?
How much data are you working with?
This is a very important factor, as if you have too much data and thus very deep recursion, a stack overflow will occur and your program will throw an exception. This is when your program tries to use more space that is available on the call stack. The size of the call stack varies depending on a variety of factors such as machine architecture and programming language.
Some languages, such as Scheme, are optimised to allow for infinite tail recursion, and implement tail call optimisation. Unfortunately, in most languages such as C#, Python and Java, this is not the case. Tail recursion is when the return result comes entirely from the recursive call. For example, our getRoot call is tail recursive as the return result relies entirely on the recursively called function or the base condition.
Whereas, the following function is not tail recursion as it relies on the multiplication of the parameter n times the value of the recursive call, and thus the recursive call must be evaluated before the return value can be.
public int fact(int n) {
if (n == 0) {
return 1;
} else {
return n * fact(n - 1);
}
}Is there a simple iterative solution?
Often recursion is the simplest way to solve a problem, and this is when it is most commonly used. It is important when choosing whether to use a recursive or iterative approach, to decide whether you can simply implement a solution using an iterative approach. In general, an iterative approach is more efficient as there is less overhead involved.
More of a Visual Learner?
I talk through this on my MissCoding YouTube Channel.
Summary
Recursion may seem like a mystical concept at first, but with a clear understanding of its principles and practical applications, you’ll find it to be a valuable tool in your programming toolkit. This blog post will equip you with the knowledge and confidence to harness the power of recursion and tackle complex problems with ease.
If you’ve enjoyed this article, you will likely enjoy more of my tech blogs or videos on MissCoding’s YouTube Channel. I also share a lot of code on GitHub so am worth a follow over on GitHub. You may even consider donating to support my continued content creation.
