When will iteration be more readable than recursion?

Question

Preface

I had read a lot on why to prefer recursion over iteration, but I still have not seen any question that explain when to prefer iteration over recursion.

Motivation

Certainly, I believe there is no best tools to solve everything.

For example, both spoon and fork are eating tools, but spoon is more suited for eating rice while fork is more suitable for eating noodles.

Obviously, I will be a fanatic if I say that fork(or spoon) is the best tool for eating.

So, it is the same as recursion or iteration, both of them are tools, they each have their own benefits and disadvantages.

However, after searching through Googles and StackOverflow, although I found a lot of example on why recursion is more readable than iteration, but I still had not found any example on when iteration is more readble than recursion.

Thus, I seek to find out situations where iteration will be more readble. Just like how the ancient human realize fork is better than spoon at handling noodles.

Expected answer

Therefore, I hope to get answers that meet the following requirement:

1. Explain a situation on when will iteration be more readable than recursion
2. Give an example of algorithm (such as Bubblesort etc.) in pseudocode to demonstrate that iteration is more readable than recursion in such case

Note

• Please note that I don't care about performance, what I care is the code readability.
• Therefore, you can use any imperative language, but not Haskell (or its derivatives) as they don't support loops.

Reference

• Why should recursion be preferred over iteration?
• https://www.quora.com/Computer-Science-Why-is-recursion-more-elegant-than-iteration
• https://softwareengineering.stackexchange.com/questions/182314/recursion-or-while-loops

Answer 1

To avoid an opinon-based answer I'd like to expand on the meaning of recursion:

When talking about recursion, it is important to distinguish between functions that are recursively defined, and functions that generate a recursive process.

Of the two aspects the latter is by far more important (assuming that you are writing a program to solve an actual problem). Given the choice between an iterative process and a recursive one, the former is the better, regardless of readability or elegance, as the difference in efficiency is enormous.

As an example, consider computing fibonacci numbers, and let's do it in Haskell, to show that this is not about loops vs function calls:

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

This generates a recursive process, for instance fib(4)

                   fib(4)
                    |
          ----------+----------
         fib(3)              fib(2)  
           |                   |
      -----+----          -----+---- 
    fib(2)    fib(1)   fib(1)     fib(0)
       |          |      |          |
       |          1      1          0
  -----+----  
fib(1)   fib(0)
 |        |
 1        0

Compare this to an iterative process (generated by a recursively defined function):

fibIter :: Int -> Int
fibIter n = iter 1 0 n
    where
    iter :: Int -> Int -> Int -> Int
    iter _ b 0 = b
    iter a b m = iter (a+b) a (m-1)

Where the process generated by fib(4) is

fibIter 4
iter 1 0 4
iter 1 1 3
iter 2 1 2
iter 3 2 1
iter 5 3 0
3

Note that the recursive process generates an exponential number of function invocations, where the iterative process does a linear number of function invocations (and only needs constant space if tail calls are eliminated).

In other cases, and in languages that do tail call elimination and have loop constructs, I'd say that the choice between writing a loop or using recursion is a matter of taste or programming conventions (making this opinion based).

Update about the readability of the bubblesort implementations:

It can be argued that the recursive formulation is more clear as it directly expresses the algorithm as

1. Bubble up the largest element and put this last in the result
2. Sort the rest of the elements with bubblesort

which -- again, arguably -- requires less mental housekeeping than the iterative formulation with loops and local variables.

For clarity, I would probably write the recursive bubblesort something like

bubbleSort :: Ord a =>  [a] -> [a]
bubbleSort [] = []
bubbleSort l = bubbleSort rest ++ [largest]
    where tmp = bubbleUpLargest l
          largest = last tmp
          rest = init tmp
          bubbleUpLargest (x:y:xs)
            | x > y = y:bubbleUpLargest (x:xs)
            | otherwise = x:bubbleUpLargest (y:xs)
          bubbleUpLargest x = x

Answer 2

Iteration-based code is - in most cases - less memory-intensive. Perhaps the best answer to this question lies in how recursion works.

When the program redirects to the "start" of a function using recursion, the C++ language does not re-use the existing instance of the function. Instead, a new instance of the function is created and the program counter is moved to the start of the new instance. The address of the old instance is placed on the Stack Buffer awaiting the return of the new instance.

However, when using iteration, the program counter is moved to the start of the existing instance of the code. No stack necessary.

This is the reason that iteration is strongly favored in many low-level programming applications that use C/C++. When programming Micro-controllers, you would almost never want to use recursion, because the stack buffer would only be able to hold a very small number of function addresses.

However, there are some occasions where recursion just makes sense. In the field of Signal Processing, the mathematics often breaks down into formulas that require recursion, and you cannot always find a closed-form version of the equation. In cases such as this, when running on a computer with sufficient memory, recursion can be the best option.

Furthermore, recursion is extremely useful in navigating File Trees. Consider the following code Code Example. Notice specifically the simplicity of his void DFS(struct node *head) function.

The truth is, with sufficient memory, recursion can be very useful. So it's not really a competition between recursion and iteration, but rather understanding the limitations that each method has.