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 the optional argument remember is supplied, the procedure returned will use option remember.

If list is specified, the returned procedure computes the list $\[u\left(0\right),...,u\left(n\right)\]$. 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 $\mathrm{params}=\[a,b,...\]$ 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= $\[c,d,...\]$ and postargs= $\[\ⅇ,f,...\]$. 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, $u\left(n-k\right)$ 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, $u\left(n-k\right)$ for any positive integer k in $0..\mathrm{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= $\[g,h,...\]$ 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 $\left[n\,u\left(n\right)\right]$. 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.

$\mathrm{fiborec}≔\left\{f\left(0\right)=1\,f\left(1\right)=1\,f\left(i\right)=f\left(i-1\right)+f\left(i-2\right)\right\}$

$\mathrm{fiborec}≔\left\{f\left(0\right)=1\,f\left(1\right)=1\,f\left(i\right)=f\left(i-1\right)+f\left(i-2\right)\right\}$

$\mathrm{with}\left(\mathrm{gfun}\right)\:$

fib1:=rectoproc(fiborec,f(i),remember);

$\mathrm{fib1}≔\mathbf{proc}\left(n\right)\mathbf{option}\mathrm{remember}\;\mathrm{procname}\left(\−2\+n\right)\+\mathrm{procname}\left(n-1\right)\mathbf{end\; proc}$

$\mathrm{fib1}\left(100\right)$

$573147844013817084101$

fib2:=rectoproc(fiborec,f(i),list);

$\mathrm{fib2}≔\mathbf{proc}\left(n\right)\mathbf{local}\mathrm{i1}\&comma;\mathrm{loc}\&semi;\mathrm{loc}\&lsqb;0\&rsqb;≔1\&semi;\mathrm{loc}\&lsqb;1\&rsqb;≔1\&semi;\mathbf{if}n<0\mathbf{then}\mathbf{error}''index\; must\; be\; \%1\; or\; greater''\&comma;0\mathbf{elif}n\&equals;0\mathbf{then}\mathbf{return}\mathrm{loc}\&lsqb;0\&rsqb;\mathbf{elif}n\&equals;1\mathbf{then}\mathbf{return}\mathrm{loc}\&lsqb;1\&rsqb;\mathbf{end\; if}\&semi;\mathbf{for}\mathrm{i1}\mathbf{to}n-1\mathbf{do}\mathrm{loc}\&lsqb;\mathrm{i1}\&plus;1\&rsqb;≔\mathrm{loc}\&lsqb;\mathrm{i1}-1\&rsqb;\&plus;\mathrm{loc}\&lsqb;\mathrm{i1}\&rsqb;\mathbf{end\; do}\&semi;\left[\mathrm{seq}\left(\mathrm{loc}\&lsqb;\mathrm{i1}\&rsqb;\&comma;\mathrm{i1}\&equals;0..n\right)\right]\mathbf{end\; proc}$

$\mathrm{fib2}\left(10\right)$

$\left[1\&comma;1\&comma;2\&comma;3\&comma;5\&comma;8\&comma;13\&comma;21\&comma;34\&comma;55\&comma;89\right]$

fib3:=rectoproc(fiborec,f(i));

$\mathrm{fib3}≔\mathbf{proc}\left(n\right)\mathbf{local}\mathrm{i1}\&comma;\mathrm{loc0}\&comma;\mathrm{loc1}\&comma;\mathrm{loc2}\&comma;\mathrm{tmp2}\&comma;\mathrm{tmp1}\&comma;\mathrm{i2}\&semi;\mathbf{if}n<=44\mathbf{then}\mathrm{loc0}≔1\&semi;\mathrm{loc1}≔1\&semi;\mathbf{if}n<0\mathbf{then}\mathbf{error}''index\; must\; be\; \%1\; or\; greater''\&comma;0\mathbf{elif}n\&equals;0\mathbf{then}\mathbf{return}\mathrm{loc0}\mathbf{elif}n\&equals;1\mathbf{then}\mathbf{return}\mathrm{loc1}\mathbf{end\; if}\&semi;\mathbf{for}\mathrm{i1}\mathbf{to}n-1\mathbf{do}\mathrm{loc2}≔\mathrm{loc0}\&plus;\mathrm{loc1}\&semi;\mathrm{loc0}≔\mathrm{loc1}\&semi;\mathrm{loc1}≔\mathrm{loc2}\mathbf{end\; do}\&semi;\mathrm{loc1}\mathbf{else}\mathrm{tmp2}≔\left[\begin{array}{rr}1& 1\\ 1& 0\end{array}\right]\&semi;\mathrm{tmp1}≔\left[\begin{array}{r}1\\ 1\end{array}\right]\&semi;\mathrm{i2}≔\mathrm{convert}\left(n-1\&comma;\mathrm{base}\&comma;2\right)\&semi;\mathbf{if}\mathrm{i2}\&lsqb;1\&rsqb;\&equals;1\mathbf{then}\mathrm{tmp1}≔\left[\begin{array}{r}2\\ 1\end{array}\right]\mathbf{end\; if}\&semi;\mathbf{for}\mathrm{i1}\mathbf{in}\mathrm{subsop}\left(1\&equals;\left(\right)\&comma;\mathrm{i2}\right)\mathbf{do}\mathrm{tmp2}≔\mathrm{LinearAlgebra}:-\mathrm{MatrixMatrixMultiply}\left(\mathrm{tmp2}\&comma;\mathrm{tmp2}\right)\&semi;\mathbf{if}\mathrm{i1}\&equals;1\mathbf{then}\mathrm{tmp1}≔\mathrm{LinearAlgebra}:-\mathrm{MatrixVectorMultiply}\left(\mathrm{tmp2}\&comma;\mathrm{tmp1}\right)\mathbf{end\; if}\mathbf{end\; do}\&semi;\mathrm{tmp1}\&lsqb;1\&rsqb;\mathbf{end\; if}\mathbf{end\; proc}$

$\mathrm{fib3}\left(100\right)$

$573147844013817084101$

$\mathrm{fib3}\left(1000\right)$

$70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501$

$\mathrm{rec\_u}≔\left\{u\left(n+2\right)\left(n^2+n+1\right)+u\left(n+1\right)\left(n-2\right)+u\left(n\right)n\&comma;u\left(0\right)=1\&comma;u\left(1\right)=2\right\}$

$\mathrm{rec\_u}≔\left\{u\left(n+2\right)\left(n^2+n+1\right)+u\left(n+1\right)\left(-2+n\right)+u\left(n\right)n\&comma;u\left(0\right)=1\&comma;u\left(1\right)=2\right\}$

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

$\mathrm{u\_n}≔\mathbf{proc}\left(n\right)\mathbf{option}\mathrm{remember}\&semi;\left(2\&ast;\mathrm{procname}\left(\&minus;2\&plus;n\right)\&plus;4\&ast;\mathrm{procname}\left(n-1\right)-\left(\mathrm{procname}\left(\&minus;2\&plus;n\right)\&plus;\mathrm{procname}\left(n-1\right)\right)\&ast;n\right)\&sol;\left(3\&plus;\left(\&minus;3\&plus;n\right)\&ast;n\right)\mathbf{end\; proc}$

$\mathrm{rec\_v}≔v\left(n+3\right)\left(n+4\right)+v\left(n+1\right)\left(n^2+2n\right)=u\left(n+1\right)-nu\left(n\right)$

$\mathrm{rec\_v}≔v\left(n+3\right)\left(n+4\right)+v\left(n+1\right)\left(n^2+2n\right)=u\left(n+1\right)-u\left(n\right)n$

$\mathrm{ini\_v}≔\left\{v\left(0\right)=1\&comma;v\left(1\right)=2\&comma;v\left(2\right)=3\right\}$

$\mathrm{ini\_v}≔\left\{v\left(0\right)=1\&comma;v\left(1\right)=2\&comma;v\left(2\right)=3\right\}$

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

$\mathrm{v\_n}≔\mathbf{proc}\left(n\right)\mathbf{local}\mathrm{i1}\&comma;\mathrm{loc}\&semi;\mathrm{loc}\&lsqb;0\&rsqb;≔1\&semi;\mathrm{loc}\&lsqb;1\&rsqb;≔2\&semi;\mathrm{loc}\&lsqb;2\&rsqb;≔3\&semi;\mathbf{if}n<0\mathbf{then}\mathbf{error}''index\; must\; be\; \%1\; or\; greater''\&comma;0\mathbf{elif}n\&equals;0\mathbf{then}\mathbf{return}\mathrm{loc}\&lsqb;0\&rsqb;\mathbf{elif}n\&equals;1\mathbf{then}\mathbf{return}\mathrm{loc}\&lsqb;1\&rsqb;\mathbf{elif}n\&equals;2\mathbf{then}\mathbf{return}\mathrm{loc}\&lsqb;2\&rsqb;\mathbf{end\; if}\&semi;\mathbf{for}\mathrm{i1}\mathbf{from}2\mathbf{to}n-1\mathbf{do}\mathrm{loc}\&lsqb;\mathrm{i1}\&plus;1\&rsqb;≔\left(\mathrm{u\_n}\left(\mathrm{i1}-1\right)-\mathrm{u\_n}\left(\mathrm{i1}-2\right)\&ast;\left(\mathrm{i1}-2\right)-\left(3\&plus;\left(\&minus;3\&plus;\mathrm{i1}\right)\&ast;\left(\mathrm{i1}\&plus;1\right)\right)\&ast;\mathrm{loc}\&lsqb;\mathrm{i1}-1\&rsqb;\right)\&sol;\left(\mathrm{i1}\&plus;2\right)\mathbf{end\; do}\&semi;\left[\mathrm{seq}\left(\mathrm{loc}\&lsqb;\mathrm{i1}\&rsqb;\&comma;\mathrm{i1}\&equals;0..n\right)\right]\mathbf{end\; proc}$

$\mathrm{v\_n}\left(9\right)$

$\left[1\&comma;2\&comma;3\&comma;\frac{1}{2}\&comma;-\frac{7}{5}\&comma;-\frac{17}{9}\&comma;\frac{125}{49}\&comma;\frac{6803}{1092}\&comma;-\frac{169567}{17199}\&comma;-\frac{423697}{14105}\right]$

$\mathrm{rec}≔\left\{u\left(n+2\right)\left(n+1\right)+u\left(n\right)\left(n^2+1\right)\&comma;u\left(0\right)=\sin \left(1\right)\&comma;u\left(1\right)=\cos \left(1\right)\right\}$

$\mathrm{rec}≔\left\{u\left(n+2\right)\left(n+1\right)+u\left(n\right)\left(n^2+1\right)\&comma;u\left(0\right)=\sin \left(1\right)\&comma;u\left(1\right)=\cos \left(1\right)\right\}$

p:=subsop(4=NULL,rectoproc(rec,u(n)));

$p≔\mathbf{proc}\left(n\right)\mathbf{local}\mathrm{i1}\&comma;\mathrm{loc0}\&comma;\mathrm{loc1}\&comma;\mathrm{loc2}\&semi;\mathrm{loc0}≔\sin \left(1\right)\&semi;\mathrm{loc1}≔\cos \left(1\right)\&semi;\mathbf{if}n<0\mathbf{then}\mathbf{error}''index\; must\; be\; \%1\; or\; greater''\&comma;0\mathbf{elif}n\&equals;0\mathbf{then}\mathbf{return}\mathrm{loc0}\mathbf{elif}n\&equals;1\mathbf{then}\mathbf{return}\mathrm{loc1}\mathbf{end\; if}\&semi;\mathbf{for}\mathrm{i1}\mathbf{to}n-1\mathbf{do}\mathrm{loc2}≔\&minus;\left(5\&plus;\left(\&minus;3\&plus;\mathrm{i1}\right)\&ast;\left(\mathrm{i1}\&plus;1\right)\right)\&ast;\mathrm{loc0}\&sol;\mathrm{i1}\&semi;\mathrm{loc0}≔\mathrm{loc1}\&semi;\mathrm{loc1}≔\mathrm{loc2}\mathbf{end\; do}\&semi;\mathrm{loc1}\mathbf{end\; proc}$

$\mathrm{evalhf}\left(p\left(100\right)\right)$

$5.27739153869639746\times {10}^{76}$

p2:=rectoproc(rec,u(n),evalfun='evalf');

$\mathrm{p2}≔\mathbf{proc}\left(n\right)\mathbf{local}\mathrm{i1}\&comma;\mathrm{loc0}\&comma;\mathrm{loc1}\&comma;\mathrm{loc2}\&semi;\mathrm{loc0}≔\mathrm{evalf}\left(\sin \left(1\right)\right)\&semi;\mathrm{loc1}≔\mathrm{evalf}\left(\cos \left(1\right)\right)\&semi;\mathbf{if}n<0\mathbf{then}\mathbf{error}''index\; must\; be\; \%1\; or\; greater''\&comma;0\mathbf{elif}n\&equals;0\mathbf{then}\mathbf{return}\mathrm{loc0}\mathbf{elif}n\&equals;1\mathbf{then}\mathbf{return}\mathrm{loc1}\mathbf{end\; if}\&semi;\mathbf{for}\mathrm{i1}\mathbf{to}n-1\mathbf{do}\mathrm{loc2}≔\mathrm{evalf}\left(\&minus;\left(5\&plus;\left(\&minus;3\&plus;\mathrm{i1}\right)\&ast;\left(\mathrm{i1}\&plus;1\right)\right)\&ast;\mathrm{loc0}\&sol;\mathrm{i1}\right)\&semi;\mathrm{loc0}≔\mathrm{loc1}\&semi;\mathrm{loc1}≔\mathrm{loc2}\mathbf{end\; do}\&semi;\mathrm{loc1}\mathbf{end\; proc}$

$\mathrm{Digits}≔30\&colon;$$\mathrm{p2}\left(100\right)$

$5.27739153869639769206242956896\times {10}^{76}$

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

$\mathrm{p3}≔\mathbf{proc}\left(n\&comma;\mathrm{b1}\right)\mathbf{local}\mathrm{i1}\&comma;\mathrm{loc0}\&comma;\mathrm{loc1}\&comma;\mathrm{loc2}\&semi;\mathrm{loc0}≔\mathrm{evalf}\left(\sin \left(1\right)\&comma;\mathrm{b1}\right)\&semi;\mathrm{loc1}≔\mathrm{evalf}\left(\cos \left(1\right)\&comma;\mathrm{b1}\right)\&semi;\mathbf{if}n<0\mathbf{then}\mathbf{error}''index\; must\; be\; \%1\; or\; greater''\&comma;0\mathbf{elif}n\&equals;0\mathbf{then}\mathbf{return}\mathrm{loc0}\mathbf{elif}n\&equals;1\mathbf{then}\mathbf{return}\mathrm{loc1}\mathbf{end\; if}\&semi;\mathbf{for}\mathrm{i1}\mathbf{to}n-1\mathbf{do}\mathrm{loc2}≔\mathrm{evalf}\left(\&minus;\left(5\&plus;\left(\&minus;3\&plus;\mathrm{i1}\right)\&ast;\left(\mathrm{i1}\&plus;1\right)\right)\&ast;\mathrm{loc0}\&sol;\mathrm{i1}\&comma;\mathrm{b1}\right)\&semi;\mathrm{loc0}≔\mathrm{loc1}\&semi;\mathrm{loc1}≔\mathrm{loc2}\mathbf{end\; do}\&semi;\mathrm{loc1}\mathbf{end\; proc}$

$\mathrm{p3}\left(100\&comma;40\right)$

$5.277391538696397692062429568990170086821\times {10}^{76}$

$\mathrm{rec}≔\left\{u\left(n\right)n+u\left(n+2\right)\&comma;u\left(0\right)=A\&comma;u\left(1\right)=B\right\}\&colon;$

rectoproc(rec,u(n),params=[p],extralocal=[A='f'(p),B='g'(A,p)]);

$\mathbf{proc}\left(n\&comma;\mathrm{b1}\right)\mathbf{local}\mathrm{i1}\&comma;\mathrm{loc0}\&comma;\mathrm{loc1}\&comma;\mathrm{loc2}\&comma;\mathrm{xloc1}\&comma;\mathrm{xloc2}\&semi;\mathrm{xloc1}≔f\left(\mathrm{b1}\right)\&semi;\mathrm{xloc2}≔g\left(\mathrm{xloc1}\&comma;\mathrm{b1}\right)\&semi;\mathrm{loc0}≔\mathrm{xloc1}\&semi;\mathrm{loc1}≔\mathrm{xloc2}\&semi;\mathbf{if}n<0\mathbf{then}\mathbf{error}''index\; must\; be\; \%1\; or\; greater''\&comma;0\mathbf{elif}n\&equals;0\mathbf{then}\mathbf{return}\mathrm{loc0}\mathbf{elif}n\&equals;1\mathbf{then}\mathbf{return}\mathrm{loc1}\mathbf{end\; if}\&semi;\mathbf{for}\mathrm{i1}\mathbf{to}n-1\mathbf{do}\mathrm{loc2}≔\&minus;\left(\mathrm{i1}-1\right)\&ast;\mathrm{loc0}\&semi;\mathrm{loc0}≔\mathrm{loc1}\&semi;\mathrm{loc1}≔\mathrm{loc2}\mathbf{end\; do}\&semi;\mathrm{loc1}\mathbf{end\; proc}$