Correctness #

To check whether a recursive method is correct, it is (usually) sufficient to check that the two following two properties hold:

(Base case(s)). The method is correct for the smallest possible inputs.

(Inductive case). For an arbitrary $n$:

$\qquad\qquad$ if the method is correct for all inputs of size $\leq n$, then it is correct for all inputs of size $n+1$.

Example. Consider the algorithm seen earlier to compute the sum of all nodes in a binary tree, if nodes are instance of the following class:
1
2
3
4
5
6
7
8
int sum(Node root){
    // base case
    if (root == null){
        return 0
    }
    // inductive case
    return root.value + sum(root.leftChild) + sum(root.rightChild)
}
For the size $n$ of the input, we can use in this example the height of the tree (i.e. the length of its longest branch).

Let use verify that our two properties hold:

(Base case). The sum of all labels in an empty tree is 0, so the method is trivially correct.

(Inductive case). Consider any natural number $n$, and any tree of height $n+1$, with root $r$. And let us assume that the method sum is correct for all trees of height $\le n$. We need to show that under this assumption, the method is correct for the tree rooted in $r$.

Observe that the subtrees rooted in r.left and r.right have height $\le n$.

So from our assumption, the two recursive calls (Line 6) to the method sum are correct, meaning that they return the sum of all values in each of the two subtrees.

Next, observe that the sum of all labels in our tree must be equal to the sum of all values in these two subtrees, plus the label of $r$. Which is precisely what the method returns.

These two properties (1 and 2 above) provide an immediate proof by induction that the method is correct for all inputs.

Proof. Partition the set of all possible inputs by size, i.e. (assuming that inputs in our base case have size 0):

the set $S_0$ of all inputs of size $0$,

the set $S_1$ of all inputs of size $1$,

the set $S_2$ of all inputs of size $2$,

etc.

In order to show that the method is correct, it is sufficient to show that it is correct for each $S_i$ (where $i \in \mathbb{N}$).

Now let us assume that properties 1 and 2 hold, i.e.:

(Base case). The method is correct for $S_0$.

(Inductive case). For any $n$,

$\qquad\qquad$ if the method is correct for $S_0 \cup S_1 \cup … \cup S_n$, then it is correct for $S_{n+1}$.

We know that Property 2 holds for an arbitrary $n$. In particular, it holds for $n= 0$. In other words (replacing $n$ with $0$):

If the method is correct for $S_0$, then it is correct for $S_1$.

So from Properties 1 and 3, we can infer:

The method is correct for $S_1$.

$\qquad$

Next, consider the case where $n = 1$. From Property 2 still, we know (replacing $n$ with $1$) that:

If the method is correct for $S_0 \cup S_1$, then it is correct for $S_2$.

So from Properties 1 and 4 and 5, we can infer:

The method is correct for $S_2$.

$\qquad$

etc.