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

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

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 ) )) = 6In 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.

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

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

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.

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.

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

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

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: