stack overflow with recursive definitions (crash)

Am 26 Nov 2005 um 15:56 hat Gilles Schintgen geschrieben:

> Hi,
> 
> Just for fun, I tried doing some numeric experiments with a recursively 
> defined sequence:
> (%i1) u[0]: bfloat(1)$
> (%i2) u[n]:= bfloat((3*u[n-1]+1)^(1/3)-1)$
> Unfortunately I'm always getting stack overflow errors when trying large 
> values of n:
> (%i3) u[10];
> (%o3)                        1.038217430642616B-1
> (%i4) u[200];
> 
> Maxima encountered a Lisp error:
> 
>  Error in PROGN [or a callee]: Bind stack overflow.
> 

Hi, 
the best would be to write an iterative or at least tail recursive version of your expression, 
which isn't really a function but a hash table (? ).

I would write it as a proper function and compile it. This helps a bit, but cannot prevent 
from stack overflow. The function is not tail recursiv. Info: Tail recursiv functions are 
replaced by iterativ function while compiling.

(%i13) u(n):= if n=0 then bfloat(1) else bfloat((3*u(n-1)+1)^(1/3)-1)$
(%i14) u(10);
(%o14) 			     1.038217430642616B-1
(%i15) u(200);
Maxima encountered a Lisp error:

 Error in CATCH [or a callee]: Bind stack overflow.

Automatically continuing.
To reenable the Lisp debugger set *debugger-hook* to nil.
(%i16) compile(u);
Compiling gazonk0.lsp.
End of Pass 1.  
End of Pass 2.  
OPTIMIZE levels: Safety=2, Space=2, Speed=2
Finished compiling gazonk0.lsp.
(%o16) 				      [u]
(%i17) u(200);
(%o17) 			     5.059738684726922B-3
(%i20) u(2000);
(%o20) 			     5.009774061200956B-4

Hope this helps
Volker van Nek