Recursion: The Pros and Cons
Ah, recursion. How many nights have I poured over your hows and whys? Alas, no longer! For I have conquered your enigmatic conviction. Your wretched desires shall haunt the recesses of my conscious ne’er more.
Ok whew, moving on. Recursion. I’ve spent a lot of time trying to get to the bottom of what recursion is and what the benefits and faults are of using the method. On the surface it seems like a difficult concept to grasp, but after a little thought, seeing examples and making analogies, the concept becomes a bit more clear. So what is recursion?
Recursion by definition is “when a thing is defined in terms of itself.” In this case we are referring to mathematical or programatic functions. With respect to a programming function, recursion happens when a function calls itself within its own definition. It calls itself over and over again until a base condition is met that breaks the loop.
There are 2 main parts of a recursive function; the base case and the recursive call. The base case is important because without it, the function would theoretically repeat forever (in application there would be what is referred to as a “stack overflow” to stop the repetition which we will touch on a little later). Below is an example of a simple recursive function.
So what is happening in that picture above? That is a simple recursive function to calculate the value of n! (n factorial). Factorial means the product of an integer and each subsequent integer below it up to and including 1. In the above example we are calculating the factorial for n = 3 (3 * 2 * 1 = 6). The function starts at the uppermost box in the diagram. The function is
def factorial(n)
if n > 1
return factorial(n - 1) * n
else
return 1
end
end Our base case (the point at which the repetition stops) is when n is no longer greater than 1. At this point the function will return 1 as the value and we will move back up the “stack” of boxes until we have our final answer. The method above repeatedly calls factorial on n-1 (it is also necessary to change the input value so that it moves closer to the base case with each recursive call, otherwise we will never reach the base case and we will be stuck in RECURSIVE PURGATORY) until it reaches the base case, which is 1. When the base case is reached, the function returns 1. 1 is then the value that is passed back up so that the previous call of factorial(n-1) = 1. n here is equal to 2 so we get 1 * 2 = 2. 2 is then passed up, n is equal to 3 so we have 3 * 2 = 6 for the final value. (If we would have gone up one more, we would have returned 6, n would be equal to 4 so 6 * 4 = 24, which is the correct value for 4!) WOOHOO you did recursion!
Ok, so we generally know the basics on how recursion works. But why is any of this important? When and why would we choose recursion over any other algorithmic method, such as say, iteration? Well there are several pros and cons to recursion.
PROS:
Recursion can reduce time complexity. This was somewhat counter-intuitive to me since in my experience, recursion sometimes increased the time it took for a function to complete the task. An example of this is calculating fibonacci numbers. If you calculate the fibonacci sequence up to a number n using recursion rather than iteration, the time to complete the task when compared to that of the iterative approach was much greater. However, if you memoize the result (aka save the value of each calculation for further use in the recursive call) you can in fact reduce the time complexity (read a great answer response for more information about memoization here).
Recursion adds clarity and reduces the time needed to write and debug code. This one is valid to a point. If you know your input into a function is going to be small, then recursion is certainly a good choice if you want to de-clutter your code. If your input is sufficiently large however, the sacrifice of speed and memory for the sake of clarity becomes much less attractive and functional.
Recursion is better at tree traversal. This one is a little more advanced. An extremely simplified version of what this means is as follows: A tree is a collection objects that are linked to one another (imagine leaves on a tree connected by branches that are in turn connected to other branches all the way to the roots). One of the more efficient ways to traverse these trees when looking for a specific leaf (or node) is by recursively following a single branch until the end of that branch until you find the value you are looking for. Again, this is extremely abstracted and simplified for what is actually happening and I urge you to look further into what is actually happening in tree traversal.
Recursion in the above tree diagram would be beneficial when used on preorder tree traversal.
CONS:
Recursion uses more memory. Because the function has to add to the stack with each recursive call and keep the values there until the call is finished, the memory allocation is greater than that of an iterative function.
Recursion can be slow. If not implemented correctly (as stated above with memoization) it can be much slower than iteration. It is actually pretty difficult to write a recursive function where the speed and memory will be less than that of an iterative function completing the same task. The reason that recursion is slow is that it requires the allocation of a new stack frame.
I know I mentioned a lot about recursion vs iteration above, so lets look more into that.
Both iteration and recursion are repetitive processes that repeat a certain process until a certain condition is met. They are both used in programming to complete tasks where a task has to be repeated in order to solve the problem.
Iteration: A function repeats a defined process until a condition fails. This is usually done through a loop, such as a for or while loop with a counter and comparative statement making up the condition that will fail. An infinite loop for iteration occurs when the condition never fails.
Recursion: Instead of executing a specific process within the function, the function calls itself repeatedly until a certain condition is met (this condition being the base case). The base case is explicitly stated to return a specific value when a certain condition is met. An infinite recursive loop occurs when the function does not reduce its input in a way that will converge on the base case.
The Stack
As stated above, recursion is memory intensive because it requires an allocated stack frame, which can be shown by the above columns/buckets. For every call of the function, another element is added to the stack and once the base case is reached (at the top of the stack, or the last entry), the element is “popped” off of the top and that value is passed to the value below it. The stack is another interesting topic to look into, and I would suggest checking it out as there is too much information to go into here. I hope I have provided a basic view of how recursion uses the stack.
In conclusion, there is a great article written about the importance of knowing about recursion here that is definitely worth the read. Obviously there is A LOT more information on recursion but I hope that I have at least touched on some major areas to give you a direction in which to explore great topics on recursion a little further.