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.