What are the advantages of recursion compared to iteration? [duplicate]

I’m trying to understand when is preferred to use recursion rather than iteration.

Actually I’ve encountered recursion only in Javascript but never in Python. I imagine that recursion should be used in determinate contexts or languages but I don’t understand when I should use it and which advantages it gives me.

I would like to see some examples of advantageous usage of recursion, as opposed to iteration.

An example of iteration being more useful than recursion: in a paper by Dijkstra (the relevant part is the first two out of the last three paragraphs), a graph theory problem is discussed. Somebody had found a recursive solution and published it; and it seemed very impressive and hard to understand. Dijkstra had been messing around with a mini-language that didn’t have recursion, tried to solve the problem, and found that there was a simple solution involving 4 separate stacks that grew and shrank independently.

An example of recursion being more useful than iteration: maze solving. You can solve a maze recursively by proceeding recursively in each of the directions left/forward/right at each step. While you could do it iteratively using a stack, that would be uglier, whereas the recursive solution is perfectly clear.

In general, use recursion when it solves the problem more clearly than any obvious alternative.

Many (but not all) languages use a stack to keep track of function calls, so recursion can use up all the space and crash the program — depending on how many levels deep the recursion goes. If you use that kind of language, you can make sure that the recursion can never go too deep, or enlarge the stack to be large enough (if the language allows), or use an alternative to recursion.

In functional languages, recursion is often the default, and things that might be expressed as a for loop in other languages are done with recursion instead. There ways of extracting the basic iteration patterns into other constructions that don’t look like either recursion or for loops, such as list comprehensions or the higher-order functions map and reduce (aka fold). Python has list comprehensions, map, and reduce; Javascript has array comprehensions, map, and reduce.

Before deciding, lets look at the similarities and differences.

Iteration is suited to problems where there are a fixed number of partial results. An example is to sum the elements of an array; we only need one partial result – the sum calculated so far.

Implementation: In iteration we have a loop. Think of it as having 4 parts:

A decision to continue or stop, based on some “controlling” data, evaluated as a logical condition.
A body, where the work is done. Sometimes, the body is combined with the next part.
A way of changing the “controlling” data. Often by changing a counter.
A way of invoking the construct (in this case, the loop) again. In c-style languages this is provided by the for, while, or do syntax.

Recursion is suited to problems where we don’t know how many partial results there will be. An example is where we are summing the elements of a binary tree (that does not have links to the parent nodes) – we need to keep the sum calculated so far and be able to ascend the tree. Ascending the tree (going to the node’s parent) is naturally done in a recursive solution; we just return to the previous call. The call stack is keeping our partial results for us.

Implementation: In recursion we have a function (sometimes several). They have the same 4 parts:

A decision to continue or stop, based on some “controlling” data, evaluated as a logical condition. The controlling data is usually passed to the function as parameter(s).
A body, where the work is done. Sometimes, the body is combined with the next part.
A way of changing the “controlling” data. Sometimes by changing a counter, often by changing which node of a data structure is “current”.
A way of invoking the construct (in this case, the function) again – that means call the function (and remember to pass the changed “controlling” data).

So, they are very similar. One feature of recursion has been omitted though: a function can return a value. This means a partial result can be returned to the caller. This is a key part of many recursive solutions.

Reasons for choosing

Language style and support. If you are working in a functional programming language (such as a Lisp dialect, Haskell, Erlang, Scala, etc), recursion is the natural way to go. If your language does not support recursion well, you can be forced to produce an iterative solution. In some problems, this can involve building and managing your own stack of partial results.
Problem or solution structure. Some problems or solutions naturally fit into a in iterative or recursive implementation. The array summing example is a natural fit for an iterative solution. But problems where our solution is like “find a part of the problem I can solve, solve it, and do the same thing again” are a natural fit for a recursive solution.
Performance or space constraints. Recursive solutions can consume more space and processor time than iterative solutions. Compilers, optimizers, and smart programming can help, but there are still cases where we must coerce a naturally recursive solution to be iterative. Until we know we have a problem, we are better following the natural, easy to read solution.

I often use recursion when I can’t achieve immutability via iteration. There is something to be said about trying to avoid immutability all the time- it’s not always the correct approach, but sometimes it can be.

Let’s take a trivial example that doesn’t show the efficacy of recursion to erase mutability: assume that I want to program Conway’s Game of Life, and I have two functions display and evolve (I’m programming this in kotlin for anyone wondering).

fun evolve(generation: Generation): Generation {
    // Create and return the next generation.
}

fun display(generation: Generation) {
    // Display the current generation.
}

Fair enough, and in my main I create a starting generation:

fun main(args: Array<String>) {
    val generationZero = Generation("xxx",
                                    "ooo",
                                    "xxx")
}

where x and o represent dead and live cells respectively.

Now I want to continuously update and display current and future generations:

 fun main(args: Array<String>) {
     val generationZero = Generation("xxx",
                                     "ooo",
                                     "xxx")

     var generationX = generationZero
     while (true) {
         display(generationX)
         generationX = evolve(generationX)
     }
 }

This is okay, and in such a trivial example probably not a problem. But for practice’s sake I would really like to have no mutability in my code. I refactor my code snippet into this:

fun runTheGameOfLife(generationX: Generation) {
    display(generationX)

    runTheGameOfLife(evolve(generationX))
}

Without a terminating condition this will eventually crash and burn, so you might want to look into that. Otherwise, voilá! You now have sweet, testable code with no mutability.

Please note that I’m not advocating eradicating all mutability- that is silliness of the highest degree, but recursion can simplify and eradicate mutability where it isn’t necessary nor safe. It is up to you to determine which places in your code deserve to be mutable.

Recursion is in many cases much simpler and much more easier to understand than iteration. Often you can solve problem that normally would take ~50 lines of code in just 10 lines by using recursion. Of corse every problem that can be solved with recursion can also be solved with iteration and you can get some better performance by that, but in many cases it’s much more ugly approach(if you want to rewrite recursive solution). Check Hanoi tower algorithm to check how beautiful can recursive approach be. 🙂

The practice. Whether you choose recursion or iteration should depend on the nature of the problem you are trying to solve.

Iteration and recursion are two techniques for dealing with collections of objects. Which one you use depends the nature of the collection. Iteration suits flat collections such as arrays and hash maps; recursion suits nested collections like tree data structures. Note that a collection can be physical, such as tree data structure, or it can be virtual, such as the set of all 4×4 magic squares.

To put it another way, if solving a problem can be done by solving a set of sub-problems of the same kind, then recursion is recommended. If the problem can be solved directly, without breaking it down into nested sub-problems, then iteration is called for.

Sometimes a problem can be solved either way. Here, your choice will depend on professional judgement: How complex is each solution? How difficult (and thus, how defect-prone) is it to code? How efficient is the algorithm? Which of these factors matter more? Say you want to write code to sort the elements of an array. Here are two choices for algorithms:

Linear insertion sort is a simple iterative solution: an outer loop walks through the array visiting each element to be put in
place; an inner loop slides that element to the correct place in the
(growing) sorted section of the list.
Quicksort works recursively: it re-arranges the elements of the list to partition them into two sub-lists, the first with all the
elements smaller than a “pivot” value and the second with all
elements larger than the pivot (this is a linear process); then it
calls itself once on each of the two sub-lists to sort them in place.

The linear insertion sort is simple to program and to validate, but has terrible performance for large arrays. Quicksort requires more care to program, but performs well on large arrays.

The theory. Recursion is a more general, and more conceptually powerful, technique than iteration. The theory behind recursion is a little deeper, which means that it takes more effort to “prove” that a recursive algorithm is correct, versus an iterative one. But because of that generality, there are problems that have straight-forward recursive solutions but have no simple iterative solutions.

Think of iteration as a utility knife and recursion as a sword. The sword is more versatile but requires more skill and effort to wield. If you have a Gordian-knot of a problem to solve, the sword is the only thing that will do. But for most problems that you are likely to encounter, the utility knife will get the job done, and get it done faster and easier.

The reality. In many years of working in the so-called real world (i.e., not in academia), I have seen two or three instances of code that recurses, whereas I have probably seen half a gazillion instances of code that iterates.

Filed under: softwareengineering - @ 07:40

Thẻ: performance, programming-practices, recursion

Thiết kế website giá rẻ

Danh mục

What are the advantages of recursion compared to iteration? [duplicate]