Add your own alternative version
Stats
172.2K views 1.9K downloads 179 bookmarked
Posted
11 Jul 2012

Comments and Discussions


i attempted this long time ago, having come back to algorithm design and seeing such a nice solution is really tickling. that idea of using stages is amazing, last i tried this i got hang up on poping and pushing and handling local variables. some people may see this as basic, but doing it right in generic manner like this is really awe inspiring. you are the man!. 10 stars.





Hi,
Thanks for you great artical on converting recursive to stack based iterative loops.
When I am looking into the example code, I am not sure why the initial params of FibNum2() is 5,4, rather than 0,1. FibNum2(10)and FibNum2(10,5,4) are not equal.





Yup, you are right in order to make FibNum2 to be equal to FibNum, the parameters should be "10,0,1."
I was only testing the random numbers to test the recursive and loop difference.
Idea was not to make FibNum2 result to be equal to FibNum, but explain the tail recursion and how it is different with loop version.
Sorry if I made you any confusion.
Wish this helps.





You might want to explain why recursive routines to sort are unlikely to cause a stack overflow because of the nature of the routine. IE, you induced a stack overflow with recursion passing 10,000 to a routine, but sorting a million items would basically concurrently call about 20 routines while making about 200K calls overall. The concurrence calls would be 30 to sort a billion items.
Hmmm, then you should explain the sort process in order to explain how a sort routine works that way and why the number of concurrent calls affects the probability of a stack overflow.
Maybe you were right to not explain why "Sort" is a good recursive candidate.





Well done! You have simplified and explained this technique in a well written procedure that is easy to follow. Thank you!





Very nice explanation. This is the sort of thing taught very theoretically in a computer science class. It is nice to see a practical explanation.





Really nice explanation man... the codes u uploaded help me understand both the styles... Thanks a Million.





I enjoyed so much! thank you





Hi, I've been wondering if the iterative version of a recursive function (using whileloop and stack) is equally efficiently in terms of time and memory?
By the way, very good article...





I don't think it's equally efficient as recursive function in terms of either time or memory.
Recursive function would be optimized more efficiently by compiler, and the memory used to stack each recursive call would be much efficiently handled in recursive function. (Don't bet on me though.)
This article is only about simple way of evading the stackoverflow error during recursive calls by simulating the recursive function with stack (allocated within the heap memory).
So if the time and memory are critical issue, then I would recommend to find the right way to make the recursive function to loop function instead of this simple recursive simulation.
(In most of my situation, the performance and memory were not the issue, but the failure of program due to error was the most critical.)





Thanks, indeed, I agree with you, just wanted a second opinion.
Actually, in my case, seems not to be much difference with respect to the recursive function, in terms of time and memory used; but since stack overflows only for some particular cases, I might use the recursive version in the remaining cases and the iterative only for trouble ones... to make it as efficient as possible.





It should be moreso on both accounts, in large part because you only store what you need in the stack, not the whole program state.
Additionally, efficiency doesn't matter if the program crashes due to a stack overflow.





Great article!
I suggest add an example with recursive call inside a loop. Sometimes the loop condition can be complicated (depending on an object, for example), and maybe it is necessary use some tricks to simulate the second loop (stage 1).
For example, a typical quicksort implementation that uses tail recursion (to limit recursive stack depth) is:
void quicksort(int v[], int left, int right)
{
int p;
while (left < right)
{
p = partition(v, left, right);
if (p  left < right  p)
{
quicksort(v, left, p  1);
left = p + 1;
}
else
{
quicksort(v, p + 1, right);
right = p  1;
}
}
}
It's easy to convert quicksort without tail recursion (and limiting stack pushing larger block first), but with tail recursion it is not trivial.
Thanks






Nice article, but I'm missing some words about the loss of performance that your solution brings.
As you use the stack (heap) class as a stack replacement, you now have a lot dynamic allocations on the heap. This brings a performance penalty. Also each SnapShotStruct has to be copied to the stack.
I don't share your belief that each recursion should be avoided in all cases. Performance is one reason why, readability and maintainability are some others why recursion sometimes is better.
You should examine each case separately and look for other solutions better tailored for the (recursive) problem/algorithm instead of blindly opting for a generic solution.





Duh.





may be i find an error in step 10. look this snippets as below:
retVal = test;
I guess the right code is:
retVal = currentSnapshot.test





Yes, that is a typo. Sorry about the misleading material.
I will fix ASAP.
Thanks for letting me know.





5! Once I wanted to write something like this but I have always been lazy to formulate a nice rulesystem for this "mechanized" conversion and also to write the article...






My recursive function call itself within a for loop located inside it. Then, how to convert that kind of recursive function to a loop? I tried your method. But, I can't understand how to convert that for loop part





If the recursive function call is within the for loop, then generally you can make
for stage0:
Operations before the recursive function call
push to the current Snapshot to the stack with changing the stage as 1 and the forloop condition (ex. forloop index)
push new Snapshot for recursive function call with stage0
for stage1:
Operations after the recursive function call return
start forloop as stage0 with the index saved from stage0.
push to the current Snapshot to the stack with changing the stage as 1 and the forloop condition (ex. forloop index) if forloop is not expired.
push new Snapshot for recursive function call with stage0.
Important thing is you split the stages as before the recursive function call and after the recursive function call.
But things can become complex when recursive function call happens within forloop depends on tailrecursion, linear recursion, binary recursion etc.





Hello,
I am doing high level synthesis for my aquisition algorithm. On that I have Split Radix Fast Fourier algorithm. In that they used recursive function. But my Vivado HLS platofrom is not supporting recursive functions. Can you please help me how to convert it to loop.
here is my code
void srrec(double *xr, double *xi, int logm)
{
static int m, m2, m4, m8, nel, n;
static double *xr1, *xr2, *xi1, *xi2;
static double *cn, *spcn, *smcn, *c3n, *spc3n, *smc3n;
static double tmp1, tmp2, ang, c, s;
static double *tab[MAXLOGM];
/* Check range of logm */
if ((logm < 0)  (logm > MAXLOGM)) {
printf("Error : SRFFT : logm = %d is out of bounds [%d, %d]\n",
logm, 0, MAXLOGM);
//error_exit();
}
/* Compute trivial cases */
if (logm < 3) {
if (logm == 2) { /* length m = 4 */
xr2 = xr + 2;
xi2 = xi + 2;
tmp1 = *xr + *xr2;
*xr2 = *xr  *xr2;
*xr = tmp1;
tmp1 = *xi + *xi2;
*xi2 = *xi  *xi2;
*xi = tmp1;
xr1 = xr + 1;
xi1 = xi + 1;
xr2++;
xi2++;
tmp1 = *xr1 + *xr2;
*xr2 = *xr1  *xr2;
*xr1 = tmp1;
tmp1 = *xi1 + *xi2;
*xi2 = *xi1  *xi2;
*xi1 = tmp1;
xr2 = xr + 1;
xi2 = xi + 1;
tmp1 = *xr + *xr2;
*xr2 = *xr  *xr2;
*xr = tmp1;
tmp1 = *xi + *xi2;
*xi2 = *xi  *xi2;
*xi = tmp1;
xr1 = xr + 2;
xi1 = xi + 2;
xr2 = xr + 3;
xi2 = xi + 3;
tmp1 = *xr1 + *xi2;
tmp2 = *xi1 + *xr2;
*xi1 = *xi1  *xr2;
*xr2 = *xr1  *xi2;
*xr1 = tmp1;
*xi2 = tmp2;
return;
}
else if (logm == 1) { /* length m = 2 */
xr2 = xr + 1;
xi2 = xi + 1;
tmp1 = *xr + *xr2;
*xr2 = *xr  *xr2;
*xr = tmp1;
tmp1 = *xi + *xi2;
*xi2 = *xi  *xi2;
*xi = tmp1;
return;
}
else if (logm == 0) return; /* length m = 1 */
}
/* Compute a few constants */
m = 1 << logm; m2 = m / 2; m4 = m2 / 2; m8 = m4 /2;
/* Build tables of butterfly coefficients, if necessary */
if ((logm >= 4) && (tab[logm4] == NULL)) {
/* Allocate memory for tables */
nel = m4  2;
if ((tab[logm4] = (double *) calloc(6 * nel, sizeof(double))) == NULL) {
// error_exit();
}
/* Initialize pointers */
cn = tab[logm4]; spcn = cn + nel; smcn = spcn + nel;
c3n = smcn + nel; spc3n = c3n + nel; smc3n = spc3n + nel;
/* Compute tables */
for (n = 1; n < m4; n++) {
if (n == m8) continue;
ang = n * TWOPI / m;
c = cos(ang); s = sin(ang);
*cn++ = c; *spcn++ =  (s + c); *smcn++ = s  c;
ang = 3 * n * TWOPI / m;
c = cos(ang); s = sin(ang);
*c3n++ = c; *spc3n++ =  (s + c); *smc3n++ = s  c;
}
}
/* Step 1 */
xr1 = xr; xr2 = xr1 + m2;
xi1 = xi; xi2 = xi1 + m2;
for (n = 0; n < m2; n++) {
tmp1 = *xr1 + *xr2;
*xr2 = *xr1  *xr2;
*xr1 = tmp1;
tmp2 = *xi1 + *xi2;
*xi2 = *xi1  *xi2;
*xi1 = tmp2;
xr1++; xr2++; xi1++; xi2++;
}
/* Step 2 */
xr1 = xr + m2; xr2 = xr1 + m4;
xi1 = xi + m2; xi2 = xi1 + m4;
for (n = 0; n < m4; n++) {
tmp1 = *xr1 + *xi2;
tmp2 = *xi1 + *xr2;
*xi1 = *xi1  *xr2;
*xr2 = *xr1  *xi2;
*xr1 = tmp1;
*xi2 = tmp2;
xr1++; xr2++; xi1++; xi2++;
}
/* Steps 3 & 4 */
xr1 = xr + m2; xr2 = xr1 + m4;
xi1 = xi + m2; xi2 = xi1 + m4;
if (logm >= 4) {
nel = m4  2;
cn = tab[logm4]; spcn = cn + nel; smcn = spcn + nel;
c3n = smcn + nel; spc3n = c3n + nel; smc3n = spc3n + nel;
}
xr1++; xr2++; xi1++; xi2++;
for (n = 1; n < m4; n++) {
if (n == m8) {
tmp1 = SQHALF * (*xr1 + *xi1);
*xi1 = SQHALF * (*xi1  *xr1);
*xr1 = tmp1;
tmp2 = SQHALF * (*xi2  *xr2);
*xi2 = SQHALF * (*xr2 + *xi2);
*xr2 = tmp2;
} else {
tmp2 = *cn++ * (*xr1 + *xi1);
tmp1 = *spcn++ * *xr1 + tmp2;
*xr1 = *smcn++ * *xi1 + tmp2;
*xi1 = tmp1;
tmp2 = *c3n++ * (*xr2 + *xi2);
tmp1 = *spc3n++ * *xr2 + tmp2;
*xr2 = *smc3n++ * *xi2 + tmp2;
*xi2 = tmp1;
}
xr1++; xr2++; xi1++; xi2++;
}
/* Call ssrec again with half DFT length */
srrec(xr, xi, logm1);
/* Call ssrec again twice with one quarter DFT length.
Constants have to be recomputed, because they are static! */
m = 1 << logm; m2 = m / 2;
srrec(xr + m2, xi + m2, logm2);
m = 1 << logm; m4 = 3 * (m / 4);
srrec(xr + m4, xi + m4, logm2);
}





If you have read the article carefully, your algorithm can be replaced with loop version very easily.
However I believe this is not a place where you ask people around to do your homework.
If you really need help, show what you tried and what is not working out, then I will be happy to help you.
p.s. I've converted your recursive version with loop version within 10 minutes.
If you show that you really tried and if it is not really working out, then I would like to help you with the solution.





Very usefull, clear and precise. A brillant article.








Very well, thank you for sharing, could be useful






This is a great inspiring article. I am pretty much pleased with your good work. You put really very helpful information. Keep it up once again.






Good article for an interesting solution.












Eliminating recursion on a recursive *implementation* is a typical refactoring[^] task.
Quote: Before refactoring a section of code, a solid set of automatic unit tests is needed.
No adequate tests > don't refactor. So, your first and most important rule should be: define automated unit tests that check the refactored code.
BTW: I fully agree with Matt's comment[^] that your rule set basically replace the implicit stack implementation by an explicit hand crafted stack implementation. In that case, I prefer the implicit one over the hand crafted one since the risk of adding errornous code is smaller.
My advise would rather be:
1) try to convert the recursion into direct recursion
2) then into tail recursion
3) and finally convert the tail recursion into a loop
Employing a handcrafted stack is not the general solution (it may need some stack some times but not to replace all call parameters and local variables, but rather to have some nested state of a particular item that is calculated).
So, overall, since it is rather misleading advise, a 3 only from my side.
Cheers
Andi





Very good point that you made. As I said in introduction, it is to help novice developers to avoid the stack overflow when they use the recursive functions. Of course, the professional developer should do as you proposed or the way, which fits the situation, but it requires time and experiences to do everything properly. And as I also said that I agree with Matt's comment, it is just moving the stack from call stack to heap stack, which is just simulating the recursive function, but I thought it might be helpful to some novice developer when they first faced the stackoverflow before they get to know the proper way to handle all the situation.
p.s. Of course the unit test is really important, but just it was not the point of article here, so I just avoid mentioning.
After all, thank you for your feedback.





It appears that a lot of this is just moving the recursion information from the call stack to a "heap" stack . The recursion isn't really "unrolled" (at least in some cases.)
For example (from the source code TailRecursion.h):
int FibNum2(int n, int x, int y)
{
if (1 == n)
{
return y;
}
else
{
return FibNum2(n1, y, x+y);
}
}
is rewritten to:
int FibNum2Loop(int n, int x, int y)
{
struct SnapShotStruct
{
int inputN;
int inputX;
int inputY;
};
int returnVal;
stack<SnapShotStruct> snapshotStack;
SnapShotStruct currentSnapshot;
currentSnapshot.inputN = n;
currentSnapshot.inputX = x;
currentSnapshot.inputY = y;
snapshotStack.push(currentSnapshot);
while(!snapshotStack.empty())
{
currentSnapshot=snapshotStack.top();
snapshotStack.pop();
if(currentSnapshot.inputN == 1)
{
returnVal = currentSnapshot.inputY;
continue;
}
else
{
SnapShotStruct newSnapshot;
newSnapshot.inputN= currentSnapshot.inputN 1 ;
newSnapshot.inputX= currentSnapshot.inputY;
newSnapshot.inputY= currentSnapshot.inputX + currentSnapshot.inputY;
snapshotStack.push(newSnapshot);
continue;
}
}
return returnVal;
}
This is still using a stack!
Tail recursion is the simplest recursion to eliminate.
It can (almost?) always be reduced to a simple loop.
(Good compiler/optimizers will detect this case and deal with it "automagically".)
The above can be simplified to:
int FibNum2SimpleLoop(int n, int x, int y)
{
while (1 != n)
{
int next_y = x + y;
n;
x = y;
y = next_y;
}
return y;
}
The "mechanical" process you present adds a great deal of complexity and seems to just shift the recursive state storage from one place to another.
Converting recursion to iteration well requires much more thinking about the problem than your process.
Sorry, the best I can do is Vote of 3.





Thank you for the feedback, and you really have good point.
I should have been more careful with the wording.
Yes it is actually simulating the recursive function using whileloop and heap stack by moving stack to heap stack.
Have updated the article so it won't mislead other readers anymore.





well written, but trivial topic. If this were rated a beginner article i'd change my vote to 5.





Thanks for the feedback, and also moved the article as you proposed!





Changed to 5. Thanks again!





WPFanatic  Why don't you just say how clever YOU are. This person has taken the trouble to submit an article and all you can say is it is too simple for you because you are so damn clever. Supercilious, sanctimonious people like you wreck forums like this because they put off people submitting articles because of gratuitous criticisms from selfappointed experts. If you are too clever  don't read Code Project at all.





Hm, maybe you overread that my only point is the article being on "intermediate" level  recursion is one of the basic concepts, and converting recursive algorithms to iterative ones, especially using the method explained in this artice (i.e. converting from stackrecursion to a kind of iterative heaprecursion) is really quite basic.
It is nicely explained though, that's why i changed my initial vote to 5 a few days ago.





I think there is a section at the start missing which spells out in black and white what is the difference between an interative function and a recursive function, and possibly another section on what the benefits of each are, and also possibly a typical scenario where you would use one over the other.






General News Suggestion Question Bug Answer Joke Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

 Best C++ article of July 2012
