The saying goes, “In order to fully understand recursion, you have to understand recursion.” As frustrating as a definition within a definition sounds, recursion can be a difficult concept to grasp and apply when it comes to writing code. As a new student to the world of computer science, I wanted to explore this daunting topic and provide an explanation in a manner that made most sense to me.
Recursion is essentially the process of breaking down a large problem into smaller versions of the same problem until we reach an end goal — we’re dividing and conquering by the running the same process in small pieces, rather than all at once.
Specifically in Ruby, for a method to be recursive, it must satisfy two conditions:
- It contains a base case, or an end goal, to tell the method when to terminate
- It calls on itself within the same method
To fully wrap our heads around the concept, let’s walk through this with an example. Say we want to sum all positive integers up to 5:
How could we potentially break this down in smaller pieces to solve? We could do something like this:
By breaking down our problem into smaller sub-problems, we can find solutions to each individual chunk and apply that answer to find our next solution. Therefore, by calculating a, we can find b, then c, and so forth to ultimately find our answer. So how can we write a method to solve each individual problem above? Let’s take a stab at this:
Within the method, we are calculating each sub-problem by calling on our own method and using the value returned to calculate our final answer. Writing this method for every single n value can be tedious. For example, if n = 100, we will need to write out 100 lines of code to find our answer. To avoid repeating the same lines of code, what if we could collapse this method by using a pattern we observed above for lines after n = 2?
Now that we recognize the pattern, let’s cut back on our code smell:
Ta-da! We created a method that satisfies both conditions required for it to be recursive. In this specific case, when n = 5, the method will continue to run on itself integer by integer until it hits n = 1, at which point it’ll stop. This is why a base case is absolutely necessary. Without a base case, the method would enter an infinite loop, never knowing when to stop itself because there’s no ultimate goal for the method to reach. We’d then end up with a “SystemStackError: stack level too deep” error. Not ideal.
Wait… can’t we just use an iteration method to loop through our values and give us the outcome we want?
Absolutely. However, oftentimes recursive methods can be shorter and cleaner, making it easier for coders to read. While recursion is simply another form of running loops with the exception of more specific conditions, the difficulty for coders is determining which technique is best to use for the job we want to accomplish. When writing codes involving process repetition, a general iteration method is the preferred approach but recursion is worth understanding at least conceptually. Though rarely used and typically slower in execution than iteration, you never know when having recursion in your toolkit that might make your life easier in the future.
