Learn Recursion From Zero to One

I remember seeing my little nephew counting. He would look at the buttons on an elevator, and count:

0, 1, 2, 3, 4, 5, 6, ...

They are natural numbers. This usual form of writing number is called Hindu-Arabic numerals. In the past Europe, though, people used Roman numerals:

, I, II, III, IIII, V, VI, ...

Could you see some patterns?

• There is no symbol for zero. Zero is nothing.
• One is I, or, nothing followed by I.
• Two is II, or, one followed by I.
• Three is III, or, two followed by I.
• Four is IIII, or, three followed by I.

Let's pretended that space is not a problem, then five can be IIIII instead of V, and six can be IIIIII instead of VI.

• Five is IIIII, or, four followed by I.
• Six is IIIIII, or five followed by I.
• And so on ...

When I see my nephew counting the numbers on the elevators, he knows they are floor numbers. One day I want to tell him, that the first floor is built on the ground, the second floor is built on the first floor, the third floor is built on the second floor, and so on ... , and that is recursion. (One day.)

That is recursion! The earliest experience we probably all have with recursion is when we started counting numbers. Or, at least, when we realized that we can count beyond our hands, beyond elevator buttons, beyond written numerals, all the way into infinity.

It is tiring to write all the "I... followed by I", not to mention impossible to write it for every one of the infinitely many natural numbers. Instead, we can write the first case, which is nothing, and describe all the following cases in terms of ... what? We might want to say "the previous natural number", but even the concept of "the previous" is yet to be defined. So we can only say "a natural number", without referring to any specific one.

• Zero is natural number. Zero is nothing.
• Each natural number is a natural number followed by I.

Therein comes the usual definition of recursion: the reference or usage of a definition in itself. The first line is called "the base case", while the second line is called "the recursive step".

I hope the plain English explanation of recursion above has helped you grasp this powerful idea. Over the years people have developed various notations for recursion. I would like to use two notations, noting their differences and commonalities, so we can feel at home with familiar notations, but also explore alternatives for different perspectives.

First, let's look at the Haskell notation.

-- Haskell 1
data Nat = Zero | I Nat

zero  = Zero
one   = I Zero
two   = I (I Zero)
three = I (I (I Zero))

We name our natural number type Nat, give it a base case Zero, and then the recursive step I Nat, connected by the or operator | (vertical bar). In the recursive step, I is the constructor, and it takes Nat as a parameter.

We can construct the base case, zero, with Zero. We can also pass the base case from Zero to I to get one. We can pass I Zero, which is one, again to I to get two. And so on.

Unfortunately due to the syntax of Haskell, instead of following a Nat by I, like we described in plain English, we have to lead by I. Hopefully we can adapt to counting forward.

The Haskell notation is clean for showing such constructions, but is probably not familiar to most programmers. Therefore, I present the roughly equivalent Java version.

// Java 1
class Nat {
    Nat prev;

    Nat() { this.prev = null; }
    Nat(Nat n) { this.prev = n; }
    static Nat Zero() { return new Nat(); }
    static Nat I(Nat n) { return new Nat(n); }
}

class Main {
    public static void main (String[] argv) {
        Nat zero  = Nat.Zero();
        Nat one   = Nat.I(Nat.Zero());
        Nat two   = Nat.I(Nat.I(Nat.Zero()));
        Nat three = Nat.I(Nat.I(Nat.I(Nat.Zero())));
    }
}

We name our natural number class Nat, with a reference to the same class named prev, meaning that it refers to the previous number. We then have the two constructors, Zero and I, in the form of overloaded Nat. For clarity, we alias the overloaded constructors with static methods of the proper names.

We can construct the base case, zero, with Zero(). We can also pass the base case from Zero() to I() to get one. We can pass I(Zero()), which is one, again to I() to get two. And so on.

Before further dealing with the recursive structure of Nat, let's go back to our childhood, and try to count it. For counting, we write "increment" and "decrement". "increment" is really another name for the I constructor. Pairing with it, "decrement" takes the previous number out. Let's write them in Haskell.

-- Haskell 2
increment       = I
decrement Zero  = undefined
decrement (I n) = n

In decrement we need to consider two cases. Because we do not define negative numbers for our Nat type, we do not define the result of decrement Zero either. For any Nat of the form I n, the result of decrement is simply n.

// Java 2
class Nat {
    Nat increment() { return Nat.I(this); }
    boolean isZero() { return this.prev == null; }
    Nat decrement() throws Exception { 
        if (this.isZero()) {
            throw new Exception("Cannot decrement Zero");
        } else {
            return this.prev;
        }
    }
}

Following Java convention, we define increment() and decrement() as instance methods. increment() aliases I(). For decrement(), we throw an Exception to indicate we cannot decrement Zero() in that case, otherwise we return this.prev.

I really hope that you have not met any problem so far. Because if you have, it is hard to debug this little mess when we don't know how to print any of Nat out. Let's print our Nat in Roman numerals!

-- Haskell 3
toRomanNumerals Zero  = ""
toRomanNumerals (I n) = (toRomanNumerals n) ++ "I"

Following our plain English description, Zero is nothing, a.k.a. an empty string. Every other Nat is its previous number in Roman numerals followed by one additional "I". Surprise, surprise, this is a recursive function!

But also notice how similar it is to decrement. On the left hand side they are the same (except for the name of course)! But instead of taking out the previous number, we apply toRomanNumerals again to it, which applies toRomanNumerals again to its previous number, which applies toRomanNumerals to the previous number of its previous number, ... Nah, that's not very clear. Let's see an example.

   toRomanNumerals (I (I (I Zero)))
=> (toRomanNumerals   (I (I Zero)))                 ++ "I"
=> ((toRomanNumerals     (I Zero))          ++ "I") ++ "I"
=> (((toRomanNumerals       Zero)   ++ "I") ++ "I") ++ "I"
=> ((""                             ++ "I") ++ "I") ++ "I"
=> ("I"                                     ++ "I") ++ "I"
=> "II"                                             ++ "I"
=> "III"

I've lined everything up so hopefully you can see the correspondence between steps. This is similar to how you would simplify an algebraic expression step by step in high school. Call it simplify, or reduce, or evaluation. Notice how as we take one step down, toRomanNumerals moves across a parenthesis inwards, (I (I (I Zero))) is peeled one level like an onion, and the peel becomes ++ "I", waiting for the inner to simplify first.

Try some more examples yourself! The more you practice, the more you would understand it. Make variations!

The Java equivalent looks like this:

// Java 3
class Nat {
    static String toRomanNumerals(Nat n) {
        if (n.isZero()) {
            return "";
        } else {
            return toRomanNumerals(n.prev) + "I";
        }
    }
}

We see again similarity with decrement, this time in the form of the if statement.

For convenience, we can add necessary ceremonies to integrate toRomanNumerals into the usual printing utilities of the languages.

-- Haskell 4
instance Show Nat where
    show = toRomanNumerals

main = do
    print zero
    print one
    print two
    print three

// Java 4
class Nat {
    public String toString() {
        return Nat.toRomanNumerals(this);
    }
}

class Main {
    public static void main (String[] argv) {
        System.out.println(zero);
        System.out.println(one);
        System.out.println(two);
        System.out.println(three);
    }
}

This is only the beginning. Next post, let's explore how we can define plus and minus operation on this model. Then, we will see how this is all related to Linked List, one of the classic data structure.

1. Personally, I had much pain learning recursion, because the professor only introduced it with Fibonacci sequence and went on straight to the tree traversals. That is when recursion becomes almost absolutely necessary, but not when recursion is the easiest to understand. I hope you find this post helpful in your understanding of recursion.

2. Hindu-Arabic numerals were revolutionary for simplifying arithmetic. In exchange, their recursive structure is more complicated.

3. IIII is the additive notation, and is more suitable for the story I am telling. The also common subtractive notation is written as IV. According to Wikipedia.

4. For maths nerds, and I beg mathematicians for forgiveness of this abusing of mathematical analogy: Countable infinity is defined in terms of natural numbers. Natural numbers can be defined in terms of induction, roughly recursion, by [Peano axiom]. Therefore, countable infinity can be defined in terms of recursion. That is one semantic by which recursion may represent infinite loop in computation. Or, without tail call optimization, stack overflow.

5. You may try the code yourself in the Haskell REPL and Java REPL by repl.it.

6. When running Haskell code in repl.it, if you see the error Variable not in scope: main, put main = return () at the end. After running the Haskell code, you can still type any name after the output and press Enter to have its value printed out, or type :t <name> to see its type.

7. When running Java code, please append the code within the same block together between the curly braces. For example, combine code pieces class Nat { a; } and class Nat { b; } into class Nat { a; b; } before running.

8. When running code piece Haskell 3, you may be confused why it doesn't print an empty line at the beginning like Java 3 does. Both of them print a line break to begin with, but the Haskell environment has an additional prompt symbol preceding the printed line break.

9. For basics about Haskell, try Haskell. For basics about Java, learn Java online.

10. If you have realized that the Java code is only one data field away from a linked list, you are right! It is also the case for Haskell.

11. This article may be regarded as a primitive form of literary programming.

If you feel that you've got something from this post, I am glad! Please don't hesitate to comment or reach out.

If you feel that you've got enough that you'd like to donate, please donate to Wikimedia Foundation, to which I owe infinitely.