Recursion in Ruby
Many functional languages, such as elixir, use recursion on a regular basis. Ruby, however, takes advantage of explicit recursion far less often, instead favoring iterators. In this post, we’ll explore some situations in which recursion is actually the better choice in Ruby.
RECURSION VS. LOOP:
To lay the groundwork, let’s illustrate how iterators in Ruby look vs recursion in a typical situation. Say I have an array and I want to square each value in it. The recursive solution in Ruby might be:
Here we set a base case where the method returns once the array is empty. Then we split the array into a head and tail, call the block on the head (this returns the square of the head) and call the method again with the tail as its argument, simultaneously pushing the return of the block into acc. Once the original array is empty, we return the value of the acc, which will be an array of the squared numbers.
The equivalent by using iteration would be the much simpler, easier, and more optimized:
[1, 2, 3].collect {|x| x * x} => [1, 4, 9]
In fact, Ruby uses iteration and loops to do a whole host of tasks, including .each, .collect/.map, .filter/.select, .find, .until, .while, etc.
WHEN TO USE RECURSION:
A good question, then, is when to use recursion in Ruby over an iterator. In most cases, a loop of some sort will be the most simplest, optimized solution for finding or changing items in an array. That being said, there are cases where recursion will be far more readable and elegant, which is something all coders should value.
We should consider favoring recursion when trying to accomplish a loop in which the result of the first loop produces the second item/array to loop over, which produces the third, etc. Using a while/until loop in that situation requires us to set up all sorts of variables to track changes which becomes progressively messier as the number of variables increase. Recursion, however, as we’ll see, allows us to keep the entire process self contained and elegant, as no new variables need to be created. Rather, the method is called and called again as soon as new items to loop over are produced.
EXAMPLE: To illustrate, let’s build the beginnings of binary search tree. The way it will work is that we’ll have a root number value with a left and right node. Say my root number is 8. If the next number I want to add is lower than 8, I will attach it to the left node. If it is higher than 8, I’ll attach it to the right node. Each number I attach will itself have two nodes, which will behave in the same manner. Thus, a built binary search tree might be depicted as:
The way the program adds a value to this binary search tree is by hopping from node to node, doing a less-than-or-more-than conditional on each (to tell whether it should go left or right) and following the nodes until it comes to an empty one, whereupon it will insert the new value as a node there.
THE LOOP BST:
Here’s where we get to loop vs. recursion. If I want to do this inserting process using a loop, then I'll need to set an instance variable for my BST (binary search tree) to keep track of the current node being looked at to determine whether to go left or right down the tree. It might look like this (messy) code:
Which, when used, might return the tree below:
Before we go over why the insert method above is not the best solution, let’s understand how it operates. The key is that it keeps track of the ‘@movement’ instance variable, which is a copy of the BST that is winnowed down as the loop progresses. Every time the method loops, it sets potential_movement to the @left or @right of the @movement variable (depending on the number at the current position).
If the number being inserted, for example, is lower than the current BST number, then potential_movement is set to whatever is at @left. If @left itself is a BST (i.e. it hasn’t gotten to the bottom of the tree yet), it sets @movement to @left (i.e. the remaining part of the tree) and repeats the process. This process happens until the loop comes to an @right or @left that is equal to nil. Then, it creates a new BST with the number we want to insert as its argument and sets that @right or @left equal to it.
PROBLEMS WITH THE LOOP VERSION:
There’s nothing wrong with the above method in that it, at least, works, but boy is it ugly and difficult to follow! Also, by the end, the @movement instance variable for each BST includes, for the most part, an unnecessary copy of the search tree below it.
The reason this method is so ungainly is that it needs to change which BST node to call self.left or self.right upon. In other words, as opposed to keeping track of a simple piece of data, such as a counter or a boolean, the loop keeps needing to be called upon different objects, in this case BSTs, to check the @right and @left values of the current BST.
THE RECURSIVE BST:
This is a great case where recursion will be helpful because recursion is precisely the process of calling the same method again and again on different objects or pieces of data, eventually using the results of those repeated calls to return the correct value.
Here’s the BST class with recursion:
Which, when used, might return:
Here, both the code and returned result are cleaner. We don’t need an @movement or potential_movment variable to keep track of which object to check @right or @left upon because that object will always be the one that insert is being called upon!
In Ruby, then, it is important to keep in mind that even though iterators and loop might be the norm, knowing how to enact recursion can still go a long way toward writing cleaner, more elegant code.














