Robert M. Corless
Department of Applied Mathematics
University of Western Ontario
London, Canada

Copyright 2001 by Robert M. Corless
All rights reserved

Programming in Maple 

Программирование в Maple

Recursion and 'option remember' 

Рекурсия и "избирательная память" 

> restart;
> A := n -> Matrix(n,n,(i,j)->`if`(abs(i-j)=1,1,`if`(i=j,i,0)));

A := proc (n) options operator, arrow; Matrix(n,n,p...
> A(5);

_rtable[4394896]
> use LinearAlgebra in seq( Determinant(A(n)), n=1..8 ) end use;

1, 1, 2, 7, 33, 191, 1304, 10241
> dt_naive := proc(n)
description "Example recursive program without option remember.";
if n <=2 then
1
else
n*dt_naive(n-1)-dt_naive(n-2)
end if
end proc:
> seq(dt_naive(n),n=1..8);

1, 1, 2, 7, 33, 191, 1304, 10241
> showstat(dt_naive);
dt_naive := proc(n)
1 if n <= 2 then
2 1
else
3 n*dt_naive(n-1)-dt_naive(n-2)
end if
end proc
> stopat(dt_naive,2);

[dt_naive]
> dt_naive(5);
dt_naive:
2* 1
DBG> where;
TopLevel: dt_naive(5)
[5]
dt_naive: n*dt_naive(n-1)-dt_naive(n-2)
[4]
dt_naive: n*dt_naive(n-1)-dt_naive(n-2)
[3]
dt_naive: n*dt_naive(n-1)-dt_naive(n-2)
[2]
dt_naive:
2* 1
DBG> cont
dt_naive:
2* 1
DBG> where
TopLevel: dt_naive(5)
[5]
dt_naive: n*dt_naive(n-1)-dt_naive(n-2)
[4]
dt_naive: n*dt_naive(n-1)-dt_naive(n-2)
[3]
dt_naive: n*dt_naive(n-1)-dt_naive(n-2)
[1]
dt_naive:
2* 1
DBG> cont
dt_naive:
2* 1
DBG> where
TopLevel: dt_naive(5)
[5]
dt_naive: n*dt_naive(n-1)-dt_naive(n-2)
[4]
dt_naive: n*dt_naive(n-1)-dt_naive(n-2)
[2]
dt_naive:
2* 1
DBG> cont
dt_naive:
2* 1
DBG> where
TopLevel: dt_naive(5)
[5]
dt_naive: n*dt_naive(n-1)-dt_naive(n-2)
[3]
dt_naive: n*dt_naive(n-1)-dt_naive(n-2)
[2]
dt_naive:
2* 1
DBG> cont
dt_naive:
2* 1
DBG> where
TopLevel: dt_naive(5)
[5]
dt_naive: n*dt_naive(n-1)-dt_naive(n-2)
[3]
dt_naive: n*dt_naive(n-1)-dt_naive(n-2)
[1]
dt_naive:
2* 1
DBG> cont

33
> dt_ok := proc(n)
option remember;
description "More efficient example recursive program with option remember.";
if n <=2 then
1
else
n*dt_ok(n-1)-dt_ok(n-2)
end if
end proc;




> showstat(dt_ok);
dt_ok := proc(n)
1 if n <= 2 then
2 1
else
3 n*dt_ok(n-1)-dt_ok(n-2)
end if
end proc
> stopat(dt_ok,2);

[dt_naive, dt_ok]
> dt_ok(5);
dt_ok:
2* 1
DBG> where
TopLevel: dt_ok(5)
[5]
dt_ok: n*dt_ok(n-1)-dt_ok(n-2)
[4]
dt_ok: n*dt_ok(n-1)-dt_ok(n-2)
[3]
dt_ok: n*dt_ok(n-1)-dt_ok(n-2)
[2]
dt_ok:
2* 1
DBG> cont
dt_ok:
2* 1
DBG> where
TopLevel: dt_ok(5)
[5]
dt_ok: n*dt_ok(n-1)-dt_ok(n-2)
[4]
dt_ok: n*dt_ok(n-1)-dt_ok(n-2)
[3]
dt_ok: n*dt_ok(n-1)-dt_ok(n-2)
[1]
dt_ok:
2* 1
DBG> cont

33
> seq( dt_ok(n), n=1..8 );

1, 1, 2, 7, 33, 191, 1304, 10241
> unstopat();

[]
> N := 27;

N := 27
> times := array(1..N);

times := array(1 .. 27,[])
> for i to N do st := time(): dt_naive(i); times[i] := time()-st; end do:
> times[N];

9.191
> times[10];

0.
> times[15];

.56e-1
> times[12];

.5e-2
> times[11];

.4e-2
> dataplot := plots[logplot]([seq([i,(times[i])],i=11..N)], style=POINT, symbol=BOX, colour=BLACK, axes=BOXED, labels=["n","cputime"] ): plots[display](dataplot);

> with(stats):
> Xvalues := [seq(i,i=11..N)];

Xvalues := [11, 12, 13, 14, 15, 16, 17, 18, 19, 20,...
> Yvalues := [seq(log(times[i]),i=11..N)];

> fit[leastsquare[[n,logT],logT=a*n+b,{a,b}]]([Xvalues,Yvalues] );

logT = .4759925001*n-10.63946248
> T := unapply( exp( rhs(%) ), n);

T := proc (n) options operator, arrow; exp(.4759925...
> theoryplot := plots[logplot](T,11..N): plots[display]({dataplot,theoryplot});

[Maple Plot]

> T( 100 )/(3.156*10^7);

356693160.6
> 365.25*24*3600;

31557600.00
> time( dt_ok(N) );

0.
> time( dt_ok(100) );

.3e-2
> time( dt_ok(1750) );
Error, (in dt_ok) too many levels of recursion
> kernelopts(stacklimit=1024);
Error, stacklimit cannot be set on this platform
> forget( dt_ok );
> time( dt_ok( 755 ) );

.196
> forget( dt_ok );
> time( dt_ok( 756 ) );
Error, (in dt_ok) too many levels of recursion
> dt_ok(755);

> ilog10(%);

1846
> T(755);

.2842051237e152

 
> %/3.155e7;

.9008086330e144
> log(%)/log(2);

331.4677910*1/ln(2)
> evalf(%);

478.2069383
> 2^30;

1073741824
> evalf(%);

1073741824.
> restart;
> f := proc( t::table )
option remember;
if t[1]=3 then
return "The entry is three.";
else
return "The entry", t[1], " is not three.";
end if;
end proc:
> T := table():
> T[1] := 17;

T[1] := 17
> f( T );

> T[1] := 3;

T[1] := 3
> f( T );

> T[1];

3

С официального разрешения                    © 2002 Waterloo Maple, Inc

 
Hosted by uCoz