Recursion can be stated as follows: when a process or concept requires itself to be defined.
But, what does it mean? It means that the process repeats itself to create a result. A famous example is the Fibonacci sequence where the function, F, is defined by the sum of the 2 previous results, with the exception of F0 that is 0 and F1 that is 1.
In programming there are 2 main ways of decomposing a problem, Bottom-up and Top-down.
The bottom-up, normally, results in an iterative process while an approach top-down is naturally recursive. To better understand these 2 approaches we will look at the example of sorting a sequence.
Think of the sorting like a tree. We have the singular values at the bottom and the sorted sequence at the top.
In the bottom-up approach we start by the leaves of the tree (bottom) and work our way up until we have our sequence fully sorted. It creates an iterative process that starts on small problems and progressively joins and solves other pieces until the problem is solved.
In the opposite side, we have the top-down approach that takes the problem and decomposes it in a recursive manner. In our sorting example it reconstructs the whole tree where each node is a call to itself. This way we have a naturally recursive solution for the problem.
Recursivity is quite useful for stuff like debugging where someone starts looking at the broad function and converges into where the code is wrong until we pinpoint a location.
In recursive world there are 2 major concepts that make or break a recursive solution and can be quite hard to debug if one is flaky / wrong.
The first concept is the base case, the base case defines when to stop. Since time and resources are finite, we can’t recurse forever, or we would be stuck and our program would crash due to resource limitations.
Because of that we need to think deeply of what is our base case and it will be definitely be different for every problem we face.
The other case we have is the recursive case where we divide the problem and make the recursive call. This one is obviously very important since it defines our logic but also defines how to divide the problem.
Having said this, the 2 main takeaways are recursive case divides the problem recursively and defines our logic and the base case defines when to stop recursion.
We will be now talking about 2 famous examples of recursion that are quite useful.
One of the examples I wanted to talk is the factorial one. A simple yet effective way to calculate the factorial of a number.
If you don’t know or simply do not remember, a factorial of a number is simply calculated by multiplying the number from 1 to n. For example 5 factorial is 5 * 4 * 3 * 2 * 1.
A simple iterative function would start at the lowest number (1 in this case) and iterate over until reaching our desired number. But a recursive solution starts at the number and calls itself over and over again until reaching 1, let’s now define both the base case and the recursive case of this solution.
The base case is simple, it just needs to check the condition to stop, in this case, we stop when the number is 1. The recursive case simply calls the factorial of n - 1 and multiplies it by n.
This way we have an effective way to calculate the factorial of a number.
Another example I want to analyze is the Fibonacci sequence, how can we calculate the nth element of such sequence in a recursive manner? Well, lucky for us it is simple!
To define the base case, as we talked before, we need to check if n, our number is one of the numbers that we know the value, either 0 or 1 if that is the case we return the value else we add the previous 2 numbers.
Now we will talk about some optimizations that can be done to recursive algorithms to make them more efficient.
Tail recursion is a technique used in some languages to optimize the recursive function by transforming it, effectively into an iterative function.
It can be only applied when the recursion appear as the very last thing and alone. Meaning we return the result of the recursive call without doing any computations based on that call results.
This works, because, internally, computers have a stack of function calls and when the last instruction is a recursive call, the new call replaces the old one and therefore the stack does not grow.
This can be very useful when we have deeply recursive functions where, when using a stack based approach we would be quickly out of resources, but with tail recursion, the stack does not grow and we can compute such functions.
Memoization is when we cache the results as soon as we compute them, making it a fast solution for computing solutions where a top-down approach is required.
Dynamic Programming or DP for short, in the other hand is when we use a data structure and iteratively fill that using previous values. This is usually implemented using table like structures (nested lists for example).
DP divides the problem into smaller ones, following a bottom-up approach.
We will now talk over common errors and pitfalls that we, programmers, usually fall into.
This error occurs when we make more recursive calls than the stack allows. Remember talking about tail recursion? Well, this is the error in case the stack becomes full of recursive calls and the program crashes.
To address this issue we either have to fine tune our base case or implement tail recursion to avoid running out of space in the stack.
Other issue is when we are coding we can easily make an error and make the recursive call several times with the same parameters, slowing down massively the code.
This is not an error but more a common pitfall that can catch many of us off guard and be really difficult to troubleshoot.
Finally we will be talking about where this recursive functions are used in the real world.
Traversing trees is normally done recursively due to the nature of the structure.
In a binary tree, every node has other nodes and every other node has even more nodes, so, by visiting every node at a time, it becomes easy to call the traverse function for every children, stopping when we reach a leaf node.
Divide and conquer algorithms are really interesting, they work by recursively dividing the problem until it becomes manageable.
Example of algorithms are for instance, the merge sort algorithm, where it divides and then merges smaller chunks.
And this concludes our small introduction to recursive functions and for now that’s all I have for you, have a nice day and keep on coding!
IV. Real-World Examples In this section, we’ll look at some common real-world algorithms and analyze their time complexities. A. Searching Algorithms Linear Search (O(n))
Introduction The Delivery Driver Analogy Imagine you’re a delivery driver tasked with delivering 100 packages throughout a city. Now consider a few different scenarios: