You can try to write your recursion in a different way. Besides what I'm
explaining further can be found in any book about functional languages
or compiling optimizations. Usually it is show in second year of
computer science cycle.
There are two kinds of recursions:
-iterative recursion.
This is when the function can be expressed as
f(x){
if t(x) then
f(x)=f(g(x))
else
f(x)=h(x);
}
This can be rewritten as
f(x){
while(t(x))
x=g(x);
return h(x)
}
Written as this, the function is constant in space modulo g and h. but
no more stack consumption. In fact the recursion is just a syntactical
rewriting of a loop. This makes is it a very simple compiling technique
for optimization but most C compilers fail on it.
-deep recursion
This is when the function can be expressed as
if t(x) then
f(x)=i(f(g(x)),j(x));
else
f(x)=h(x);
Here we cannot avoid a stack mechanisme. But you can locate the stack in
heap.
So get a lib for stacks:
Type -> stack
Function -> Stack *s newStack(), void* pop(Stack *s),
void push(Stack *s,void*), bool isEmpty(Stack
*s)
void clearStack(Stack *s)
Then you can write your function as followed:
f(x){
Stack* s
s=newStack();
While(t(x)){
Push(s,j(x));
x=g(x);
}
res=h(x);
while(!isEmpty(s)){
res=i(pop(s),res);
}
return res;
}
Deep recursion is the real recursion, you cannot syntactically rewrite
it in a iterative version(without a stack mechanisme). You can only
easily move the problem from the execution stack to the heap. But it
does not save space. If you exhaust the heap... Get a device with more
memory or look for a better algorithm.
Steve Van der Hoeven
Freelance developer
-----Original Message-----
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of
Richard Coutts
Sent: Sunday, August 17, 2003 4:11 PM
To: Palm Developer Forum
Subject: Questions on Stack Overflow strategies
I'm using some recursive calls that are filling up my stack. There's no
easy way around the recursion, so I'm finding other ways to be frugal
with
stack usage. I've been reading up on the stack issues and have a couple
of
questions:
(1) I read somewhere that even if I keep below the stack size that I
allot
myself, that Palm Hacks can occupy some of the stack, and that my app
consequently may not have as much as it thinks it does. E.g., if my app
is
compiled for a 4K stack, but there are Hacks that occupy 512 Bytes, that
I'm
really working with a 3.5K stack (is this true? I'm not very savvy
about
how Hacks work). If this is the case, how do you work with this? Do
you
allocate the stack to be a little bigger than it needs to be to allow of
Hacks to take some of it?
(2) When the stack overflows, I get the initial message from POSE
listing
the last 6 or so functions on the stack with the amount of stack they're
using in parenthasis. But, there's usu. a dozen or so function calls
above
that that are the real culprits -- is "#pragma warn_stack_usage 1" the
only
way to get a function's stack size, or is there a way to see the amount
of
stack all of the functions were using at the time POSE crashed?
Thanks,
Rich
--
For information on using the Palm Developer Forums, or to unsubscribe,
please see http://www.palmos.com/dev/support/forums/
--
For information on using the Palm Developer Forums, or to unsubscribe, please see
http://www.palmos.com/dev/support/forums/
