Warming up to Recursive Algorithms
Encountering recursive algorithms for the first time can be a bit intimidating, so if you are struggling to feel comfortable with them, I hope the following guided examples with visualizations can help you warm up to recursion. As you may already know, recursion occurs when a function is called inside itself, sort of like a dream within a dream. Inception’s Cobb can tell you how easy it is to get lost in such a mess, so in order to be able to keep track of these layers, we will need to have some sort of queue, and perhaps something to help avoid a never-ending staircase.
Our first example will deal with finding the product of two integers, a and b. Before we try to call our function within itself, we need to find our base case, that is, the simplest form of the problem. If b is equal to 1, we would just need our function to return a, since a * b = a. That will be our base case, and we will need to include that in our function in order to avoid any never-ending stairs.
Now, the trickier part is determining what your function is supposed to return if b is anything else. The problem here is, your function will not return the answer itself, but will rather perform an operation before calling itself until the base case is reached. First of all, how do we make sure the base case is reached to begin with? Well, our function depends on two arguments, and we know we need b to reach the value of 1, so we can simply subtract 1 from b every time we call our function (assuming b is greater than 1).
If we set our function that way, we know that recursion will happen b number of times. In order to make things easier, we could pick some arbitrary values for a and b, say a=5 and b = 3. As mentioned before, we know recursion will happen three (b) times because of the way we have set up our function. We also know that 3 * 5 = 15, so how do we get 15 by performing an operation 3 times? Additionally, we know our value of a (5) might need to be included in each operation, so we can see that 15 can be reached by adding 5 each time, 3 times. That is:
But how does this actually work? We will need a queue to help keep track of what happens every time we call our function. When we call our function for the first time, the if clause is not evaluated since b = 3, and our function attempts to return a value, which is equal to the sum of a + a new call to our function. Now, our function has not returned a value yet; it has simply gotten a part of the answer (let’s call this total) and will now need to evaluate the function mult(5,2) in order to retrieve the rest of the total, which, as of now, is pending at 5. The process is repeated and our total is now at 5 + 5 +a call to a new function mult(5,1). Now that we have reached the base case where b =1, the if clause gets evaluated, our total gets another 5 added to it, and our function can finally stop and give a final answer of 15!
