4.4 Recursion

We have already seen recursion in the function fib in Section If Statements. Here is another, slightly more complicated example.

We will now write a function to determine the number of partitions of a positive integer. A partition of a positive integer is a descending list of numbers whose sum is the given integer. For example [4,2,1,1] is a partition of 8. Note that there is just one partitio of 0, namely [ ]. The complete set of all partitions of an integer n may be divided into subsets with respect to the largest element. The number of partitions of n therefore equals the sum of the numbers of partitions of n-i with elements less than or equal to i for all possible i. More generally the number of partitions of n with elements less than m is the sum of the numbers of partitions of n-i with elements less than i for i less than m and n. This description yields the following function.

gap> nrparts:= function(n)
>    local np;
>    np:= function(n, m)
>       local i, res;
>       if n = 0 then
>          return 1;
>       fi;
>       res:= 0;
>       for i in [1..Minimum(n,m)] do
>          res:= res + np(n-i, i);
>       od;
>       return res;
>    end;
>    return np(n,n);
> end;
function ( n ) ... end

We wanted to write a function that takes one argument. We solved the problem of determining the number of partitions in terms of a recursive procedure with two arguments. So we had to write in fact two functions. The function nrparts that can be used to compute the number of partitions indeed takes only one argument. The function np takes two arguments and solves the problem in the indicated way. The only task of the function nrparts is to call np with two equal arguments.

We made np local to nrparts. This illustrates the possibility of having local functions in GAP. It is however not necessary to put it there. np could as well be defined on the main level, but then the identifier np would be bound and could not be used for other purposes, and if it were used the essential function np would no longer be available for nrparts.

Now have a look at the function np. It has two local variables res and i. The variable res is used to collect the sum and i is a loop variable. In the loop the function np calls itself again with other arguments. It would be very disturbing if this call of np was to use the same i and res as the calling np. Since the new call of np creates a new scope with new variables this is fortunately not the case.

Note that the formal parameters 'n' and 'm' of 'np' are treated like local variables.

(Regardless of the recursive structure of an algorithm it is often cheaper (in terms of computing time) to avoid a recursive implementation if possible (and it is possible in this case), because a function call is not very cheap.)

[Top] [Previous] [Up] [Next] [Index]