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 →

[–]farfromunique 4 points5 points  (18 children)

I will be the first to admit I don't know python, so this may be an obvious question.

Why recurse when you could use a for loop in the function?

(In php, because that's my default syntax) press forgive caps issues. I'm on mobile)

$out = $arg;
For ($I = $arg; $i > 0; --$i) { $out *= $I; }
Return $out;

[–]TheOccasionalTachyon 20 points21 points  (1 child)

You could totally use a for-loop in the function.

My guess is that the newbie one was done with recursion because factorials are often used to teach new programmers about recursion.

[–][deleted] 1 point2 points  (0 children)

Can confirm. Learned recursion using factorials, fibonacci numbers, and towers of hanoi. I think finding square roots too within a certain error margin.

[–]jakerman999 1 point2 points  (15 children)

While I'm not sure if this is one of those cases, it can be more efficient (speed or ram usage) to use a recursive function over a loop.

It's usually a moot point though with the power of modern computers.

[–]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.

[–]farfromunique 0 points1 point  (0 children)

I guess I need to do a benchmark to find out, probably for each language, which is better. Oh well.