What do I understand about recursion (Part 1)
At the most basic level, recursion means calling a function within that function itself. If implemented improperly, it leads to infinite loops which are not useful at all. But if we establish some guardrails, recursion can be a powerful problem-solving method, despite its initial non-intuitiveness.
The problem that I faced at the beginning was how to make sense of the fundamental process. For example, how can a function be called within its definition? Isn't the function incomplete at that point? There are two ways to clear this mental mess. The first is to take it for granted: "It is what it is what it is..." That is never the right approach because it only sets the mess aside rather than clearing it. But that is still what I did initially and I got away with it, initially. The only way to achieve the right understanding of this concept was to understand what actually makes it possible.
For that, we first need to know about the compiler. The compiler is what makes any high-level language like Python, Java and C work in the first place. It translates code written by us and converts it into binary code (as that is the only language a machine understands)...
Now that we can wrap our heads around the process of function calls within the definition itself, we need to understand how to use recursion properly. Just like a loop, we need to set a limit or condition which, when no longer met, exits the recursive function. For that, we have what we call the base case.
The base case is the simplest function call that the recursion will eventually reach. For example, for a recursive factorial function, we know that factorial(1) = 1. And we know that the factorial must take all the numbers from 1 to n (or reverse, depending on your approach) in the calculation. So, for factorial(4), we know that the simplest part of the solution is factorial(1). We might not know what factorial(4) is but we do know what factorial(1) is equal to. Here is why that base case will be our saviour -
factorial(4) is nothing but 4 * factorial(3). If we repeat this decomposition, we eventually arrive at the fact that factorial(2) is equal to 2 * factorial(1). Well, what do we have there? So far, we were dealing with a bunch of unknowns that were a smaller part of the original problem, such as factorial(3) and factorial(2).
But now we have decomposed the problem enough to have reached the base case, which we know the answer to.
So, we already know that factorial(1) = 1,
which means factorial(2) = 2 * factorial(1) = 2 * 1 = 2,
which means factorial(3) = 3 * factorial(2) = 3 * 2 = 6,
which finally brings us back to factorial(4) = 4 * factorial(3) = 4 * 6 = 24.
As you can see, after going down the rabbit hole of functions all the way till we encountered our simplest (and known) case, the answer then bubbled back up all the way till factorial(4).
To now generalise this function:
def factorial(num: int) -> int:
if num == 1: # FIRST THING! Checks if we have reached our base case
return 1 # Because we know the answer to our base case factorial(1)
return num * factorial(num - 1)
As we established, we always want to multiply our current number with the factorial of the previous number. But before that happens, it will check if the current argument of the function is equal to 1, as that is our base case, i.e. our last step in calculating the factorial.