Why should recursion be preferred over iteration?

Question

Iteration is more performant than recursion, right? Then why do some people opine that recursion is better (more elegant, in their words) than iteration? I really don't see why some languages like Haskell do not allow iteration and encourage recursion? Isn't that absurd to encourage something that has bad performance (and that too when more performant option i.e. recursion is available) ? Please shed some light on this. Thanks.

Answer 1

Iteration is just a special form of recursion.

Answer 2

In Java, recursive solutions generally outperform non-recursive ones. In C it tends to be the other way around. I think this holds in general for adaptively compiled languages vs. ahead-of-time compiled languages.

Edit: By "generally" I mean something like a 60/40 split. It is very dependent on how efficiently the language handles method calls. I think JIT compilation favors recursion because it can choose how to handle inlining and use runtime data in optimization. It's very dependent on the algorithm and compiler in question though. Java in particular continues to get smarter about handling recursion.

Quantitative study results with Java (PDF link). Note that these are mostly sorting algorithms, and are using an older Java Virtual Machine (1.5.x if I read right). They sometimes get a 2:1 or 4:1 performance improvement by using the recursive implementation, and rarely is recursion significantly slower. In my personal experience, the difference isn't often that pronounced, but a 50% improvement is common when I use recursion sensibly.

Answer 3

I find it hard to reason that one is better than the other all the time.

Im working on a mobile app that needs to do background work on user file system. One of the background threads needs to sweep the whole file system from time to time, to maintain updated data to the user. So in fear of Stack Overflow , i had written an iterative algorithm. Today i wrote a recursive one, for the same job. To my surprise, the iterative algorithm is faster: recursive -> 37s, iterative -> 34s (working over the exact 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-first search , with recursive backtracking

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;
        }

Sure the iterative isn't elegant, but alhtough its currently implemented on an ineficient way, it is still faster than the recursive one. And i have better control over it, as i dont want it running at full speed, and will let the garbage collector do its work more frequently.

Anyway, i wont take for granted that one method is better than the other, and will review other algorithms that are currently recursive. But at least from the 2 algorithms above, the iterative one will be the one in the final product.

Answer 4

Recursion is the typical implementation of iteration. It's 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's happening.
for i in iterator(50):
    print(i)

Answer 5

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

But you can not even count the number of folders with any recursive method, sooner or later all will give stack overflow.

Only a Good lightweight iterative code should be used to scan folders professionally.

Believe or not, most top antivirus cannot scan maximum depth of UNC folders.

Answer 6

As others have stated, there's nothing intrinsically less performant about recursion. There are some languages where it will be slower, but it's not a universal rule.

That being said, to me recursion is a tool, to be used when it makes sense. There are some algorithms that are better represented as recursion (just as some are better via iteration).

Case in point:

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

I can't imagine an iterative solution that could possibly make the intent clearer than that.