2. Recursive Definitions

First, we will look at the use of recursion as a method for describing/specifying something.

2.1. Everyday Examples

Royalty:: A person is royal if he is a monarch, or is descended from a royal person.
Citizenship:: A person is a Canadian citizen if he was born in Canada, or has acquired citizenship after emigrating to Canada, or has a parent who is a Canadian citizen.

2.2. Mathematical Examples

Functions are very often defined recursively. The classic example is the factorial function

        factorial(0) = 1
        factorial(n) = n * factorial(n-1)   [for n>0]

This definition is concise and very easy to understand and to use. Let's compute factorial(3).

   factorial(3) = 3 * factorial(2)
                = 3 * ( 2 * factorial(1) )
                = 3 * ( 2 * ( 1 * factorial(0) ))
                = 3 * ( 2 * ( 1 *      1     ) ))
                = 6

In general, a recursive definition is made up of two parts. There is a base case that tells us directly what the answer is, and there is a recursive case that defines the answer in terms of the answer to some other, related problem.

In factorial, the base case is factorial(0)=1, this directly tells us the answer; the recursive case is factorial(n) = n * factorial(n-1). This does not directly tell us the answer, but tells how to construct the answer for factorial(n) on the basis of the answer to the related problem, factorial(n-1).

The Royalty and Citizenship definitions are just the same - there is a base case, which directly determines royalty or citizenship, and a recursive case, which defines the royalty/citizenship of one person in terms of the royalty/citizenship of some other person.

Another classic is the Fibonacci function:

      fibonacci(0) = 1
      fibonacci(1) = 1
      fibonacci(n) =  fibonacci(n-1) + fibonacci(n-2)   [for n>1]

This definition is a little different than the previous ones because

It has two base cases, not just one; in fact, you can have as many as you like.
In the recursive case, there are two recursive calls, not just one. There can be as many as you like.

Let's compute fibonacci(4) to see how the definition works:

fibonacci(4)
=  fibonacci(3)                  + fibonacci(2)
= (fibonacci(2)  + fibonacci(1)) + (fibonacci(1) + fibonacci(0))
= ((fibonacci(1) + fibonacci(0)) + 1) + (1 + 1)
= (     1        +      1      ) + 1) + (1 + 1)
= 5

2.3. Computing Examples

Definition of a Stack

In the first lecture, I gave you an intuitive definition of a stack, drawing an analogy with everyday `stacks' of books, papers, etc. And I also gave a purely behavioural definition - a stack is anything on which you can perform the operations POP, PUSH etc. as specified. This is a perfectly valid definition, and a very useful one too, because it leaves us entirely free to impose any shape or structure on a stack that we like (as long as we can still perform the operations). There is also a structural definition, that defines a stack in terms of its `structure':

A stack is either EMPTY
or it consists of two parts: (1) a `top' value and (2) a `remainder', which is a stack.

This follows our normal pattern for a recursive definition. There is a base case, which tells us directly that EMPTY is a valid value for a stack to have. Then there is the recursive case, which tells us how to determine if a value is a valid stack by looking at its two parts and checking that they have appropriate values.

For example, consider the value S = (7, (29,(11,EMPTY))).

We can use the above definition to recognize that this is a valid stack. S has two parts, we'll regard the first part (7) as its `top', and the second part as its `remainder' = (29,(11,EMPTY)). According to the definition, S is a valid stack providing that this remainder is a valid stack. Is it?

Well, it has two parts; its `top' (first part) is 29, and its second part, or `remainder', is (11,EMPTY). So this will be a valid stack value providing that this `remainder' is a valid stack. We apply the definition to this remainder. (11,EMPTY) has two parts, `top'=11, and `remainder'=EMPTY, and it is a valid stack providing that its remainder is a valid stack.

The base case allows us to immediately recognize that EMPTY is a valid stack. And this allows us to conclude that (11,EMPTY) is a valid stack. This, in turn, allows to conclude that (29,(11,EMPTY)) is a valid stack, and this, finally, allows us to conclude that our original stack, S =(7,(29,(11,EMPTY))) is indeed a valid stack.

Recursive definitions of data types are extremely common in Computer Science. We will see them throughout the course - for lists, and trees, and all the variations of them that we study. They have the advantage that they give great insight into how many basic operations can be performed.

For example, the recursive definition of `stack' we've just seen suggests we could implement stacks, with a `pair', that is, a record/structure having two parts, one of type `value', one of type stack. With this implementation, we can pop a stack S, just by returning its remainder, POP(S) = S.remainder, and we can PUSH value V onto stack S just by creating the pair (V,S). You can see that the definition itself has given us very strong guidance in implementing the basic operations on the data type.

Definition of an Arithmetic Expression

All programming languages allow you to write arithmetic expressions such as 5*(2+3). How can we define the concept of arithmetic expression? The only way, really, is to do it recursively.

An arithmetic expression is any of the following:

a numeric constant
an identifier (of a numeric type variable or constant)
an arithmetic expression enclosed in parentheses
two arithmetic expressions separated by a binary arithmetic operator.

Definitions such as this are used universally to define the syntax of programming languages, and the first step in any compiler is to use these definitions to uncover the basic building blocks and organization of your program. This process is called `parsing', and the result is a parse tree.

The process is actually very similar to the one we just used when we verified that S was valid stack. You repeatedly apply the definitions to break a given value into parts, and then check the validity of each of the parts. The base cases give you direct answers about the validity of certain values.

For example, we can use the above definition to parse this input:

                5 * (2 + 3)

Apply rule 4. This breaks the given input into 3 parts, 5, *, (2+3) and imposes these constraints on them:

(a) 5 must an arithmetic expression
(b) * must a binary arithmetic operator
(c) (2 + 3) must be an arithmetic expression

Once these have been verified, we know that our original input is a valid arithmetic expression.

We verify (a) by application of rule 1, and (b) by looking up * in a list of known binary arithmetic operators. All that remains, in order to show that our original input is a valid expression, is to verify (c).

Verifying (c) requires several steps:

First, apply rule 3: This says that (2 + 3) is an arithmetic expression only if 2 + 3 is an arithmetic expression.

To verify that 2+3 is a valid expression, we apply rule 4. This breaks 2+3 into 3 parts, 2, +, and 3 and imposes these constraints:

(d) 2 must an arithmetic expression
(e) + must a binary arithmetic operator
(f) 3 must be an arithmetic expression

We verify (d) and (f) by rule 1, and (e) by looking up + in a list of known binary arithmetic operators. Thus we have verified all the conditions necessary to show that our initial input is a valid expression.

This process not only gives us a `yes/no' answer, the trace of the verification steps shows us the structure of the expression. This is called the parse tree of the expression: