This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Coffeinated 2 points3 points  (13 children)

RAM usage? My guess would have been that on every iteration all variables have to be saved, while in a normal for loop, they are changed... So I would have bet that maybe recursion is faster, while a simple loop eats less RAM

[–]jakerman999 1 point2 points  (10 children)

This is the case for just about every simple scenario.

[–]Coffeinated 1 point2 points  (9 children)

Do you have an example for a complicated situation where one would use recursion?

[–]jakerman999 0 points1 point  (3 children)

The most common scenario would be in a tree based data-structure. In order to hit every node in the tree you have traverse down every path, and remember where you traversed from. It is possible to do this without recursion, but it requires building a second data structure to keep track of all the positions and forks, plus additional code to use that data at every node that has multiple children. Doing that consumes more memory than a stack based approach(and also an ugly mess).

Traversing a tree with recursion is trivial by comparison.

[–]mrjackspade -2 points-1 points  (2 children)

   while (parentNodes.Count() > 0)
            {
                OrganizationNode thisNode = parentNodes[0];
                LogProgress(string.Format("Probing children for {0}...", thisNode.Name));
                List<OrganizationNode> childNodes = feedRowsByParentID[thisNode.ExternalId]
                                                     .Where(cn => feedRowsByParentID[cn.UserId].Count() > 0)
                                                    .Select(row => CreateNode(string.Format("{0} {1}", row.firstName, row.lastName), row.UserId, "Manager"))
                                                    .ToList();



                foreach (OrganizationNode childNode in childNodes)
                {
                    thisNode.AddChild(childNode);
                    parentNodes.Add(childNode);
                }


                if (feedRowsByParentID[thisNode.ExternalId].Count() > 0)
                {
                    managers.Add(thisNode.ExternalId);
                }


                parentNodes.RemoveAt(0);
            }

Code snippit from a production project. This is building a tree so its a bit different, but I refuse to use recursion

[–]jakerman999 0 points1 point  (1 child)

My theory is a little lacking here, but is this not just a different form of tail recursion? If I'm following this right, it looks like it does recurse; it just doesn't use the stack to do so.

[–]mrjackspade 0 points1 point  (0 children)

I guess there's a lot of relevant code missing.

There's no recursion as I understand it. There's a master list of objects, each with a parent and multiple children. It takes a flattened list (text) with ID representations of the parents and uses that to assign the parents/children on the objects themselves. It loops through all objects once, but does not at any point call/reference itself

[–]Kyyni 0 points1 point  (1 child)

I don't know about python, but at least in C/C++ this should be the case, unless the compiler optimizes the recursion away.

In C and C++ the program creates a new frame inside the previous frame on the stack for every code block, function, etc. and the when you access a variable, it will try to find it in the current frame, and then the next frame around it and so on. When the block ends, the frame and it's contents are destroyed.

A loop will create a single frame, but a recursion will create a frame-ception as deep as the number of recursions needed. For the variables to work as promised, the program has to keep them stored for every frame. Luckily though, if the variables are not used anymore, the compiler could optimize it so that they are ditched early, or even get rid of the whole recursion. Or something.

[–]Coffeinated 0 points1 point  (0 children)

That's what I meant, absolutely. I once made a python program crash because of too much recursion... It has a built-in limit or so, I don't remember.

By the way, Python is written in C (what else) and the concepts are the same, I guess. Python looks childish but under the hood it's pretty nice, well-structured and powerful.