Have You Seen the Recursion Google Joke?

The recursion Google joke is not easy to spot, but it is clever.

Try and find the joke with a Google search.

Did you spot the joke?

What is the recursion google joke?

When you search recursion on Google, you will notice a suggestion:

Google uses its auto-suggest to correct the user with the message:

‘Did you mean: recursion’

If you notice there are no spelling mistakes in the search bar! We did mean ‘recursion’, we entered in the exact text. And if you continue to click on the link, you will see the same suggestion for ‘recursion’.

Pretty funny right?

What is recursion?

If you are not familiar with recursion you may not get the joke. So let’s look at a textbook definition:

Recursion is a way to solve a problem in Software Engineering, by using a function that calls itself.

This is similar to a loop in programming. A loop repeats a section of code until a condition is met. Whereas with recursion, the function itself repeats execution until a specific condition is met.

Let’s say we have a function that minuses the input by 1 until we have an input of 0. We could approach this in two ways. Using a loop or recursion.

An example of a loop in PHP:

So the code above utilizes a while loop to minus the input by 1 and repeat until the $input is 0 or less.

An example of recursion in PHP:

The recursive function is similar, but rather than looping within the code. The function is continuously called with:

$this->recursiveFunction($input — 1)

And the input is subtracted by one in the parenthesis of the next function call.

Essentially, recursion is a function calling itself until a specific condition is met.

This condition is responsible for halting the execution once the problem has been solved, and is known as the stop condition.

In recursion a call must have:

• A stop condition
• An operation is involved in solving the problem.
• A call to the function itself.

Recursion is great for solving typical algorithms, such as merge sort and binary search, check out an article on a Big O Notation Example where recursion is used.

The Stop Condition

The most important factor of recursion is the stop condition. Without a properly defined stop condition, your code can continue to run until your application crashes.

This stop condition tells your application to stop running as the problem has been solved. And in the case of the above example. The stop condition is when the input is 0 or less.

The Operation

An operation where the code performs an action is essential for solving the problem. Otherwise, the function continues to loop as the stop condition is never met.

In our example, the operation occurs within the parenthesis of the recursive call itself where we minus the input by 1 (highlighted in bold).

$this->recursiveFunction($input — 1);

Without the operation, we pass in the input continuously and the function would call forever.

The Call Stack

Recursive functions use a call stack.

The call stack is a queue of function calls that use a first in last out processing system. Meaning each function call is added to the call stack like a stack of dining trays at a café. The first tray goes in and trays continue to stack. When someone comes to pick up a tray, they pick up the most recently placed tray, which is at the top of the stack.

This is how the call stack works in recursion.

Each reference to the function itself halts execution at the point of the recursive call and adds a call to the top of the stack. Repeating this sequence until the stop condition is met.

When the stop condition is true, the call stack begins executing calls in the last in first out order of the stack.

So for the recursiveFunction in the example above, the call stack looks like this:

Now the stop condition has been met. The call stack begins emptying calls in a last in, first out order. Running the remaining code ‘return’ for each call on the call stack:

What are the benefits of recursion?

While recursion and looping are similar.

Many Software Engineers prefer recursion, as it reduces the number of lines needed and is easier to read.

When you are performing an algorithm that requires a large amount of operation and branches off to another function. It can be easier to use a recursive call over a loop.

Recursion is useful for solving a problem that uses similar traits to recursion. For example when searching through a tree node using Depth First Search, which requires a Last in First Out queue while searching. Recursion makes sense to use over a loop in this example.

So when using specific search algorithms, check to see if the data structure and the algorithm use a recursive solution.

What are the drawbacks of recursion?

With the simplicity of code you get with recursion, there are drawbacks.

• Recursion is more memory intensive due to the call stack.
• If we add the incorrect stop condition. The recursive call may never end, and as a result, we may run out of memory.
• Recursive calls tend to be slower than loops in execution.
• Code using recursion can be misread due to how the call stack operates.

Always test your recursive calls, they can bring your systems to a halt if the stop condition is not set properly.

The recursive Google joke is a light-hearted play on Recursion

The joke from Google is one that never ends!

While recursion is a useful technique for iterating through code until you solve a problem. It’s a light-hearted way for Google to play a joke on its users wanting to learn more about recursion. I hope Google continues to add Computer Science based Easter eggs into their search engines, as they sure are funny.

Let me know in the comments if you find any other Easter eggs.