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>>; };