Recursion is one of the major hurdles new programmers find in learning algorithms. It's not necessarily intuitive, and a requirement to have a grasp on a language. In fact, any recursive algorithm question can be solved using iteration. So why learn recursion? I'll be going over why it's important, what it is, and how to start using in in Ruby.
What is Recursion?
Recursion is a method to solving a problem where you call on smaller instances of the same problem. While coding, you often call on the current function within itself on a smaller subset of the problem. In iteration, you would call on an index that moves through the smaller instances of the problem. The difficulty here lies in identifying the smaller index. While I'll be talking about recursion in regards to simple ruby functions, it is a topic that can be applied to a lot of complex computer science problems.
When you call a function inside another function, the functions are added to a call stack, where the outside function awaits the computation of the inner function to finish its computation. Adding the same function to the stack in recursion means at some point you need to hit the smallest instance of the problem. If you don't hit a point where the recursive function call stops, then you will overflow the stack. Recursion is less efficient than iteration, so problems that can be solved easily with iteration should be. If efficiency is important, and it would be hard to use iteration, then tail recursion should be considered.
In tail recursion, you have to make sure that there is no additional computation to be computed after the recursive call is complete. This can be easily done by returning the recursive call itself, rather than returning an equation that includes a computation using the value of the recursive call. Tail recursion is faster because the interpreter in Ruby will convert it into iteration, rather than having a ridiculous call stack.
Importance of Recursion
Recursion is taught in most intro to computer science classes, included in many algorithm books, and is a topic new programmers often struggle with. For many, the idea that recursion can be solved with iteration mean that they don't need to learn how to use it. Recursion as a concept is important in understanding more complex data structures and computer science concepts in general. For example, when solving tree traversal problems, it would be very complex using iteration. With recursion, it become a logical traversal in each layer of the tree. Trees are built by nature to be smaller version of the larger problem, which lends itself nicely to recursion.
If you aren't planning to learn more complex algorithms, you should still consider understanding how recursion works. The concepts in understanding recursive call relates to many computer science concepts, which I won't cover here. In terms of just the general knowledge, it can be asked in many coding interviews, or even come up in a conversation with manager. If you are looking to be prepared for interviews, you should plan to have recursion under your belt.
Ruby Recursion
In Ruby, recursion is quite simple, but it can look very confusing due to implicit returns. I'll be more robust in my example to show some clarity.
Problem: Return the sum of a sequence of integers, that are defined by three input numbers: start_num, end_num, and step. If begin_num is greater than the end_num, the function should return 0
Example:
sequence_sum(2,6,2) == 12 # 2 + 4 + 6
If you have seen my previous post on algorithmic thinking, I'll be following those steps to work through this problem using recursion. The question is asking us to do a geometric sum. The inputs are the start, end and step size, and our output will just be a number. In terms of a solution, I see that I could do it iteratively, but it seams that it would be simpler to do with recursion, since the problem has layers of smaller problems that can be solved with the same equation.
In ruby, we can use a while loop where the escape case is when the begin_num becomes greater than the end_num. This is the case where we stop adding to the sum. In the loop, we can return the current begin_num plus the same function called with the current begin_num being replaced with the current begin_num plus the step size. The end_num and step will be the same through each function call. When we hit the escape case, we will want to not call the function again, and instead return 0, as instructed.
def sequence_sum(begin_num, end_num, step)
while begin_num <= end_num do
return begin_num + sequence_sum(begin_num + step, end_num, step)
end
return 0
end
This solution becomes quite simple, with only 6 lines of code. Since we want to be able to change the inputs, this will work for any step size and begin number. There are no additional variables defined in the function, which allows for clarity in the calculation. In the recursive case, the return in the while loop will await the call of sequence_sum to finish before computing the sum. This means that there will be many function calls waiting for their sum to be returned. When the values finally hit the base case, all of the function calls will return up the value, returning the sum in the top level.
Learning recursion isn't an easy task. After reading this post, I hope you are feeling more confident in trying problems on your own. This post is not intended to teach you all of recursion, but instead offer you an easier entry point for your own studies.
Top comments (0)