Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

replacing recursion with stack

stack recursion

  • Please log in to reply
4 replies to this topic

#1 bobabc

bobabc

    CC Newcomer

  • Member
  • PipPip
  • 12 posts

Posted 24 August 2012 - 04:49 AM

Hello i got this recursive method

			    private void StrongConnect(Vertex v)
			    {
					    v.index = index;
					    v.lowlink = index;
					    index++;
					    nodeStatck.Push(v);
					    foreach (Vertex w in v.Dependencies) {
							    if (w.index < 0) {
									    StrongConnect(w);
									    v.lowlink = Math.Min(v.lowlink, w.lowlink);
							    }
							    else if (nodeStatck.Contains(w)) {
									    v.lowlink = Math.Min(v.lowlink, w.index);
							    }
					    }
					    if (v.lowlink == v.index) {
							    List<Vertex> scc = new List<Vertex>();
							    Vertex w;
							    do {
									    w = nodeStatck.Pop();
									    scc.Add(w);
							    } while (v != w);
							    output.Add(scc);
					    }
			    }

but i want to replace recursive call with stack

i did this but it doest nto work

private void StrongConnect(Vertex v)
	    {
		    Stack<Vertex> sss = new Stack<Vertex>();
		    sss.Push(v);
		    while (sss.Count > 0)
		    {
			    v = sss.Pop();
			   
			    v.index = index;
			    v.lowlink = index;
			    index++;
			    nodeStatck.Push(v);
			    foreach (Vertex w in v.Dependencies)
			    {
				    if (w.index < 0)
				    {
					    sss.Push(w);
					    //StrongConnect(w);
					    v.lowlink = Math.Min(v.lowlink, w.lowlink);
				    }
				    else if (nodeStatck.Contains(w))
				    {
					    v.lowlink = Math.Min(v.lowlink, w.index);
				    }
			    }
			    if (v.lowlink == v.index)
			    {
				    List<Vertex> scc = new List<Vertex>();
				    Vertex w;
				    do
				    {
					    w = nodeStatck.Pop();
					    scc.Add(w);
				    } while (v != w);
				    output.Add(scc);
			    }
		    }

what am i doing wrong here?
  • 0

#2 CodeTiger

CodeTiger

    CC Regular

  • Member
  • PipPipPip
  • 25 posts
  • Programming Language:Java, C++, C#, JavaScript, Lua
  • Learning:Objective-C

Posted 25 August 2012 - 02:29 AM

What doesnt work? Do you get an exception or is the result unexpected?
I wonder a little bit why you want replace it?
  • 0

#3 bobabc

bobabc

    CC Newcomer

  • Member
  • PipPip
  • 12 posts

Posted 25 August 2012 - 02:49 AM

because when i put big graph, recursion is too deep and its using memory which does not belong to me then i get exception, but i was told to replace recursion with own stack
  • 0

#4 CodeTiger

CodeTiger

    CC Regular

  • Member
  • PipPipPip
  • 25 posts
  • Programming Language:Java, C++, C#, JavaScript, Lua
  • Learning:Objective-C

Posted 28 August 2012 - 02:51 AM

and what is the problem with the second? I guess a exception, but which one and where?
  • 0

#5 Roy192

Roy192

    CC Lurker

  • New Member
  • Pip
  • 6 posts

Posted 03 September 2012 - 07:45 AM

I can't understand much of your code when I can only see a small fragment of it. I also don't know what you're trying to do (something with vertexes? idk).

But I can see a big difference between the two pieces of code you posted. In the recursion one you do some stuff with the vertex and then you take all its dependancies and process them with the method one by one and after you done that, you change the lowlink value of the vertex. And after you done all dependacies, you check the final value of lowlink.

In the second one using a stack you do the same but with one big difference. You don't process the dependancies untill after you check the lowlink value in the next step of the while loop. They just get added to the stack and only get processed the next time the while loop runs.

If that isn't clear to you, take a look at this picture.
  • 0





Also tagged with one or more of these keywords: stack, recursion

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download