The Philosophy of Recursion

It was CS111, my first computer science course at Rutgers University. The lecture topics were fairly straightforward so far. Input/output, selection, and repetition statements made sense to me. I started to think that a programming career was possible. Then my professor announced the topic for the day: recursion.

I wasn't intimidated until my professor started describing recursion. He said that recursion was a different way of thinking. It was both powerful and abstract. It was elegant and mysterious. It would twist your mind into thinking differently. But what really caught my attention about recursion was that fully understanding it was a moment of enlightenment. You may not understand it right now, in a few days, or even months later. One day, when you are ready, recursion will come to you and say, "I see you."

For me, that moment came years later at my first full-time job after college. I was having a difficult time with a program. I understood the problem, but I couldn't develop the solution algorithm. Then I remembered recursion. The problem reminded me of recursion. After some reflection, I was able to wrap my head around recursion and develop the algorithm. It was a moment of enlightenment for me, like in The Karate Kid when Daniel realizes that Karate was in him all along.

It was then that I realized that recursion was always around me, in many forms. On television, I saw a newscaster. Behind him was a television monitor of that same broadcast. In that monitor was the same broadcaster sitting in front of a television monitor of the same broadcast. And so on.

At a child's birthday party, I picked up two mylar balloons. They both had silvery, mirror-like surfaces. I put them next to each other and saw myself in a reflection of myself in a reflection, seemingly into infinity.

Even artwork from as far back as 1320 illustrate recursion. Medieval paintings used the Droste effect to show a picture, within a picture, within a picture, etc. The main photo at the top of this article is an example of the Droste effect. Take a minute to contemplate that drawing. Let it draw you in.

The 2010 sci-fi film Inception is perhaps the clearest example of recursion in a movie. In the film, the characters must access deep layers of subconsciousness to extract information and alter the future. To do this, they sleep and enter a shared dream world. Once in the dream, they assemble and once again sleep and dream. And so on. The deeper they go, the closer they get to the subconscious state of the target's mind. To leave a dream state, the characters use a kick to return to the previous dream state and so on. More on kicks later.

One final example of recursion is one that you can do yourself. Take two phones and start a video call between them. Then face one camera to the other. With both cameras in view, quickly rotate one phone a quarter turn clockwise. Watch the effect on the other phone. This effect is also seen at the end of the Arkangel episode of the Black Mirror television series.

Now back to programming. The Hello World program for recursion is the factorial concept from mathematics. Here is the calculation of five factorial (5!):

5! = 5 * 4 * 3 * 2 * 1 = 120

A simple Java program to calculate the factorial is:

int n = 5;

for (int i=4; i >= 1; i--)
  n = n * i;

System.out.println(n);  //120

The for loop simply performs the calculation above in a straightforward manner.

A recursive program requires a different way of thinking. The factorial equation above offers clues on how to think recursively. 5! is the same as 5 times 4!. 4! is the same as 4 times 3!. And so on. Eventually, we reach 1! which by definition is simply 1.

So, a function call to calculate 5! would return the expression:

5 times a function call for 4!

But the function call for 4! is a function call to the same function. In other words, let the function call itself.

Ponder that for a moment 🤔.

When the first function call for 5! makes a second function call for 4!, it waits for the second function call to return. The second function call returns the expression:

4 times a function call for 3!

It too waits for the function call for 3! to return. Function calls repeat in this manner until the function call for 1!. At that point, there is no need for an additional function call, because the function can simply return 1. This simple case is the kick needed to stop making recursive calls and return to the previous level. Inception.

The previous function call receives 1 and returns 2 * 1 to its caller, which returns 3 * 2 to its caller, which returns 4 * 6 to its caller, which returns 5 * 24 to the first function call, which is the final answer of 120.

Here is the complete Java program for this example:

public class FactorialExample {

  public static int factorial(int n) {
    if (n == 1)
      return 1;
    return n * factorial(n-1);
  }

  public static void main(String[] args) {

    System.out.println( factorial(5) );  //120

  }

}

Recursion will make you think on a different level or levels. It will twist your mind like a Droste painting. But recursion will one day come to you, and you will recognize it like an old friend. And together you will navigate the world of programming in ways you never thought of.

Thanks for reading. 😃

Follow me on Twitter @realEdwinTorres for more programming tips and help.