This procedure returns a Maple procedure that, given a non-negative integer n as input, gives the nth term of the linear recurrence.

If the argument 'remember' or 'remember'=true is specified, then the procedure will compute the sequence via a recursive procedure using option remember. By default, 'remember'=false and the sequence is computed iteratively.

The argument 'remember' should be given when one needs a large number of values of the sequence.

When 'remember'=false and the coefficients of the recurrence are nonconstant polynomials, the returned procedure will run in a straight loop, using a linear number of arithmetic operations and without wasting extra space.

When 'remember'=false and the coefficients are constant, the procedure will employ a binary-based optimization strategy (for large index values only), and runs with a logarithmic number of arithmetic operations. This optimization can be disabled by specifying constantoptimize=false.

When 'remember'=false, by default the initial terms of the recurrence are embedded in the code. This can be changed to put the initial terms of the recurrence in the remember table by specifying initialremember=true.

When the first terms of the recurrence are not explicitly supplied, they are represented symbolically.

The command with(LREtools,REtoproc) allows the use of the abbreviated form of this command.

$\mathrm{with}\left(\mathrm{LREtools}\right)\:$$\mathrm{interface}\left(\mathrm{verboseproc}=3\right)\:$

fib := REtoproc(f(i)=f(i-1)+f(i-2),f(i),{f(0)=0,f(1)=1});

$\mathrm{fib}≔\mathbf{proc}\left(n::\mathrm{nonnegint}\&comma;\$\right)\mathbf{local}i\&comma;\mathrm{u0}\&comma;\mathrm{u1}\&comma;\mathrm{u2}\&comma;a\&comma;\mathrm{res}\&comma;l\&semi;\mathrm{u0}≔0\&semi;\mathrm{u1}≔1\&semi;\mathbf{if}n\&equals;0\mathbf{then}\mathrm{u0}\mathbf{elif}n\&equals;1\mathbf{then}\mathrm{u1}\mathbf{elif}n<=44\mathbf{then}\mathbf{for}i\mathbf{from}2\mathbf{to}n-1\mathbf{do}\mathrm{u2}≔\mathrm{u0}\&plus;\mathrm{u1}\&semi;\mathrm{u0}≔\mathrm{u1}\&semi;\mathrm{u1}≔\mathrm{u2}\mathbf{end\; do}\&semi;\mathrm{u0}\&plus;\mathrm{u1}\mathbf{else}a≔\mathrm{array}\left(1..2\&comma;1..2\&comma;\left[\left[1\&comma;1\right]\&comma;\left[1\&comma;0\right]\right]\right)\&semi;\mathrm{res}≔\mathrm{array}\left(1..2\&comma;\left[\mathrm{u1}\&comma;\mathrm{u0}\right]\right)\&semi;l≔\mathrm{convert}\left(n-1\&comma;\&apos;\mathrm{base}\&apos;\&comma;2\right)\&semi;\mathbf{if}l\&lsqb;1\&rsqb;\&equals;1\mathbf{then}\mathrm{res}≔\mathrm{array}\left(1..2\&comma;\left[1\&equals;a\&lsqb;1\&comma;1\&rsqb;\&ast;\mathrm{res}\&lsqb;1\&rsqb;\&plus;a\&lsqb;1\&comma;2\&rsqb;\&ast;\mathrm{res}\&lsqb;2\&rsqb;\&comma;2\&equals;a\&lsqb;2\&comma;1\&rsqb;\&ast;\mathrm{res}\&lsqb;1\&rsqb;\&plus;a\&lsqb;2\&comma;2\&rsqb;\&ast;\mathrm{res}\&lsqb;2\&rsqb;\right]\right)\mathbf{end\; if}\&semi;\mathbf{if}l\&equals;\left[1\right]\mathbf{then}\mathrm{res}\&lsqb;1\&rsqb;\mathbf{else}\mathbf{for}i\mathbf{in}l\&lsqb;2..\&minus;2\&rsqb;\mathbf{do}a≔\mathrm{array}\left(1..2\&comma;1..2\&comma;\left[\left(2\&comma;2\right)\&equals;a\&lsqb;1\&comma;2\&rsqb;\&ast;a\&lsqb;2\&comma;1\&rsqb;\&plus;a\&lsqb;2\&comma;2\&rsqb;\&Hat;2\&comma;\left(1\&comma;2\right)\&equals;a\&lsqb;1\&comma;1\&rsqb;\&ast;a\&lsqb;1\&comma;2\&rsqb;\&plus;a\&lsqb;1\&comma;2\&rsqb;\&ast;a\&lsqb;2\&comma;2\&rsqb;\&comma;\left(2\&comma;1\right)\&equals;a\&lsqb;1\&comma;1\&rsqb;\&ast;a\&lsqb;2\&comma;1\&rsqb;\&plus;a\&lsqb;2\&comma;1\&rsqb;\&ast;a\&lsqb;2\&comma;2\&rsqb;\&comma;\left(1\&comma;1\right)\&equals;a\&lsqb;1\&comma;1\&rsqb;\&Hat;2\&plus;a\&lsqb;1\&comma;2\&rsqb;\&ast;a\&lsqb;2\&comma;1\&rsqb;\right]\right)\&semi;\mathbf{if}i\&equals;1\mathbf{then}\mathrm{res}≔\mathrm{array}\left(1..2\&comma;\left[1\&equals;a\&lsqb;1\&comma;1\&rsqb;\&ast;\mathrm{res}\&lsqb;1\&rsqb;\&plus;a\&lsqb;1\&comma;2\&rsqb;\&ast;\mathrm{res}\&lsqb;2\&rsqb;\&comma;2\&equals;a\&lsqb;2\&comma;1\&rsqb;\&ast;\mathrm{res}\&lsqb;1\&rsqb;\&plus;a\&lsqb;2\&comma;2\&rsqb;\&ast;\mathrm{res}\&lsqb;2\&rsqb;\right]\right)\mathbf{end\; if}\mathbf{end\; do}\&semi;\left(a\&lsqb;1\&comma;1\&rsqb;\&Hat;2\&plus;a\&lsqb;1\&comma;2\&rsqb;\&ast;a\&lsqb;2\&comma;1\&rsqb;\right)\&ast;\mathrm{res}\&lsqb;1\&rsqb;\&plus;\left(a\&lsqb;1\&comma;1\&rsqb;\&ast;a\&lsqb;1\&comma;2\&rsqb;\&plus;a\&lsqb;1\&comma;2\&rsqb;\&ast;a\&lsqb;2\&comma;2\&rsqb;\right)\&ast;\mathrm{res}\&lsqb;2\&rsqb;\mathbf{end\; if}\mathbf{end\; if}\mathbf{end\; proc}$

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

$354224848179261915075$

fib2 := REtoproc(f(i)=f(i-1)+f(i-2),f(i),{f(0)=0,f(1)=1},'remember');

$\mathrm{fib2}≔\mathbf{proc}\left(n::\mathrm{nonnegint}\&comma;\$\right)\mathbf{option}\mathrm{remember}\&semi;\mathrm{procname}\left(n-2\right)\&plus;\mathrm{procname}\left(n-1\right)\mathbf{end\; proc}$

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

$354224848179261915075$

rec := REtoproc(f(i)=i^2*f(i-1)+f(i-2),f(i),{},'remember');

$\mathrm{rec}≔\mathbf{proc}\left(n::\mathrm{nonnegint}\&comma;\$\right)\mathbf{option}\mathrm{remember}\&semi;n\&Hat;2\&ast;\mathrm{procname}\left(n-1\right)\&plus;\mathrm{procname}\left(n-2\right)\mathbf{end\; proc}$

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

$9058477158744039108901484875567483833514619274297483550856232216805415823966784458605109749449017462079827918537250156488348819998559536412999537100386489240766568099262887636990141071242906533135806432242520067765428965147272705161620549611736618446171403767978982293333281882312513474668524116583587067499136325876f\left(1\right)+2203823124569416698291075403023306063089022127683403942005208386556556750073849332403233124551522569729148712230224505771905205727903820151912839068030542989769962446264480000034834468134656141631555555405058769399965103438352643881658179110007643158335872008434125847040069584050780045011709372240155319761920733361f\left(0\right)$