Newsgroups: comp.sys.transputer From: Richard Beton Subject: Re: Is Occam a recursive language ? Organization: Roke Manor Research Limited Date: Tue, 24 Jun 1997 08:16:47 +0100 Mime-Version: 1.0 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <33AF745F.1841CC22@roke.co.uk> egamess@kanaima.ciens.ucv.ve wrote:

I am a new programmer in Occam. Is Occam is a recursive language ?
If yes, can someone write the factorial function ?
Thank you very much for help.

Occam deliberately prevents the expression of recursion. It does this by requiring all identifiers to be in scope at the point they are used, and since it does not have syntax for declaring forward references, it is not possible to write recursive programs.

Why does occam not allow recursion? The primary reason is that occam gains many of its benefits for embedded programming from the compiler's ability to compute (at compile time) exact memory sizes for stacks etc. You know exactly how much memory a given occam program will ever require, because the compiler can tell you that information. The difficulty with recursion is computing the stack size required - this is not possible in the general case (similarly, it is not possible, in general, to confirm that programs containing WHILE loops will ever terminate). Therefore occam does not allow recursion.

There exist mappings for all real recursive programs such that the recursion is replaced by iteration. It then falls to the programmer to provide an array for the data structures which, in the recursive version, would be provided by the compiler using the stack.

Often, however, converting a recursive algorithm to an iterative one actually involves a different algorithm, for the sake of simplicity, transparency and efficiency.

Example: factorial expressed using (illegal) recursion:

INT FUNCTION factorial (VAL INT n)
INT result:
VALOF
    IF
      (n > 1)
        result := n * factorial (n-1)
      (TRUE)
        result := 1
    RESULT result
:

Example: factorial expressed using iteration:

INT FUNCTION factorial (VAL INT n)
INITIAL INT result IS 1:
VALOF
    INITIAL INT x IS n:
    WHILE (x > 1)
      SEQ
        result := result * x
        x := x - 1
    RESULT result
:

Recursion is a concept drilled into mathematics at a very fundamental level. Consequently, it seems hard at first not to use it. It is often the natural way to express an algorithm. However, I have often found iterative algorithms with which I have replaced recursion to be more straightforward and less messy than I would have expected: my experience is that not having recursion has not been a problem. The iterative factorial function (above) illustrates how the program size and complexity do not necessarily increase, whilst the memory requirement becomes fixed at compile time. The iterative factorial would probably execute faster, too.

Regards,
Rick
--
Richard Beton BSc CPhys MInstP
Roke Manor Research Limited
--------- Standard Disclaimer about my own views etc etc --------
Welsh Highland Railway: http://www.whr.co.uk/WHR/WHR.html