Copyright (c) Theodore Norvell 2017. Licence: Creative Commons Noncommercial Attribution International 4.0.
This is a Jupyter notebook. See How to use these notes.
"Alice had not a moment to think about stopping herself before she found herself falling down what seemed to be a very deep well. ...
"Down, down, down. Would the fall never come to an end?" --Lewis Carrol, Alice's Adventures in Wonderland.
One of the key ideas of recursive programming is that if a recursive program is going to work, there must be at least one case in which subroutine does not call itself. These cases --there could be more than one-- are called the base cases. For example in my definition for combinations.
def combinationsMine( n, r ):
"""
Pre: n and r are integers such that 0 <= r and r <= n
Post: result == the number of subsets of size r of a set of size n
"""
assert isinstance(n, int) and n >= 0
assert isinstance(r, int) and 0 <= r and r <= n
if r == 0: return 1
elif r == n: return 1
else: return combinationsMine(n-1, r-1) + combinationsMine(n-1, r)
The base cases are r==n and r==n
When a base case is called, we call sometime say the recursion has "bottomed out".
So there has to be a bottom.
How can we be sure that our recursion will hit bottom?
The secret is in a function called the variant? If we can find a variant function with the right properties, then the recursion must eventually hit the bottom.
As an example, for the combinationsMine subroutine, a suitable variant function is
$$
f(n, r) = n
$$
The variant function will have the same parameters as the subroutine.
The first property a suitable variant function needs to have is that its value must be a natural number (i.e. an integer greater or equal to 0), provided its prameters respect the precondition of the subroutine. We'll call this property (a). You should check that our example, $f$ obeys this property.
The second property the suitable should have is that its value for any child calls is less than the value for the parent call, assuming the parmeters of the parent call satsify the subroutine's precondition. We'll call this property (b). You should check that our example $f$ obeys this property for the definition of combinationsMine.
As always we require that every child call respects the precondition of the contract, assuming the parent call also respects the precondition of the contract. We'll call this property (c). It's not a property of the variant function, but of the recursive subroutine. You should check that the definition of combinationsMine satisfies this property.
With these three properties ((a) The value of the variant function is natural provided the precondition is respected. (b) The value of the variant function is always smaller than the value for the parent call, provided the parent call respects the precondition. (c) All child calls respect the precondition, provided the parent call respects the precondition.) you can see that any call to a recursive subroutine will eventually get to a base case.
We can prove this using proof by contradiction. Suppose there is a call to our subroutine that respects the precondition, which makes a child call, which makes a grandchild call, that makes a great-grandchild call, and so on infinitely. From property (c), all these child calls respect the precondition. From property (a), the value of the variant function is a natural number, for all these calls. Let's call these natural numbers $n_0$ for the original call, $n_1$ for the child call, $n_2$ for the grandchild call, and so on. From property (b), we have $n_0 > n_1$ and $n_1 > n_2$ and so on infinitely. But of course there is no infinitely long list of natural numbers such that $$ n_0 > n_1 > n_2 > n_3 > ... $$
As an exercise find a suitable variant function for the Factorial example, the Fibonnaci example, and the Partitions example.
From now on, identifying a suitable variant function will be part of the design process.
Very occasionally, we find it difficult to find a suitable variant function by the definition of suitable above. An example is my first solution to the superOperator problem, which was.
def superOpMine( x, y, z ) :
"""
pre: y and z are integers with y >= 1 and z >= 1
post: If z is 1, the result is (...(x+x)+ ...)+x, with y xs.
And if z is 2, the result is (...(x*x)* ...)*x, with y xs
And if z is 3, the result (...(x to the x) to the ... ) to the x, with y xs.
And if z is 4 or more the result is superOpMine( ... superOpMine( superOpMine(x, x, z-1), x, z-1) ..., x, z-1), with y xs.
"""
assert isinstance(y, int) and y >= 1
if y==1: return x
elif z==1: return superOpMine( x, y-1, 1) + x
else: return superOpMine( superOpMine( x, y-1, z), x, z-1)
We can't use the function
$$
f(x, y, z) = z
$$
since it doesn't obey property (b) for the calls superOpMine( x, y-1, 1) and superOpMine( x, y-1, z). We can't use the function
$$
f(x, y, z) = y
$$
since it doesn't necessarily obey property (b) for the call superOpMine( superOpMine( x, y-1, z), x, z-1). We can't use
$$
f(x, y, z) = x
$$
since it doesn't necessarily obey property (b) for either recursive call.
It turns out there is no simple suitable variant function for this particular recursive subroutine if we use our definition of suitable above.
To accomodate recursive subroutines like superOpMine, we can change the definition of suitable, just a litte. First we need a bit of mathematics.
A sequence $n_0$, $n_1$, $n_2$, ..., whether infinite or finite is called a descending sequence if $$ n_0 > n_1 > n_2 > ... $$
A set $S$ together with a relation $>$ is called a well founded set if there are no infinite descending sequences $n_0$, $n_1$, $n_2$, ... of elements of $S$.
Clearly the natural numbers together with the usual $>$ relation is a well founded set. The integers are not, since we have $$ 2 > 1 > 0 > -1 > -2 > .. $$ Nor are the postitive rational numbers together with the usual $>$ relation, since we have $$ 1 > 1/2 > 1/3 > 1/4 > ... $$
Pairs of natural numbers are a well founded set, if we define $>$ as lexicographic ordering, which means $$ (a, b) > (c, d) \;\text{if and only if}\; a > c \; \text{or} \; (a=c\;\text{and}\;b > d $$ If a decending sequence starts with $(a,b)$, then after at most $b$ steps the first component has to decrease, and then after a finite number of steps, the first component has to decrease again. So there can't be an infinite decending sequence. For example starting with $(1,3)$, I can make a sequence $$ (1,3) > (1,2) > (1,1), > (1,0) > (0, 2) > (0, 1) > (0, 0) $$ And the sequence must end here. I can make a descending sequence starting with $(1,3)$ any finite length I want, but it has to be finite.
So all we need to do is modify our definition of suitable so that instead of having to compute a natural number in property (a), it can compute a member of any well founded set. And we need to use the order of the well founded set in property (b).
For superOpMine, can you find a suitable variant function?