convert Recursion to linear can it be done ?

[umen]

Hello all
i have legacy code that preform Recursion calling this Recursion is very heavy and long and sometimes it gives me stack overflow exceptions
i wander in general or algorithmic view can i convert Recursion flow to linear ( not Recursion) ?
Thanks

[Zachm]

You can ALWAYS convert a recursive algorithm to a "non-recursive" one using a Stack to simulate the recursive calls. Each Stack element is a struct / class which will hold all the recursive call parameters data for one recursive call, this way you can handle the recursion yourself and without using the call stack, since your stack will allocate memory from the heap.

Regards,
Zachm

[umen]

Thanks for the reply
could you please point me to some code example
Thanks

[TheCPUWizard]

Thanks for the reply
could you please point me to some code example
Thanks


int Sum(int x)
{
if (x > 1)
return x + Sum(x-1);
else
return 1;
}


int Sum(int x)
{
int z = 0;
for (int i=1; i<=x; ++i)
z+=i;
return z;
}

int Sum(int x)
{
std::stack<int> parts;
for (int i=1; i<=x; ++i)
{
parts.push(i);
}
int z = 0;
while (!parts.empty())
{
z += parts.pop();
}
return z;
}





[/code]