Learn Recursion From Zero to One
Tags: computerscience, beginners, functional, java
Published: 2020-04-03 07:17:06

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
-- 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
// 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
-- 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
// 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
-- 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.

```haskell
   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
// 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
-- Haskell 4
instance Show Nat where
    show = toRomanNumerals

main = do
    print zero
    print one
    print two
    print three
```

```java
// 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.

---

0. 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.

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

2. `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](https://en.wikipedia.org/wiki/Roman_numerals#%22Standard%22_forms).

3. 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.

[Peano Axioms]: https://en.wikipedia.org/wiki/Peano_axioms

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

[Haskell REPL]: https://repl.it/languages/haskell
[Java REPL]: https://repl.it/languages/java

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].

[try Haskell]: https://www.tryhaskell.org/
[learn Java online]: https://www.learnjavaonline.org/

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](http://www.literateprogramming.com/).

---

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](https://donate.wikimedia.org), to which I owe infinitely.