Recursion, Overhead, and Computational Graffiti

Recursion can allow a complex algorithm to be specified in a short, simple, and often beautiful form. A function calls itself on a subset of the data, using the results from those subproblems to form the final solution. However, Recursion can also add computational overhead due to the new recursive function calls.

On her way to the library of Alexandria, Ann could see the signs of chaos engulfing the kingdom. The traditionally smooth operation of the kingdom's services inefficiently squeaked along under the burden of additional complexities. Overhead the pigeons of the kingdom's vast carrier network flew about aimlessly. The postal carriers had given up sorting the mail before embarking on their delivery routes. Instead, they stood in front of each mailbox and flipped through their full bag to find that house's letters. Everything was a mess.

Ann first noticed the computational graffiti in the outskirts of Alexandria. Initially, it looked harmless -- the rebellious proclamations of teenagers: "DFS Rulez" or "Dynamic Programming FTW". The signs soon became more troubling: "Say 'No' to Big-O" and "BRUTE FORCE ALGORITHMS FOREVER". At first, Ann thought these signs were jokes. Who would argue against an efficient algorithm? The absurdity made them almost unbelievable.

Then Ann saw a message that stopped her cold:

int RecursiveAdd(int n, int m) {

if (m == 0) return n; // base case

return RecursiveAdd(n, m-1) + 1;

}

The recursive algorithm for adding two numbers covered the entire North wall outside a Florist's shop. While technically valid, the sheer inefficiency of the of the approach shocked Ann. Why take a simple mathematical operation, m + n, and embed it within a chain of m function calls? The overhead was staggering. The graffiti clearly pointed to the complete collapse of computational thinking.

Tearing herself away from the disturbing image, she broke out in a full run. There was no time to lose.

Merge Sort and Lines of Kindergarteners

Merge sort is a recursive, sorting algorithm based on two intuitive principles:

1) It is easy to sort very short lists. In fact, it is trivial to sort lists containing only one item.

2) It is easier to merge together two sorted lists than it is to sort a long list.

Using those ideas, the merge sort algorithm can be described simply as: "Break the data to sort in half, sort each half separately using merge sort, and merge the halves back together into a single sorted list."

Ann's kindergarten teacher, Mrs. Magee, was fiercely competitive. She insisted that the class excel in everything. Her class always had the highest test scores. Her class always won at dodgeball. And, most important of all, her class could form a sorted line faster than any other class in the kingdom.

It did not matter how the class was being sorted. They could line up by height, by first name, by last name, by length of their left pinky toe, or even by their skill at dodgeball. Mrs. Magee would call out an attribute, and the class would spring into action.

Like all winning teams, their excellence depended on more than natural talent. In fact, most kindergarteners in the class were absolutely dreadful at sorting when they started school. Once, two students, Jack and Jake, had spent fifteen minutes trying to compare the order of their names. It was embarrassing.

The class's ability came from practice. Mrs. Magee drilled the class for hours at the start of the school year. Every time the students went to the bathroom or to lunch, she would first make them line up in some sorted order.

Of course, there was also a strategy -- Merge Sort. It was her secret weapon, her key to winning.

At the command "LINE UP!" the class would split into two equally sized groups.

Class before sorting

First split

Those groups would then each split into two smaller groups.

The splitting continued until each group had just a single person.

Then, starting from each pair of singletons, the groups would reform. Each child would look at their partner and quickly line up in order. With only two people it was easy. A single quick comparison provided the order.

After the groups of two were in order, the kids would merge into larger groups. Again, merging was simple -- you only needed to compare the two kids at the front of the two lines. The person with the smallest value had to be one of the first two kids, because the lines were sorted. The first two kids would compare, and one would step forward to start the new sorted line.

Merge Step 1

Now the second smallest still had to be one of the front two kids.

Merge Step 2

And so forth.

Merge Step 3

Merge Step 4

Merge Step 5

The lines would quickly merge together, forming larger groups. This would continue until the entire class was in order.

That is how Mrs. Magee's class won the sixth annual kingdom sorting championship. Her class was in order a full five minutes before the runners up. In fact, Mr. Frizzle's fifth graders were still comparing the numbers of freckles on their right arms when Mrs. Magee's champions had left for lunch.

To be continued in Sorting During the Flu Outbreak: The Reality of Sorting Small Sets

---------------

To learn more about other sorting techniques see Why Tailors Use Insertion Sort or Bullies, Bubble Sort, and Soccer Tickets.

Panicked Depth First Search: Part 7 of Ann's Visit to G'Raph

Depth first search is a search algorithm that fully explores a single path before backtracking to test other paths. The algorithm operates in a recursive way, first exploring all of the options down one subpath before considering other subpaths. For example, on a graph the algorithm will explore the neighbors of a neighbor before returning to original node to test other direct neighbors. Unlike breadth first search, which uses a queue based approach to track unexplored states, depth first search uses an approach based on a stack.

Ann realized that she had made a critical mistake almost as soon as she left the library. In her rush to get to the school, she had neglected to bring a map with her. In any other town, this would not have been a major problem -- she would just run in the general direction of the school. But finding your way around in G'Raph was not that simple.

Ann stopped when she reached Thomas's farm. There were two paths in front of her, and she was not sure which way led to the school. She looked around for the farmer, but Thomas was not in his radish patch.

Making a quick decision, Ann chose the path out of Thomas's farm that was on her right. She ran over the bridge, and found herself at the local pottery kiln. An assortment of bowls were lined up outside the kiln. Judging from the quality of craftsmanship at least a few of the bowls must have been made by third graders at the school. Ann hoped that she was getting close.

Now Ann had another decision to make -- two new paths led away from the kiln. Again Ann chose the path to her right, and she ran over the bridge. This time the result was less promising. Ann had come to a dead end. She was on an island that appeared to be a mud quarry. There were no new bridges that might take her to the school.

Ann backtracked quickly, returning to the pottery kiln island.

She then ran down another bridge, arriving at a carrot farm. It was another dead end.

Ann backtracked to the pottery kiln again. This time there were no more paths to take, so she backtracked further. She returned to Thomas's farm. From the farm, she took the other bridge and arrived at another (smaller) radish farm. From the looks of it, this farm was decidedly less successful than Thomas's farm. Ann paused for the briefest moment to wonder what could cause the difference in radish growing performance between two almost indistinguishable islands of mud. Maybe it had something to do with crop rotation strategies.

Yet again, Ann was faced with a choice of bridges. She started with the path to her right. Much to her relief, this bridge led directly to the school.

Ann ran up to the school. Florence and Edgar were already there. Their scooters were parked nearby, and Edgar held a folded map of G'Raph in his hand. Ann cursed herself again for not having brought a map. She could have saved a lot of backtracking.

"You made it!" exclaimed Edgar. "I was afraid that you would get lost without a map."

"I did get lost." admitted Ann. "Or at least, I hit a few dead ends and had to backtrack."

"Ah… a depth first search." noted Florence. "Nice."

"Depth first search?" asked Ann. She was still a little out of breath from all the running.

"Depth first search is when you keep exploring along one path until you hit either a dead end or a node that you have seen before. Then you backtrack to the most recent decision point and try a different option. If there are no new options at that point, then you backtrack again." explained Edgar.

"Think about searching a binary tree." suggested Florence. "With depth first search, you keep exploring deeper and deeper until you come to a dead end."

"Or find what you are looking for." added Edgar.

"Yes. Good point." replied Florence. "You can also find what you are looking for. Edgar, remember that time we used depth first search on that choose your own adventure novel?"

"Fun times." answered Edgar.

Ann just nodded. She was too tired to appreciate the algorithmic beauty of her own frantic run. A map would have saved her from having to experience depth first search first hand.

The school's principal, having seen the group standing outside, came out to see what was going on.

"Have you seen a strange man in a dark cloak?" asked Ann without bothering to introduce herself.

"Umm… yes. Why do you ask?" asked the principal.

"Did he talk to anyone?" asked Ann, ignoring the principal's question.

"Yes. He talked with one of our star students, Elizabeth. He had some question about some sort of math problem." answered the principal. "I was there too, but honestly could not understand what he was talking about. Elizabeth seemed certain that she could figure it out though. She went right home to work on it. She is very bright, you know. Probably the best scholar that our school has ever taught. She will find the answer."

"Do you know what the question was?" asked Ann.

"It was something about islands and bridges. I think he called it 'vertex covering'. I had not heard of it before, but it sounded like fun."

Ann felt her stomach drop. She was familiar with the vertex covering problem from her own time in school. Like the traveling salesman problem, it was unknown whether the vertex covering problem had an efficient solution. The problem fell into a class of NP-hard problems.

Unless Ann missed her guess, Elizabeth had just fallen victim to the same spell as Geoffrey. G'Raph High School's star student was a risk of becoming unnaturally obsessed with a single NP-hard problem.

So far, the wizard had targeted two star scholars. Unfortunately, Ann had no idea why.

To be continued in Part 8: Minimum Spanning Trees, Prim's Algorithm, and Bridge Upgrades...

Follow Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph.

--------------------

Find out more about breadth first search in: Breadth First Search and the Search for the Pig Thief.

Or find out about stacks and queues in: Stacks, Queues, Priority Queues, and the Prince's Complaint Line.