BLOGNAME: LOUDER THAN WORDS

An informal, stream-of-consciousness reflection on business ideas, events and issues in modern business, modern life and with some specifics to the web-software industry by Paul Tomori, Internet Entrepreneur

The Power of an Analogy Recursive Algorithms Re-visited After Two Decades By Paul Tomori Sunday, February 08, 2009 at 20:43:57 (EST) Today's blog entry is on computer science... kind of! I know - I know. I have covered popular culture news items, investment, mathematics and other stuff, but really I am into computers first and foremost. Really, I am! So the topic is "recursive algorithms"... but don't run away. Honest, this topic is truly fascinating. I was thinking the other day about how much trouble I had understanding the concept of a recursive algorithm when I was in university. Truly, I was baffled by it. The professor described its use by describing a certain type of computing scenario, which really gave me no footing to draw an understanding from. For example, don't you hate it when someone uses a word you never heard of in the definition of another word you never heard of? Where is the anchor upon which to attach new understanding? Enter the analogy. An analogy, as you probably know, is a parallel explanation for some new concept that is based on an existing concept that you are probably already comfortable with. People who know me well, know that I LOVE my analogies. THEY don't always love my analogies of course, but I love my analogies. So what does this have to do with a recursive algorithm in computer science? Lots. I am going to explain the concept using an analogy from the more accessible world of making pancakes. Fun. Keep reading. This is riveting stuff - I promise. First, the technical definition (close to what my professor used and which left me perplexed): A recursive algorithm is one that calls itself. Loose translation: A recursive algorithm is an instruction that includes a command to repeat the very same instruction. Better right? But still not adequate. It doesn't sound like English quite yet. And now the analogy: Imagine you are making pancakes. You have to follow a a bunch of instructions (i.e. a recipe) to pull it off. You might have these instructions stored in your brain or you might be reading them off of a card. Either way, there are certain steps that if followed accurately will produce the desired result: a golden brown, edible, fully cooked and downright tasty breakfast. The full instructions for making pancakes are too long for this blog. I am going to jump to the chase, where yes, a recursive algorithm is embedded in the cooking process. Here's the instruction REALLY simplified: 1. make batter 2. pour batter onto a hot griddle 3. assess the pancake and decide whether to flip it or let it keep cooking 4. wait til the other side cooks 5. serve yummy pancakes Inside step 3 is a recursive algorithm. Here it is: 3.1 watch for the bubbles that are appearing on top to pop 3.2 if the bubbles pop and then immediately fill in, then proceed to step 3.3, otherwise if the bubbles pop and leave a little crater, then flip the panckage and proceed to step 4 3.3 wait about 15 seconds and return to step 3 Do you see how step 3 is an instruction that has the power to call itself (i.e. to require that it repeat itself)? That is the recursive part. That is, you might have to "assess" the surface of the pancake a half-dozen times before you stop repeating the assessment and THAT is when you escape the recursion and proceed to next steps. EVERY recursive algorithm has to have an "escape" instruction... that is: a way to end the repeating. Otherwise, you end up with a fatal loop (a fatal loop is never really "fatal", but I think they use that word to give it extra drama). The program will crash, the computer might freeze up... or in the case of the pancakes, if you don't have an escape option at step 3, then the pancake burns. Here's why: Imagine if you just kept assessing the top surface of the pancake, but didn't have a cue upon which to flip it to the other side? Right: thick black smoke would soon become a new kind of cue for a new set of instructions that probably would not end with the words "serve yummy pancakes"!) So, there you have it. For almost 2 decades, I have sworn there was a better way to explain "recursive algorithm" and I believe that does it. You now know that an algorithm is really just a set of instructions, like a recipe. And, you know that "recursive" means something that essentially repeats. When combined, the two words together mean "an instruction that repeats until there is a reason built within the instruction forcing an end to the instruction". In several of the programs that my company has produced, we have recursive algorithms built in. For example, Merlin, which is a campaign tracker. Merlin stores traffic data from a website in a big log file. It stores lead data, that is data which initially brings people to a given website. And, it stores conversion data, that is data which indicates a purchase has been made. Every night Merlin sorts the data and then attempts to determine which of the lead data are correlated with the conversion data. Here's the routine: 1. open log file 2. sort all data by IP addresses so that leads and sales are clumped together with sales at the end of a given set of similarly-sourced leads 3. then, look for a sale and if one is found, proceed to step 4, 4. look at the previous line from the sale to see if it reveals a lead source (i.e. a lead source could be another website or a search engine, etc... etc) then determine if continued searching is warranted 5. record the lead source, the lead and the conversion in a little data trio that can be used in a summary report The recursive algorithm appears at step 4 4.1 if the previous line is of a similar IP, then record its lead source and compare it with any other lead sources already stored from other leads related to this sale 4.2 if the IP address is different, then escape to step 5, otherwise backup one more line and repeat step 4 When it's all done, we have matching leads and lead sources for just about every conversion. Of course, there is a LOT more to it than what I have described above, but the fundamentals of the recursive algorithm are shown in the simple beauty. Fun stuff! Return To Blog Index