当前位置: 动力学知识库 > 问答 > 编程问答 >

Recursion vs loops

问题描述:

I'm facing a problem where both recursion and using a loop seem like natural solutions. Is there a convention or "preferred method" for cases like this? (Obviously it is not quite as simple as below)

Recursion

Item Search(string desired, Scope scope) {

foreach(Item item in scope.items)

if(item.name == desired)

return item;

return scope.Parent ? Search(desired, scope.Parent) : null;

}

Loop

Item Search(string desired, Scope scope) {

for(Scope cur = scope; cur != null; cur = cur.Parent)

foreach(Item item in cur.items)

if(item.name == desired)

return item;

return null;

}

网友答案:

I favor recursive solutions when:

  • The implementation of the recursion is much simpler than the iterative solution, usually because it exploits a structural aspect of the problem in a way that the iterative approach cannot

  • I can be reasonably assured that the depth of the recursion will not cause a stack overflow, assuming we're talking about a language that implements recursion this way

Condition 1 doesn't seem to be the case here. The iterative solution is about the same level of complexity, so I'd stick with the iterative route.

网友答案:

If performance matters, then benchmark both and choose on a rational basis. If not, then choose based on complexity, with concern for possible stack overflow.

There is a guideline from the classic book The Elements of Programming Style (by Kernighan and Plauger) that algorithm should follow data structure. That is, recursive structures are often processed more clearly with recursive algorithms.

网友答案:

Recursion is used to express an algorithm that is naturally recursive in a form that is more easily understandable. A "naturally recursive" algorithm is one where the answer is built from the answers to smaller sub-problems which are in turn built from the answers to yet smaller sub-problems, etc. For example, computing a factorial.

In a programming language that is not functional, an iterative approach is nearly always faster and more efficient than a recursive approach, so the reason to use recursion is clarity, not speed. If a recursive implementation ends up being less clear than an iterative implementation, then by all means avoid it.

In this particular case, I would judge the iterative implementation to be clearer.

网友答案:

If you are using a functional language (doesn't appear to be so), go with recursion. If not, the loop will probably be better understood by anyone else working on the project. Of course, some tasks (like recursively searching a directory) are better suited to recursion than others.

Also, if the code cannot be optimized for tail end recursion, the loop is safer.

网友答案:

Use the loop. It's easier to read and understand (reading code is always a lot harder than writing it), and is generally a lot faster.

网友答案:

I would say the recursion version is better understandable, but only with comments:

Item Search(string desired, Scope scope) {
    // search local items
    foreach(Item item in scope.items)
        if(item.name == desired)
            return item;

    // also search parent
    return scope.Parent ? Search(desired, scope.Parent) : null;
}

It is far easier to explain this version. Try to write a nice comment on the loop version and you will see.

网友答案:

It is provable that all tail-recursive algorithms can be unrolled into a loop, and vice versa. Generally speaking, a recursive implementation of a recursive algorithm is clearer to follow for the programmer than the loop implementation, and is also easier to debug. Also generally speaking, the real-world performance of the loop implementation will be faster, as a branch/jump in a loop is typically faster to execute than pushing and popping a stack frame.

Personally speaking, for tail-recursive algorithms I prefer sticking with the recursive implementation in all but the most-performance-intensive situations.

网友答案:

I prefer loops as

  • Recursion is error-prone
  • All the code remains into one function / method
  • Memory and speed savings

I use stacks (LIFO schema) to make the loops work

In java, stacks is covered with Deque interface

// Get all the writable folders under one folder
// java-like pseudocode
void searchWritableDirs(Folder rootFolder){
    List<Folder> response = new List<Folder>(); // Results
    Deque<Folder> folderDeque = new Deque<Folder>(); // Stack with elements to inspect
    folderDeque.add(rootFolder);
    while( ! folderDeque.isEmpty()){
        Folder actual = folder.pop(); // Get last element
        if (actual.isWritable()) response.add(actual); // Add to response
        for(Folder actualSubfolder: actual.getSubFolder()) { 
            // Here we iterate subfolders, with this recursion is not needed
            folderDeque.push(actualSubfolder);
        } 
    } 
    log("Folders " + response.size());
 }

Less complicated, more compact than

// Get all the writable folders under one folder
// java-like pseudocode
void searchWritableDirs(Folder rootFolder){
    List<Folder> response = new List<Folder>(); // Results
    rec_searchWritableDirs(actualSubFolder,response);
    log("Folders " + response.size());
}

private void rec_searchWritableDirs(Folder actual,List<Folder> response) {
   if (actual.isWritable()) response.add(actual); // Add to response
   for(Folder actualSubfolder: actual.getSubFolder()) {
       // Here we iterate subfolders, recursion is needed
       rec_searchWritableDirs(actualSubFolder,response);
   }                
}

The latter has less code, but two functions and it's harder to understand code, IMHO.

网友答案:

I find the recursion more natural, but you may be forced to use the loop if your compiler doesn't do tail call optimization and your tree/list is too deep for the stack size.

网友答案:

I usually prefer the use of loops. Most good OOP designs will allow you to use loops without having to use recursion (and thus stopping the program from pushing all those nasty parameters and addresses to the stack).

It has more of a use in procedural code where it seems more logical to think in a recursive manner (due to the fact that you can't easily store state or meta-data (information?) and thus you create more situations that would merit it's use).

Recursion is good for proto-typing a function and/or writing a base, but after you know the code works and you go back to it during the optimization phase, try to replace it with a loop.

Again, this is all opinionated. Go with what works best for you.

网友答案:

If your code is compiled it will likely make little difference. Do some testing and see how much memory is used and how fast it runs.

网友答案:

If the system you're working on has a small stack (embedded systems), the recursion depth would be limited, so choosing the loop-based algorithm would be desired.

网友答案:

You can also write the loop in a more readable format. C's for(init;while;increment) have some readability drawbacks since the increment command is mentioned at the start but executed at the end of the loop.

Also YOUR TWO SAMPLES ARE NOT EQUIVALENT. The recursive sample will fail and the loop will not, if you call it as: Search(null,null). This makes the loop version better for me.

Here are the samples modified (and assuming null is false)

Recursion (fixed and tail-call optimizable)

Item Search(string desired, Scope scope) {

    if (!scope) return null

    foreach(Item item in scope.items)
        if(item.name == desired)
            return item;

    //search parent (recursive)
    return Search(desired, scope.Parent);
}

Loop

Item Search(string desired, Scope scope) {
    // start
    Scope cur = scope;

    while(cur) {
        foreach(Item item in cur.items)
            if(item.name == desired)
                return item;

        //search parent
        cur = cur.Parent;

    } //loop

    return null;
}
网友答案:

Avoid recursion. Chances are that piece of code will have to be maintained eventually at some point and it'll be easier if it is not done with recursion. Second, it'll most likely have a slower execution time.

分享给朋友:
您可能感兴趣的文章:
随机阅读: