Recursion is considered both a fundamental precept of computer science and a litmus test that separates the decent programmers from the terrible ones.
I'm pretty sure I understand recursion. But I don't know what it says about me as a programmer that I pushed this chapter to the back of the book. However, while it is fun and challenging to write recursive procedures, it's rare to find situations in which a loop can't do the same thing – sometimes faster.
But it's important to at least recognize the pattern as you might run across a use-case for it. Even if a loop is possible, recursive solutions can be more elegant. And designing them are a good way to stretch out your programmer-thinking muscles.
This was another section that I hadn't originally planned writing. There's not much code yet, but there's an attempt to describe recursion through narrative. Let me know if it is a disaster.
I have a few applications in mind in the realm of image recognition and text-processing that I hope to include in a future update.
The King and his rocks
The following convoluted parable came to me so easily that I think I probably picked it up from somewhere else, possibly a college textbook or lecture long ago. However, a cursory Googling "recursion" and "rock lifting" did not find any positive matches. I apologize in advance if the following section is some kind of subconscious ripoff.
At its most basic conception, recursion is a division of labor. Pretend there is a king in a faraway kingdom from a long time ago, and pretend that you are his new chief servant. The villagers have just delivered their annual gift of giant rocks. This is considered a gift in this primitive time period, and as such, no one has figured out how to build a good weight scale and it's the lead servant's job to determine the heaviest rock to add to the king's heavy rocks collection.
This task is a huge undertaking for the chief servant. The gifted rocks are of all different types and densities; their weight cannot be determined by sight. So the servant – starting with the first rock all the way to the last rock – was forced to pick up each rock and compare it with the current heaviest rock.
If the new rock was not heavier, then the servant would move on to the next one.
If the new rock is heavier, then that rock becomes the current heaviest rock
With hundreds of heavy rocks to lift, you can see how the simple task of comparing rocks becomes an overwhelming, crippling task. And a dangerous one, too, as many previous servants have been executed by the king for taking too long. It gets more difficult as you progress because of fatigue. Even more annoying is that, in a close contest, you might have to lift the same two rocks over and over to correctly determine the heaviest.
Delegating and dividing the work
Meanwhile, the villagers are all meandering about. They know rocks are important to the king so they stick around to seem interested, but they all really would rather be home in their huts right now. Their idle rock-gazing being somewhat of a bitter annoyance to you, you decide to make them help you. After all, they want this over with too. So you pick out two villagers and assign each of them half of the rock stash to weigh.
"Come back to me when you've found the heaviest rock from your stash," you tell them.
You're feeling quite proud of yourself. When each of the two villagers has done his and her job, you will have to only decide between their two choices. You go into your servant quarters to treat yourself to a nap.
Your deputized villagers, however, are no less wise or lazier than you. Realizing that even half the rock pile is going to be hard work, your two villagers each pick out two other villagers and do the same thing you did: split their rock pile between these two new villagers to weigh.
The rock stash has effectively been divided into four separate stashes. Once the heaviest rock has been found from each of the four piles, the two villagers you hired will each pick between two rocks. Then, they each present to you the heaviest rock that "they" found.
As you can imagine, the new hired villagers are no less industrious. They each get two villagers and split the pile between them. Those new villagers do the same. This goes on and on until there are enough deputized villagers for all the rocks to the point that each villager has a task as simple as the one that you, the lead servant, will end up doing: picking the heaviest between two rocks.
--TK IMG?There's no more work to delegate at this point. So each one makes a decision and rolls the heavier rock to the villager who hired him/her. That villager now has that rock and the rock of the second villager they hired. She makes a choice between the two rocks and rolls it to her superior. And so forth.
This goes all the way up the chain to the two villagers who you originally hired. They each roll their heaviest rock to you. You pick the heaviest rock. The king is happy, the villagers go home, and you're alive for the next round of rock selection.
The two principles of recursion
The rock story, as silly as it is, at least embodies the main characteristics of recursion:
- An end goal, or base case
- A process in which the task at hand is reduced towards that end goal
The base case in this case is: to have two rocks (or fewer; if there are odd rocks, the base case will be just involve one rock) from which to judge from.
The process involves dividing any quantity of rocks that contains more than 2 rocks
So the task keeps getting divided and subdivided until the base case is met: a pile of just 2 rocks. At that point, a comparison is made and the result is returned to the parent task (the hiring villager who originally had 4 rocks).
Comparing Rocks with Code
Back to our present-day, let's sketch the solution out in code. First, consider the original algorithm for determining the heaviest rock: Holding onto the so-far heaviest rock and comparing it to every other rock in sequence. This is just a vanilla iteration loop with a variable for the current maximum value:
# make some random rocks
rocks = 30.times.map{rand(200) + 1}
puts rocks.join(', ')
max_rock = 0
rocks.each do |rock|
max_rock = rock if max_rock < rock
end
puts "Heaviest rock is: #{max_rock}"
## or with inject
puts "Heaviest rock is: #{rocks.inject{|max_rock, rock| max_rock > rock ? max_rock : rock}}"
The recursive algorithm does not require a loop. Instead, we make define a method that accepts one argument: an array of values
- If the array has two values or fewer, return the largest of the two values
- If the array has more than two values, split it into two arrays. Then invoke the method two more times to handle each sub array.
Here's the code for that method and how it is applied:
def rock_judger(rocks_arr)
if rocks_arr.length <= 2 # the base case
a = rocks_arr[0]
b = rocks_arr[-1]
else
a = rock_judger(rocks_arr.slice!(0,rocks_arr.length/2))
b = rock_judger(rocks_arr)
end
return a > b ? a : b
end
rocks = 30.times.map{rand(200) + 1}
puts rocks.join(', ')
puts "Heaviest rock is: #{rock_judger(rocks)}"
One caveat: Because I use the array's pop method to subdivide each array, the original array, pile_of_rocks, is modified at the end. Programmatically, all the lesser rocks have been discarded. That's not important in our example here, but it may be a poor design decision just to save myself one arithmetic operation.
The two-line version:
def rock_judger(r_arr)
count = r_arr.length
a,b = count <= 2 ? [r_arr[0], r_arr[-1]] : [rock_judger(r_arr.pop(count/2)), rock_judger(r_arr)]
return a > b ? a : b
end
Neither of these are simpler or more elegant than the original iterative solution. So what was the point of recursion?
That's a good question to ask, even if you're an expert programmer. Recursion has performance and design tradeoffs, and some of this is dependent on the nature of the language and compiler. In this case, iterating with each loop is significantly faster than any of the recursive methods.
Recursive design
However, there are cases where recursion can help you produce a more elegant solution.
In programming land, the rock-sorting problem is easy to implement with a loop. Because in programming, it's trivial to find the largest of two data values.
However, in the fantasy-world, a major problem is that comparing weights involved a time-intensive relative judgment. It's nearly impossible for a human to tell that the heaviest rock found so far is heavier than any other given rock by memory alone. He will have to physically pick up both rocks, maybe several times each if the weights are close.
Splitting the task among many workers so that each worker only has to judge between two rocks confers a huge logistical benefit.
There are similar situations in the context of real-world programming, but I'm drawing blanks on ones that are easy to describe.
Memory constraints
In such a situation, the recursion strategy is particularly useful because no worker has to do a "computationally difficult" task of comparing more than two rocks. But what happens if there aren't enough able-bodied rock comparers? Such a constraint exists for programmers For example, each individual method call requires its own memory space. If your system architecture has memory limits, there will be a limit to how deep you can go with recursion.
Applications (under construction)
Under construction; will likely include image processing and analysis applications.
Further reading can be found at Wikipedia's excellent list.