Why should recursion be preferable to iteration?

Question

Iteration is more efficient than recursion, right? Then why do some people claim that recursion is better (more elegant, they say) than iteration? I really don’t understand why some languages, such as Haskell, do not allow iteration and encourage recursion? Isn't it absurd to encourage something that has poor performance (and that too, when a more efficient option is available, i.e. recursion)? Please shed some light on this. Thank.

Answer 1

Iteration is more efficient than recursion, right?

Not necessary. This concept comes from many C-like languages, where a function call, recursive or not, had a lot of overhead and created a new stack frame for each call.

For many languages, this is not the case, and recursion is equally or more efficient than the iterative version. These days, even some C compilers rewrite some recursive constructs into an iterative version or reuse the stack frame for a tail recursive call.

Answer 2

Try searching in depth and recursively and tell which one gave you an easier time. Or collect the sort. For many problems, it comes down to supporting your own stack explicitly and leaving your data in the function stack.

I can’t talk to Haskell since I have never used it, but this concerns the more general part of the question posed in your title.

Answer 3

Haskell does not allow iteration because iteration involves mutable state (index).

Answer 4

As others have argued, there is nothing less impressive in recursion. There are several languages ​​where it will be slower, but this is not a universal rule.

Saying, for me, recursion is a tool that will be used when it makes sense. There are some algorithms that are better represented as recursion (as some of them are better through iteration).

Example:

fib 0 = 0 fib 1 = 1 fib n = fib(n-1) + fib(n-2) 

I cannot imagine an iterative solution that could make the goal clearer than that.

Answer 5

Here is some information about the pros and cons of recursion and iteration in c:

http://www.stanford.edu/~blp/writings/clc/recursion-vs-iteration.html

Basically, for me, recursion is sometimes easier to understand than iteration.

Answer 6

A few things:

• Iteration is not necessarily faster
• The root of all evil: encouraging something only because it can be moderately faster, premature; there are other considerations.
• Recursion is often much more concise and clearly conveys your intentions.
• By disabling a mutable state, as a rule, functional programming languages ​​are easier to reason and debug, and recursion is an example of this.
• Recursion takes up more memory than iteration.

Answer 7

An iteration is just a special form of recursion.

Answer 8

I don’t think that in recursion there is something inherently less productive - at least in the abstract. Recursion is a special form of iteration. If a language is designed to support recursion, it may possibly perform as well as iteration.

In the general case, recursion makes explicit the idea of ​​the state that you put forward at the next iteration (these are the parameters). This can facilitate parallelization of execution by language processors. At least, this is a direction that language developers are trying to use.

Answer 9

In Java, recursive solutions usually outperform non-recursive ones. In C, it tends to be the other way around. I think that in general this applies to adapted compiled languages ​​or compared to compiled languages.

Edit: By “general” I mean something like a 60/40 split. It very much depends on how efficiently the language handles method calls. I think JIT compilation promotes recursion because it can choose how to handle inline and use runtime data in optimization. It is very dependent on the algorithm and compiler in question. Java, in particular, continues to absorb recursion processing.

Quantitative research results with Java (PDF link) . Please note that these are mainly sorting algorithms and use the older Java virtual machine (1.5.x, if I'm right). They sometimes get 2: 1 or 4: 1 performance improvements using a recursive implementation, and rarely recursion is much slower. In my personal experience, the difference is not often expressed, but a 50% improvement is common when I use recursion wisely.

Answer 10

Recursion is one of those things that seem elegant or efficient in theory, but in practice are generally less efficient (if the compiler or dynamic recompiler) do not change what the code does. In general, everything that causes unnecessary subroutine calls will be slower, especially when more than one argument is laid out / popped up. All you can do to remove processor cycles, that is, instructions that the processor must chew on, is fair play. Compilers can do pretty good work these days in general, but it's always good to know how to write efficient code manually.

Answer 11

I think this will help to understand what performance is. This link shows how a perfectly intelligently encoded application really has many opportunities for optimization, namely the 43rd! None of this had anything to do with iteration or recursion.

When an application is configured this far, it goes to the point where loops saved by iteration versus recursion can really make a difference.

Answer 12

As a low-level, ITERATION deals with the CX registry for counting loops and, of course, data registers. RECURSION not only deals with the fact that it also adds links to the stack pointer to save links to previous calls, and then how to return .-

My university professor told me that everything you do with recursion can be done with Iterations and viceversa, however it is sometimes easier to do this with recursion than Iteration (more elegant), but iterations are better at performance level .-

Answer 13

Recursion is a typical implementation of iteration. This is just a lower level of abstraction (at least in Python):

 class iterator(object): def __init__(self, max): self.count = 0 self.max = max def __iter__(self): return self # I believe this changes to __next__ in Python 3000 def next(self): if self.count == self.max: raise StopIteration else: self.count += 1 return self.count - 1 # At this level, iteration is the name of the game, but # in the implementation, recursion is clearly what happening. for i in iterator(50): print(i) 

Answer 14

I would compare recursion with explosives: you can achieve great results in the shortest possible time. But if you use it without precaution, the result can be disastrous.

I was very impressed by proving the complexity of the recursion that calculates the Fibonacci numbers here . Recursion in this case has complexity O ((3/2) ^ n), and iteration only O (n). Calculating n = 46 with recursion written in C # takes half a minute! Wow...

IMHO recursion should only be used if the nature of the objects is suitable for recursion (trees, parsing, ...) and never due to aesthetics. The performance and resource consumption of any "divine" recursive code needs to be carefully studied.

Answer 15

It’s hard for me to argue that each is better than the other.

Im is working on a mobile application that should do background work with the user's file system. One of the background threads should sweep the entire file system from time to time in order to maintain updated data to the user. Therefore, fearing, I wrote an iterative algorithm. Today I wrote recursive, for the same work. To my surprise, the iterative algorithm is faster: recursive → 37s, iterative → 34s (works on the same file structure).

Recursive:

 private long recursive(File rootFile, long counter) { long duration = 0; sendScanUpdateSignal(rootFile.getAbsolutePath()); if(rootFile.isDirectory()) { File[] files = getChildren(rootFile, MUSIC_FILE_FILTER); for(int i = 0; i < files.length; i++) { duration += recursive(files[i], counter); } if(duration != 0) { dhm.put(rootFile.getAbsolutePath(), duration); updateDurationInUI(rootFile.getAbsolutePath(), duration); } } else if(!rootFile.isDirectory() && checkExtension(rootFile.getAbsolutePath())) { duration = getDuration(rootFile); dhm.put(rootFile.getAbsolutePath(), getDuration(rootFile)); updateDurationInUI(rootFile.getAbsolutePath(), duration); } return counter + duration; } 

Iterative: - Iterative depth search with recursive reverse tracing

 private void traversal(File file) { int pointer = 0; File[] files; boolean hadMusic = false; long parentTimeCounter = 0; while(file != null) { sendScanUpdateSignal(file.getAbsolutePath()); try { Thread.sleep(Constants.THREADS_SLEEP_CONSTANTS.TRAVERSAL); } catch (InterruptedException e) { e.printStackTrace(); } files = getChildren(file, MUSIC_FILE_FILTER); if(!file.isDirectory() && checkExtension(file.getAbsolutePath())) { hadMusic = true; long duration = getDuration(file); parentTimeCounter = parentTimeCounter + duration; dhm.put(file.getAbsolutePath(), duration); updateDurationInUI(file.getAbsolutePath(), duration); } if(files != null && pointer < files.length) { file = getChildren(file,MUSIC_FILE_FILTER)[pointer]; } else if(files != null && pointer+1 < files.length) { file = files[pointer+1]; pointer++; } else { pointer=0; file = getNextSybling(file, hadMusic, parentTimeCounter); hadMusic = false; parentTimeCounter = 0; } } } private File getNextSybling(File file, boolean hadMusic, long timeCounter) { File result= null; //se o file é /mnt, para if(file.getAbsolutePath().compareTo(userSDBasePointer.getParentFile().getAbsolutePath()) == 0) { return result; } File parent = file.getParentFile(); long parentDuration = 0; if(hadMusic) { if(dhm.containsKey(parent.getAbsolutePath())) { long savedValue = dhm.get(parent.getAbsolutePath()); parentDuration = savedValue + timeCounter; } else { parentDuration = timeCounter; } dhm.put(parent.getAbsolutePath(), parentDuration); updateDurationInUI(parent.getAbsolutePath(), parentDuration); } //procura irmao seguinte File[] syblings = getChildren(parent,MUSIC_FILE_FILTER); for(int i = 0; i < syblings.length; i++) { if(syblings[i].getAbsolutePath().compareTo(file.getAbsolutePath())==0) { if(i+1 < syblings.length) { result = syblings[i+1]; } break; } } //backtracking - adiciona pai, se tiver filhos musica if(result == null) { result = getNextSybling(parent, hadMusic, parentDuration); } return result; } 

Confident that the iterative is not elegant, but despite the fact that it is currently implemented for an indefinite period, it is still faster than recursive. And I have better control over it, because I don’t want it to work at full speed and let the garbage collector do its work more often.

In any case, I will not take for granted that one method is better than another and will consider other algorithms that are currently recursive. But at least from the 2 algorithms above, the iterative will be one of the final product.

Answer 16

Iteration is more efficient than recursion, right?

Yes.

However , when you have a problem that fits perfectly with the recursive data structure, the best solution is always recursive .

If you pretend to solve the iteration problem, you end up inventing a stack and creating messy and ugly code compared to a graceful recursive version of the code.

However, the Iteration will always be faster than Recursion . (in von Neumann architecture), so if you always use recursion, even if the loop is sufficient, you will pay a performance penalty.

Is recursion faster than a loop?

Answer 17

"Iteration is more efficient than recursion" is actually language specific and / or compiler specific. The case that comes to mind is when the compiler does a loop-unwrap. If you implemented a recursive solution in this case, it will be a little slower.

It pays to be a scientist (testing hypotheses) and know your tools ...

Answer 18

on the way ntfs UNC max as 32K
C: \ A \ B \ X \ C .... more than 16K folders can be created ...

But you can’t even count the number of folders with any recursive method, sooner or later everyone will cause a stack overflow.

For scanning folders, only good iterative code with a light weight is professionally used.

Believe it or not, most of the best antiviruses cannot scan the maximum depth of UNC folders.