How, why, and when is recursion the better choice for your algorithm?

Recursion is an algorithm design technique in which the underlying algorithm calls itself with updated input until certain conditions are met. These terminating conditions that end the recursive call of the algorithm are also called "the base" of the recursion.

How can a process (aka algorithm) can actually call itself? Simple. All there is to know is that there exist a dependence relationship between the states of the algorithm. For example, consider the famous Fibonacci sequence of natural numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, etc.

One can notice that each term of that sequence, except the first two, can be writen as a sum of the previous two terms. In other words there exist the following dependence relationship between the current state and the previous two states:

1
1
2 = 1 +1
3 = 2 + 1
5 = 3 + 2
8 = 5 + 3
13 = 8 + 5
21 = 13 + 8

The formal way to write this relationship between the terms is: f(n) = f(n-1) + f(n-2). We can now use this formula to create a program that computes the n^th Fibonacci number for us.

There are two popular ways to code this. The first is to design an algorithm that iterates starting at the third term starting at index 0, until the n^th term, and uses dummy variables to momentarily store and update the previous two states in order to compute the final one.
That is:

The second is to design an algorithm that uses the first two states as the base for the recursion, and then recursively calls itself on the previous two states, namely:

Both algorithms produce identical results, but is it a trivial question to ask "which one would you use"?

In order to choose which algorithm to use, even beyond the scope of this example, we need to examine the complexity of the algorithm, or in simple words:

1) how much memory each algorithm consumes while it runs, and
2) how fast it works when the input gets too big.

After examining these two characteristics (time and memory), we then pick the one with the best trade-off between the two, depending on the situation. Spoiler alert: the recursive version of the Fibonacci algorithm is tremendously inefficient in comparison to the linear version.

But why? The answer to this lies on the mechanics of recursion. To understand how these mechanics work, you first need to think of it as a function composition from mathematics.

Consider: f o g o h (n) = f( g( h(n) ) ) i.e. h executes first, then g, and finally f.

Similarly: f o f o f o ... o f (n) = f ( f ( f ( ... f (n) ... ) ) )

This can be modeled using a stack data structure:

When the base condition of recursion is met, the recursion (aka the piling of f functions in the stack) ends, and the compiler pops them out LIFO style. For more information on how stacks work, check out this link:
https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues

Ok cool, but this is not the entire story. In fact, this "naive" model, although it's correct, it might mislead the reader that the recursive calls of f are linear. In other words, f will be called at most n times, right? Well, this is where "depends" comes in.

In order to determine the size of the "recursion stack", i.e. how many times f will be called, we need to examine the so called "recursion tree". That is, a visual representation of the recursion in a particular problem. In the Fibonacci recursion case, that would look something like the following:

Recall that the Fibonacci recursion algorithm returns "Fibonacci(n - 1) + Fibonacci(n-2)" which will first trigger "Fibonacci(n - 1)" which will trigger "Fibonacci(n - 2)" etc. until it finally triggers "Fibonacci(1)" or "Fibonacci(0)" which both return 1 and therefore their sum will be returned and computed as "Fibonacci(3)".

Repeating this process, the algorithm will visit EVERY node of the tree above before it returns the final result cause it needs to "pop out" all the piled up recursive function calls of the recursion stack, that are shown in the tree above. It is clear now that the larger the input is, the larger the size of the recursion stack will be.

But how large compared to the input? In the Fibonacci case we are dealing with a binary tree, thus the number of nodes is at most 2^height - 1, which is an exponential value. That means, that for any input n₀ > n, there will be triggered, roughly, a multiple 2^c, c = |h₀ - h| number of extra calls, where h₀ and h are the heights of the recursion trees of input n₀ and n, respectively. Yikes.

Here it's worth to mention that this problem of exponentially many redundant calls of the Fibonacci recursion can be solved using a technique called "memoization". However, the purpose of this article is to analyze recursion so that it can be wisely used in problem solving, and not to provide a solution to possible inefficiencies of recursion.

That being said, this is not always the case with recursion trees. The Fibonacci recursion is inefficient because it computes the same values over and over again. In other cases, such as Mergesort or the rod-cutting method, recursion can be quite helpful.

For example, consider the Mergesort algorithm:

which basically calls itself from 0 to (n/2 - 1) and then again from n/2 to n, dividing n by 2 in each step, until n is equal to 1. Then it merges all these sub-intervals in a sorting manner and as a result the array gets sorted. For more details about Mergesort see this link:
https://en.wikipedia.org/wiki/Merge_sort

Let's examine the recursion tree of Mergesort and see what this tells us about the algorithm:

where M(1) is a single element of the input array, after the array has been subdivided to a unit level. Notice here that the number of subdivisions is exactly the one necessary to break down the array into its component parts, which is LINEAR, and then will take logarithmic time to actually merge all the elements back together into a sorted array, cause the levels of the tree to be merged is height = log₂ (n).

Therefore, Mergesort's recursion actually makes sense here. It won't grow exponentially nor it will take too much memory to operate.

To summarize, the ways to find out if recursion is a good approach to solve your problem or not, are:

1) Draw the recursion tree of the recursive calls of your algorithm. Notice that the tree could be ternary or any n-ary tree, depending on how many times you call the algorithm within. Nevertheless the logic remains the same.

2) Compute the time and space complexity of the algorithm and compare it to a non-recursive alternative. You can study the space complexity by drawing a memory layout, i.e. a stack, and model the data to be stored in each step there. For time complexity, you will have to check the recursion tree and compute the steps in each level, or use useful results from computer science literature, i.e. Master Theorem

Remember, any recursive algorithm can be written as a procedural algorithm, so don't get frustrated if your solution is too inefficient at the beginning. We all have been there. :)

I hope you found this article useful! Let me know what you think in the comments, and see ya around!