Re: recursive relationship

joe_celko_at_my-deja.com writes:

>>> I do not understand very well the concept of a recursive
>relationship. Could someone please explain and give me an example? <<
 

>There are two fundamental ways to define something: (1) Intention and
>(2) Extension. An Intentional definition gives a list of the elements
>in the relationship ("THIS is what I mean!"). An Extentional definition
>gives a rule to determine if an element is or is not in the
>relationship. Recursion is a special kind of extentional definition.

Wrong way round. An extensional definition lists the exemplars, and an intenSional one uses rules.

>It uses the rule itself to define the rule. For example, the factorial
>function can be recursively defined by the rule that
 

> n! := IF (n = 0)
> THEN 1
> ELSE n *(n-1)!
> END IF;
 
> 4! = 4 * 3!
> = 4 * 3 * 2!
> = 4 * 3 * 2 * 1!
> = 4 * 3 * 2* 1 * 0!
> = 4 * 3 * 2* 1 * 1 = 24
 

>There are also many kinds of recursion -- simple, primitive, non-
>primitive, etc. -- if you want to bored to death, ask a mathematician
>about them. All finite recursive definitions must have a "fixed
>point", which is something that stops recursing (i.e. (n=0) in this
>example).

This is usually called a base case. A fixed point (or fixpoint) of a function is something else (a value x such that f(x) = x).

A good example of a recursive relation is the ancestor relation:

ancestor(x,y) <- parent(x,y).			Base case
ancestor(x,y) <- parent(x,z), ancestor(z,y).	Recursive case

David Received on Fri Jan 14 2000 - 00:00:00 CET