Recursion

A function definition may contain calls to library functions as well as calls to functions defined in the program. In particular, a function may call itself (either directly or through other functions), in which case the function definition is said to be recursive.

A function may have to be defined recursively if the set of arguments for which the function is defined is infinite, and there is no limitation on the size of the arguments.

Let us consider, for example, the following problem. Suppose we have to define a function Reverse that "reverses" a ground expression by rearranging its top-level terms in reverse order. Thus, if the argument has the form 
    Gt1 Gt2 ... Gtn
where Gt1, Gt2, ..., Gtn are ground terms, then the function is to return the ground expression 
    Gtn ... Gt2 Gt1
If the length of the argument expression were limited, for example, if we knew that n<=3 , we could consider four separate cases to produce the following function definition 
$func Reverse e.Exp = e.Exp;

Reverse
  {
  = ;
  t1 = t1;
  t1 t2 = t2 t1;
  t1 t2 t3 = t3 t2 t1;
  };

There is no limit on the length of the input expressions, however. Thus, the function definition has to consider an infinite number of cases, which seems to imply that the program has to be infinite in size.

This difficulty, however, can be circumvented by means of recursion. We can reason in the following way. Let us consider an argument expression 
    Gt1 Gt2 ... Gtn
If n=0 , then the result to be returned is the empty expression. Otherwise, if n>=1 , the problem can be reduced to a less difficult one. Namely, by discarding the first term in the argument expression we get the expression 
    Gt2 ... Gtn
which is n-1 terms in length. By reversing this expression we get 
    Gtn ... Gt2
Now, by adding Gt1 to the end of the expression, we get the desired result 
    Gtn ... Gt2 Gt1
Reasoning in this way, we come to the following recursive definition of the function Reverse: 
Reverse
  {
  = ;
  t.X e.Rest = <Reverse e.Rest> t.X;
  };
It is interesting that there exists another solution to the problem of the expression reversion, which is in no way worse than the above. Namely, the problem can be reduced to a less difficult one by discarding the last term, rather than the first one, in which case we get the following solution: 
Reverse
  {
  = ;
  e.Rest t.X = t.X <Reverse e.Rest>;
  };
It can be easily seen that the essence of the solution consists in dividing the original expression Ge into two smaller non-empty expressions Ge1 and Ge2 such that 
    Ge = Ge1 Ge2
Now, each of the expressions Ge1 and Ge2 can be reversed separately. Let the corresponding expressions obtained be Ge'1 and Ge'2. Then the expression 
    Ge'2 Ge'1
is obviously the result of reversing the original expression Ge.
If Refal Plus is implemented for a multi-processor computer in such a way that the reversion of Ge1 and Ge2 can be performed simultaneously, it is advantageous to make Ge1 and Ge2 approximately equal in length. In this way we get the following modification of the above function definition, in which there are calls to library functions from the modules Access and Arithm: 
$func Reverse e.Exp = e.Exp;

Reverse
  {
  = ;
  t1 = t1;
  eX,
    <Length e.X> :: sLen,
    <Div sLen 2> :: sDiv,
    = <Reverse <Middle sDiv 0 eX>>
    <Reverse <Left   0 sDiv eX>>;
  };
Parent topic: Functions Defined in the Program