Nutty Easter Eggs

I’ve always appreciated Easter Eggs in software products.  I remember doing things like searching for Elvis in the original Mac OS Map program, or finding the magic hidden dot in Atari’s Adventure to get you to the secret room.  I just added a friend of mine who is leaving the company where we worked on Facebook and saw a picture of something on Google.

If you search on Google it will often offer up a “did you mean” link in case you misspelled something or they found something with what appears to be more relevant hits.  I’m going to take a detour here and hit upon a programming concept before continuing.

Recursion is an often confusing concept until you have worked with a lot.  The premise is that you take a larger problem and rather than solve the whole problem you make a little machine that can navigate the entire problem one step at a time.

If you had a 5 pictures and wanted to know how many different ways you could arrange them you would solve it as follows.  (# choices on 1st pick) + (# choices on 2nd pick) + (# choices on 3rd pick) + (# choices on 4th pick) + (# choices on 5th pick).  For 5 pictures it would look like this:

(5) + (4) + (3) + (2) + (1) = 15

Each time you choose a picture you take away from the # possible of choices.  This can be written as the following expression to be more generic:

For n > 0;  f(n) = n + (n-1) + (n-2) + … (1)

That’s easy to do if you have a small number of choices but what if you wanted to figure it for 1,000 pictures?  It would take you a long time to write that out and calculate it.  This is a great problem to be solve recursively because you can create a little machine to solve one of the numbers and then use the machine to keep solving the rest.  Here is how that would work.

when n>1: f(n) = n + f(n-1)

when n = 1: f(n) = n

Back to our 5 picture problem it would come out as follows:

  • f(5) = 5 + f(4)
  • f(4) = 4 + f(3)
  • f(3) = 3 + f(2)
  • f(2) = 2 + f(1)
  • f(1) = 1

You can start to see that the little function machine takes (n) and then calls itself to figure out what (n-1) would be.  It keeps calling itself until it reaches 1 and then it just returns one.  Look at the list above and you will notice that the last term on the first line is actually the 2nd line.  The last term on the 2nd line is actually the 3rd line and so on.  You can start performing substitution and when you reach the end you will have our original equation.  Here is the substitution in action:

  • f(5) = 5 + f(4)
  • f(5) = 5  + 4 + f(3)
  • f(5) = 5 + 4 + 3 + f(2)
  • f(5) = 5 + 4 + 3 + 2 + f(1)
  • f(5) = 5 + 4 + 3 + 2 + 1
  • f(5) = 15

So our machine is designed to add a number to the results of the same machine for the next lower number until it reaches 1 and simply returns 1.  The machine “recursively” calls itself until it reaches 1 and then breaks out.  So here is what it would look like in coding logic:

  • print Machine(5)
  • function Machine (n)
    • if n > 1 then return (n + Machine(n-1))
    • else return (1)
  • end function

So that was my long detour and let me get back to Google and their “did you mean” link.  If you to go to Google and search on the word “recursion” it will display all the normal results.  If you look at the top of the results Google will offer you a “did you mean” link and it points to the word “recursion”.  If you click on that link it returns you to same page.  Get it?  It’s a nerd thing!  I just love finding and seeing these Easter Eggs!