we******@yahoo.com (Victor) wrote in message news:<4c**************************@posting.google. com>...

Hello,

I've got a situation in which the number of (valid) recursive calls I

make will cause stack overflow. [...]

My question, then is whether there isn't a more straightforward way to

accomplish this goal. [...]

First, see if you can find another algorithm for your function that

does not depend on the per invocation state. If you can do this, then

you have removed the memory consumption problem of your recursive

function.

If it is not possible to remove that requirement, the next best

alternative is to re-write your function to remove the recursive

calls and manage the per invocation state explicitly. This will

give you precise control over the memory used by your function.

As an example, consider the following textbook illustration of a bad

recursive implementation of a function to find the n-th Fibonacci

number:

unsigned fib(unsigned n)

{

if (n < 2) return n;

return fib(n-1) + fib(n-2);

}

This function can be rewritten as (remember that we are staying

true to the per invocation state of the original recursive

implementation):

#define N 1024

#define fibpush(x) (fibstack[fibcount++] = x)

#define fibpop() (fibstack[--fibcount])

#define fibtop() (fibstack[fibcount-1])

unsigned fib(unsigned n)

{

enum state { BEG, FIB, SUM, END, FIN } state = BEG;

enum point { INIT, FIB1, FIB2, FINI };

struct fibstate { enum point point; unsigned value; } s, t;

struct fibstate fibstack[N];

unsigned fibcount = 0;

t.point = INIT;

t.value = n;

fibpush(t);

while (state != FIN)

switch(state) {

case BEG: if (fibtop().value < 2) {

state = END; break;

}

t.point = FIB1;

t.value = fibtop().value - 1;

fibpush(t);

state = BEG; break;

case FIB: t = fibpop();

s = fibtop();

s.point = FIB2;

s.value = fibtop().value - 2;

t.point = FINI;

fibpush(t);

fibpush(s);

state = BEG; break;

case SUM: t = fibpop();

s = fibpop();

fibtop().value = s.value + t.value;

state = END; break;

case END: switch (fibtop().point) {

case INIT: state = FIN; break;

case FIB1: state = FIB; break;

case FIB2: state = SUM; break;

case FINI: break;

}

case FIN: break;

}

t = fibpop();

return t.value;

}

In practice, you would check for stack overflow and underflow

in the push and pop operations.

This is just an example. There are, of course, far better ways

to write a function that finds the n-th Fibonacci number

recursively. One improved implementation is:

static unsigned fib_r(unsigned a, unsigned b, unsigned n)

{

if (n < 2) return b;

return fib_r(b, a+b, n-1);

}

unsigned fib(unsigned n)

{

if (n < 2) return n;

return fib_r(0, 1, n);

}

When translated into the equivalent non-recursive version, the

above implementation becomes:

static unsigned fib_r(unsigned a, unsigned b, unsigned n)

{

for (;;) {

if (n < 2) return b;

#ifdef TRICKY

b = a+b;

a = b-a;

#else

{

int t = a;

a = b;

b += t;

}

#endif

--n;

}

}

unsigned fib(unsigned n)

{

if (n < 2) return n;

return fib_r(0, 1, n);

}

-- James