convert a recurrence into a function - Maple Help

Online Help

All Products    Maple    MapleSim

Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : gfun : gfun/rectoproc

gfun[rectoproc] - convert a recurrence into a function

Calling Sequence

rectoproc(eqns,u(n), remember, list,params=[a,b,...],<options>)




single equation or set of equations



name; recurrence name



name; index of recurrence u



(optional) name; specify that returned procedure uses option remember



(optional) name; specify that returned procedure computes the list [u(0), ..., u(n)]

params = [a, b, ...]


(optional) names; argument names

evalfun = fname


(optional) a function applied at each iteration

preargs=[c, d, ...]


(optional) first arguments to this function

postargs=[e, f, ...]


(optional) last arguments to this function






(optional) while condition



(optional) error condition









(optional) copyright string to be added to the options

extralocal=[g, h, ...]


(optional) names for extra local variables






The rectoproc(eqns, u(n)) command returns a Maple procedure that, given a non-negative integer n as input, returns the nth term u(n) of the linear recurrence.


If remember is specified, the function returns a procedure that uses option remember.


If the optional argument remember is supplied, the procedure returned will use option remember.


If list is specified, the returned procedure computes the list &lsqb;u0,...,un&rsqb;. In this case it runs in a linear number of arithmetic operations.


One of the optional arguments remember or list should be given each time one needs a large number of values of the sequence. When the first terms of the recurrence are not explicitly supplied, they are represented symbolically.


If params=&lsqb;a,b,...&rsqb; is specified, the function returns a procedure that accepts n, a, b,... as input.


If the coefficients of the recurrence are nonconstant polynomials, the returned procedure runs in a linear number of arithmetic operations without using extra space if the remember option is not specified.


If the coefficients are constant, the returned procedure runs in a logarithmic number of arithmetic operations without using extra space if the remember option is not specified.


If the optional argument evalfun=fname is given, then the specified procedure is used in the generated code as an evaluation rule. Extra arguments can be passed to the procedure with options preargs= &lsqb;c,d,...&rsqb; and postargs= &lsqb;&ExponentialE;,f,...&rsqb;. Names declared in preargs and postargs may appear in the argument sequence of the generated procedure if they are also declared with the option params. The function is mapped over initial conditions and it is evaluated before procedure generation if the option evalinicond is supplied.


The option whilecond=boolean_expr defines a condition that is checked at each iteration of the loop of the generated procedure. The condition is represented by a boolean expression that may be function of n, unk for any positive integer k and function of the names declared in params, preargs and postargs. Execution stops when the condition turns true. This option does not impact initial conditions.


The option errorcond=boolean_expr defines a condition that is checked at each iteration of the loop of the generated procedure. The condition is represented by a boolean expression that may be function of n, unk for any positive integer k in 0..ord - where ord is the order of the recurrence - and function of the names declared in params, preargs and postargs. An error is thrown when the condition turns true.


The option extralocal= &lsqb;g,h,...&rsqb; allows to declare and initialize extra local variables. g, h, ... must be either symbols or equations in the form symbol=expression, in which case the expression is used for initialization.


The option nosymbolsubs disables the name substitution that occurs for the parameters (declared with the option params). This means that the symbols that are used in the generated procedures are the same as the symbols used in the input recurrence. By default, the symbols that are used in the generated procedures are gathered in the global table gfun/rectoproc/symbol.


The option index makes the generated procedure return the list n&comma;un. This is useful in conjunction with whilecond.


You should specify remember or list each time a large number of values for the sequence is required.


The option rhs=expression allows to specify a right hand side of the recurrence that does not have to be a polynomial. The right hand side may be function of n and of the names declared in the options params, preargs and postargs.


Fibonacci numbers

You can create different types of programs to generate Fibonacci numbers that meet certain memory or time requirements.

The most obvious procedure is recursive and "remembers" values that are already computed.






fib1:=procnoptionremember&semi;procname&minus;2&plus;n&plus;procname&minus;1&plus;nend proc





To create a program which computes and lists the first n terms of the recurrence, we use the list option.


fib2:=procnlocali1&comma;loc&semi;loc&lsqb;0&rsqb;:=1&semi;loc&lsqb;1&rsqb;:=1&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc&lsqb;0&rsqb;elifn&equals;1thenreturnloc&lsqb;1&rsqb;end if&semi;fori1to&minus;1&plus;ndoloc&lsqb;i1&plus;1&rsqb;:=loc&lsqb;&minus;1&plus;i1&rsqb;&plus;loc&lsqb;i1&rsqb;end do&semi;seqloc&lsqb;i1&rsqb;&comma;i1&equals;0..nend proc





To create a program that is more space conscious we avoid the remember option. In this case the program exploits the fact that the recurrence has constant coefficients for extra efficiency.


fib3:=procnlocali1&comma;loc0&comma;loc1&comma;loc2&comma;tmp2&comma;tmp1&comma;i2&semi;ifn<=44thenloc0:=1&semi;loc1:=1&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc0elifn&equals;1thenreturnloc1end if&semi;fori1to&minus;1&plus;ndoloc2:=loc0&plus;loc1&semi;loc0:=loc1&semi;loc1:=loc2end do&semi;loc1elsetmp2:=`Matrix(2, 2, {(1, 1) = 1, (1, 2) = 1, (2, 1) = 1, (2, 2) = 0})`&semi;tmp1:=`Vector(2, {(1) = 1, (2) = 1})`&semi;i2:=convert&minus;1&plus;n&comma;base&comma;2&semi;ifi2&lsqb;1&rsqb;&equals;1thentmp1:=`Vector(2, {(1) = 2, (2) = 1})`end if&semi;fori1insubsop1&equals;&comma;i2dotmp2:=`LinearAlgebra:-MatrixMatrixMultiply`tmp2&comma;tmp2&semi;ifi1&equals;1thentmp1:=`LinearAlgebra:-MatrixVectorMultiply`tmp2&comma;tmp1end ifend do&semi;tmp1&lsqb;1&rsqb;end ifend proc








An example of right-hand side: nested procedures

This example shows how terms of nested recurrences can be computed. The first sequence is first converted into a procedure:




u_n := rectoproc(rec_u,u(n),remember);

u_n:=procnoptionremember&semi;2&ast;procname&minus;2&plus;n&plus;4&ast;procname&minus;1&plus;nprocname&minus;2&plus;n&plus;procname&minus;1&plus;n&ast;n&sol;3&plus;&minus;3&plus;n&ast;nend proc


The second sequence is defined by







The procedure computing vn is now generated

v_n:=rectoproc({op(1,rec_v)}union ini_v,v(n),rhs=subs(u=u_n,op(2,rec_v)),list);

v_n:=procnlocali1&comma;loc&semi;loc&lsqb;0&rsqb;:=1&semi;loc&lsqb;1&rsqb;:=2&semi;loc&lsqb;2&rsqb;:=3&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc&lsqb;0&rsqb;elifn&equals;1thenreturnloc&lsqb;1&rsqb;elifn&equals;2thenreturnloc&lsqb;2&rsqb;end if&semi;fori1from2to&minus;1&plus;ndoloc&lsqb;i1&plus;1&rsqb;:=u_n&minus;1&plus;i1u_n&minus;2&plus;i1&ast;&minus;2&plus;i13&plus;&minus;3&plus;i1&ast;i1&plus;1&ast;loc&lsqb;&minus;1&plus;i1&rsqb;&sol;i1&plus;2end do&semi;seqloc&lsqb;i1&rsqb;&comma;i1&equals;0..nend proc


Computation of 10 first terms:




Applying a function at each iteration

We illustrate several ways to compute numerical values of the sequence defined by the following recurrence:




If hardware floating point numbers give a sufficient accuracy, then it is best to produce the procedure and then call evalhf on it:


p:=procnlocali1&comma;loc0&comma;loc1&comma;loc2&semi;loc0:=sin1&semi;loc1:=cos1&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc0elifn&equals;1thenreturnloc1end if&semi;fori1to&minus;1&plus;ndoloc2:=&minus;5&plus;&minus;3&plus;i1&ast;i1&plus;1&ast;loc0&sol;i1&semi;loc0:=loc1&semi;loc1:=loc2end do&semi;loc1end proc





If more precision is required, then evalf can be applied at each iteration using


p2:=procnlocali1&comma;loc0&comma;loc1&comma;loc2&semi;loc0:=evalfsin1&semi;loc1:=evalfcos1&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc0elifn&equals;1thenreturnloc1end if&semi;fori1to&minus;1&plus;ndoloc2:=evalf&minus;5&plus;&minus;3&plus;i1&ast;i1&plus;1&ast;loc0&sol;i1&semi;loc0:=loc1&semi;loc1:=loc2end do&semi;loc1end proc





It is also possible to give the precision as an argument:

p3 := rectoproc(rec,u(n),evalfun='evalf',params=[d],postargs=[d]);

p3:=procn&comma;b1locali1&comma;loc0&comma;loc1&comma;loc2&semi;loc0:=evalfsin1&comma;b1&semi;loc1:=evalfcos1&comma;b1&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc0elifn&equals;1thenreturnloc1end if&semi;fori1to&minus;1&plus;ndoloc2:=evalf&minus;5&plus;&minus;3&plus;i1&ast;i1&plus;1&ast;loc0&sol;i1&comma;b1&semi;loc0:=loc1&semi;loc1:=loc2end do&semi;loc1end proc





Extra local variables

The option extralocal is useful when the values of some parameters are not known until the procedure is executed. In the example below, the recurrence is provided with generic initial conditions. The values of these initial conditions are computed at execution-time.

To create a procedure which computes and lists the first n terms of the recurrence, use the list option.



procn&comma;b1locali1&comma;loc0&comma;loc1&comma;loc2&comma;xloc1&comma;xloc2&semi;xloc1:=fb1&semi;xloc2:=gxloc1&comma;b1&semi;loc0:=xloc1&semi;loc1:=xloc2&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc0elifn&equals;1thenreturnloc1end if&semi;fori1to&minus;1&plus;ndoloc2:=&minus;&minus;1&plus;i1&ast;loc0&semi;loc0:=loc1&semi;loc1:=loc2end do&semi;loc1end proc


See Also

gfun, procedure, remember

Download Help Document

Was this information helpful?

Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam