Recursion vs loop

Question

I'm using a recursive function in my c# asp.net program and it throws "StackOverflow Exception". This exception is thrown when I run my program in IIS.

If I use a loop instead of the recursive function will it throw "StackOverflow Exception"?

Which is good to use a loop or recursion in case of this exception?

Edit:

After analyzing the problem, I found the exception is caused because the level of recursion is more than 1000 and it causes the stack to overflow.

Now, I'm completely lost in converting my recursive function to an iteration because multiple recursion is used. I'm posting a sample code here for reference:

RecursiveFunction(Node n)    {
   //Some Code for local variables
node.processed=true;
if(n.up){
   //Create a sub node for node below the current one
  if(!subnode.processed)
   RecursiveFunction(subnode);
}
else{
   //Create a sub node for node above current one
 if(!subnode.processed)
   RecursiveFunction(subnode);
}
return result;
}

Note: The above sample code may be an infinite loop because I just used it to mention multiple recursions are used, its actual implementation is not an infinite loop.

In this case, the base condition is, if a node is processed already it will not use recursion and returns the result directly.

My question is, if multiple recursions are used, how can I replace it with an iteration. I googled and found many suggestions for replacing a recursion with iteration or stock. But I don't find anything about replacing a multiple recursion with iteration.

Sorry, I can't post the code, my doubt is even if I convert my recursive function to a loop, will it solve the problem (StackOverflow Exception)? — Anandaraj
– Anandaraj, Commented Oct 22, 2013 at 12:36
If you convert a recursive function that throws a StackOverflow-exception into an imperative loop, chances are good that it will end in an endless loop, running for ever. — sloth
– sloth, Commented Oct 22, 2013 at 12:41
My recursive function is not endless, just the stack size is limited. In visual studio dev server it works fine. It causes exception only in IIS. So, I think the loop will not be infinite. Thank you all for your quick reply. — Anandaraj
– Anandaraj, Commented Oct 22, 2013 at 12:49

FarmerBob · Accepted Answer · 2013-11-14 09:10:02Z

2

You can convert any recursive function into non-recursive by managing your own stack. Something like this:

void NonRecursiveFunction(Node n)    {
   var stack = new Stack<Node>();
   stack.Push(n);

   while(stack.Any()) {
        node = stack.Pop();
        //Some Code for local variables
        node.processed=true;
        if(n.up){
            //Create a sub node for node below the current one
            if(!subnode.processed)
                stack.Push(subnode);
        } else{
            //Create a sub node for node above current one
            if(!subnode.processed)
                stack.Push(subnode);
        }
    }
    return result;
}

answered Nov 14, 2013 at 9:10

FarmerBob

1,3649 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Anandaraj Over a year ago

Thanks for your quick reply. I'll try your suggestion.

weston · Accepted Answer · 2013-10-22 12:42:41Z

Ok, so you just want to know if it will solve it:

Yes, you will not get a StackOverflowException if you switch to a loop.

When you call a method, it gets pushed on to the call stack. Calling the same method from within itself builds up a larger and larger stack. Eventually this can pop with a StackOverflowException when the program uses up all the available memory on the stack.

In a loop, you are not pushing more and more to the stack so you don't get this problem. However it can be less straight forward to implement, otherwise we'd never use recursion.

As someone else has mentioned, it is possible there is nothing wrong with using recursion in this case, it's just you aren't stopping the recursion at anypoint. In which case a loop version of the same will carry on forever (but you won't get the StackOverflow!)

Collectives™ on Stack Overflow

Recursion vs loop

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related