Before getting into how to traverse binary trees, whether ordered or unordered, as mentioned in my last post, we have to go into recursion, since it’s an integral part of how to do that, which brings me to the creation of a new series: Algorithm Concepts. This series that’ll show up from time to time will probably cover things like Big O or searching algorithms. On with the show!
So what is this thing?
GeeksforGeeks defines recursion as “the process in which a function calls itself directly or indirectly”. A function that does this, therefore, is called a recursive function.
Say, for instance, you need to figure out the factorial of a given number. Remember your grade school math, ha!) where the factorial of a non-negative integer “n”, is the product positive integers less than or equal to n. For instance, 4-factorial, or 4!, is equal to 4*3*2*1, or 24.
Programmatically, a factorial function could look something like this:
function factorial(x) {
if (x === 0)
{
return 1;
}
return x * factorial(x-1);
}
Anatomy of a recursive function using factorial
Let’s take a look at the anatomy of this recursive function. Notice the if statement. That would be your base case to terminate the recursive function. If there’s no base case or way to get out of the function, there’s a good chance it’ll just infinitely loop.
Secondly, in the last return statement, notice how factorial() is called again, but with X-1 passed in. It’ll return the value of whatever X is times the return value of factorial(x-1), which in our example, X = 3. It’ll look something like this:
return 4 * factorial(3)
So, before the above statement resolves, there will be a function call of factorial(3). The function call of factorial(3) will then look something like this…
return 3 * factorial(2)
Notice the pattern here? This above statement won’t be resolved either until the next subsequent call finishes. X will get whittled down until the base case is met. This is the part of the function that makes it recursive. factorial() is called within factorial().
We’ll skip the calls of factorial(2) and factorial(1) just for brevity’s sake. When factorial(0) is called, it’ll go to the termination case mentioned earlier and return 1.
Once we hit our base case and there are no more functions to call, things will ‘unravel’, if you will. You can think of this succession of calls as nested functions. The innermost function will return first. Then the next, and then the next. We’ll finally be able to resolve the functions we didn’t finish executing yet.
So in our example, it’ll go as follows:
Since factorial(0) becomes our last function call, it’ll return it’s return value first, and it will return 1.
factorial(1) returns 1 * factorial(0), or 1*1
If you see the pattern, then factorial(2) returns 2 * factorial(1), or 2*1*1
Again, for brevities sake, we can skip factorial(3)’s call, and top off with factorial(4), or 4*3*2*1, which is our last remaining method to complete, and it will return our final value of 24.
When recursion goes wrong
As mentioned before, we need a proper termination case. If we don’t have a proper termination case, the functions will keep going indefinitely until we cancel our program or some sort of error gets thrown. Take the following example:
function factorial(x) {
/*if (x === 0)
{
return 1;
}*/
return x * factorial(x-1);
}
We don’t have a termination case.
Let’s say in this example:
function factorial(x) {
if (x === 0)
{
return 1;
}
return x * factorial(x);//HERE
}
On line 6, X is not decremented, so we’ll never reach our base case.
Let’s say in this example:
function factorial(x) {
if (x === 0)
{
console.log('Sup dude')
}
return x * factorial(x);//HERE
}
The base case isn’t returning anything, so execution won’t stop, which leads to the overall point that in recursion, things are dependent on one another, but there does need some sort of endpoint so that all subsequent method calls can finish. Remember that unwinding idea I was talking about earlier.
Closing
So that’s the deal with recursion, which we’ll see more often when we go back to binary trees next time.