Recursion or Iteration?

Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!

It is possible that recursion will be more expensive, depending on if the recursive function is tail recursive (the last line is recursive call). Tail recursion should be recognized by the compiler and optimized to its iterative counterpart (while maintaining the concise, clear implementation you have in your code).

I would write the algorithm in the way that makes the most sense and is the clearest for the poor sucker (be it yourself or someone else) that has to maintain the code in a few months or years. If you run into performance issues, then profile your code, and then and only then look into optimizing by moving over to an iterative implementation. You may want to look into memoization and dynamic programming.

Recursion is more costly in memory, as each recursive call generally requires a memory address to be pushed to the stack - so that later the program could return to that point.

Still, there are many cases in which recursion is a lot more natural and readable than loops - like when working with trees. In these cases I would recommend sticking to recursion.

Typically, one would expect the performance penalty to lie in the other direction. Recursive calls can lead to the construction of extra stack frames; the penalty for this varies. Also, in some languages like Python (more correctly, in some implementations of some languages...), you can run into stack limits rather easily for tasks you might specify recursively, such as finding the maximum value in a tree data structure. In these cases, you really want to stick with loops.

Writing good recursive functions can reduce the performance penalty somewhat, assuming you have a compiler that optimizes tail recursions, etc. (Also double check to make sure that the function really is tail recursive---it's one of those things that many people make mistakes on.)

Apart from "edge" cases (high performance computing, very large recursion depth, etc.), it's preferable to adopt the approach that most clearly expresses your intent, is well-designed, and is maintainable. Optimize only after identifying a need.

Your performance deteriorates when using recursion because calling a method, in any language, implies a lot of preparation: the calling code posts a return address, call parameters, some other context information such as processor registers might be saved somewhere, and at return time the called method posts a return value which is then retrieved by the caller, and any context information that was previously saved will be restored. the performance diff between an iterative and a recursive approach lies in the time these operations take.

From an implementation point of view, you really start noticing the difference when the time it takes to handle the calling context is comparable to the time it takes for your method to execute. If your recursive method takes longer to execute then the calling context management part, go the recursive way as the code is generally more readable and easy to understand and you won't notice the performance loss. Otherwise go iterative for efficiency reasons.

I believe tail recursion in java is not currently optimized. The details are sprinkled throughout this discussion on LtU and the associated links. It may be a feature in the upcoming version 7, but apparently it presents certain difficulties when combined with Stack Inspection since certain frames would be missing. Stack Inspection has been used to implement their fine-grained security model since Java 2.

http://lambda-the-ultimate.org/node/1333

Using recursion, you're incurring the cost of a function call with each "iteration", whereas with a loop, the only thing you usually pay is an increment/decrement. So, if the code for the loop isn't much more complicated than the code for the recursive solution, loop will usually be superior to recursion.

It depends on the language. In Java you should use loops. Functional languages optimize recursion.

Recursion and iteration depends on the business logic that you want to implement, though in most of the cases it can be used interchangeably. Most developers go for recursion because it is easier to understand.

I would think in (non tail) recursion there would be a performance hit for allocating a new stack etc every time the function is called (dependent on language of course).

it depends on "recursion depth". it depends on how much the function call overhead will influence the total execution time.

For example, calculating the classical factorial in a recursive way is very inefficient due to: - risk of data overflowing - risk of stack overflowing - function call overhead occupy 80% of execution time

while developing a min-max algorithm for position analysis in the game of chess that will analyze subsequent N moves can be implemented in recursion over the "analysis depth" (as I'm doing ^_^)

Mike is correct. Tail recursion is not optimized out by the Java compiler or the JVM. You will always get a stack overflow with something like this:

int count(int i) {
  return i >= 100000000 ? i : count(i+1);
}

I found another differences between those approaches. It looks simple and unimportant, but it has a very important role while you prepare for interviews and this subject arises, so look closely.

In short: 1) iterative post-order traversal is not easy - that makes DFT more complex 2) cycles check easier with recursion

Details:

In the recursive case, it is easy to create pre and post traversals:

Imagine a pretty standard question: "print all tasks that should be executed to execute the task 5, when tasks depend on other tasks"

Example:

    //key-task, value-list of tasks the key task depends on
    //"adjacency map":
    Map<Integer, List<Integer>> tasksMap = new HashMap<>();
    tasksMap.put(0, new ArrayList<>());
    tasksMap.put(1, new ArrayList<>());

    List<Integer> t2 = new ArrayList<>();
    t2.add(0);
    t2.add(1);
    tasksMap.put(2, t2);

    List<Integer> t3 = new ArrayList<>();
    t3.add(2);
    t3.add(10);
    tasksMap.put(3, t3);

    List<Integer> t4 = new ArrayList<>();
    t4.add(3);
    tasksMap.put(4, t4);

    List<Integer> t5 = new ArrayList<>();
    t5.add(3);
    tasksMap.put(5, t5);

    tasksMap.put(6, new ArrayList<>());
    tasksMap.put(7, new ArrayList<>());

    List<Integer> t8 = new ArrayList<>();
    t8.add(5);
    tasksMap.put(8, t8);

    List<Integer> t9 = new ArrayList<>();
    t9.add(4);
    tasksMap.put(9, t9);

    tasksMap.put(10, new ArrayList<>());

    //task to analyze:
    int task = 5;


    List<Integer> res11 = getTasksInOrderDftReqPostOrder(tasksMap, task);
    System.out.println(res11);**//note, no reverse required**

    List<Integer> res12 = getTasksInOrderDftReqPreOrder(tasksMap, task);
    Collections.reverse(res12);//note reverse!
    System.out.println(res12);

    private static List<Integer> getTasksInOrderDftReqPreOrder(Map<Integer, List<Integer>> tasksMap, int task) {
         List<Integer> result = new ArrayList<>();
         Set<Integer> visited = new HashSet<>();
         reqPreOrder(tasksMap,task,result, visited);
         return result;
    }

private static void reqPreOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {

    if(!visited.contains(task)) {
        visited.add(task);
        result.add(task);//pre order!
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPreOrder(tasksMap,child,result, visited);
            }
        }
    }
}

private static List<Integer> getTasksInOrderDftReqPostOrder(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    reqPostOrder(tasksMap,task,result, visited);
    return result;
}

private static void reqPostOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {
    if(!visited.contains(task)) {
        visited.add(task);
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPostOrder(tasksMap,child,result, visited);
            }
        }
        result.add(task);//post order!
    }
}

Note that the recursive post-order-traversal does not require a subsequent reversal of the result. Children printed first and your task in the question printed last. Everything is fine. You can do a recursive pre-order-traversal (also shown above) and that one will require a reversal of the result list.

Not that simple with iterative approach! In iterative (one stack) approach you can only do a pre-ordering-traversal, so you obliged to reverse the result array at the end:

    List<Integer> res1 = getTasksInOrderDftStack(tasksMap, task);
    Collections.reverse(res1);//note reverse!
    System.out.println(res1);

    private static List<Integer> getTasksInOrderDftStack(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> st = new Stack<>();


    st.add(task);
    visited.add(task);

    while(!st.isEmpty()){
        Integer node = st.pop();
        List<Integer> children = tasksMap.get(node);
        result.add(node);
        if(children!=null && children.size() > 0){
            for(Integer child:children){
                if(!visited.contains(child)){
                    st.add(child);
                    visited.add(child);
                }
            }
        }
        //If you put it here - it does not matter - it is anyway a pre-order
        //result.add(node);
    }
    return result;
}

Looks simple, no?

But it is a trap in some interviews.

It means the following: with the recursive approach, you can implement Depth First Traversal and then select what order you need pre or post(simply by changing the location of the "print", in our case of the "adding to the result list"). With the iterative (one stack) approach you can easily do only pre-order traversal and so in the situation when children need be printed first(pretty much all situations when you need start print from the bottom nodes, going upwards) - you are in the trouble. If you have that trouble you can reverse later, but it will be an addition to your algorithm. And if an interviewer is looking at his watch it may be a problem for you. There are complex ways to do an iterative post-order traversal, they exist, but they are not simple. Example:https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

Thus, the bottom line: I would use recursion during interviews, it is simpler to manage and to explain. You have an easy way to go from pre to post-order traversal in any urgent case. With iterative you are not that flexible.

I would use recursion and then tell: "Ok, but iterative can provide me more direct control on used memory, I can easily measure the stack size and disallow some dangerous overflow.."

Another plus of recursion - it is simpler to avoid / notice cycles in a graph.

Example (preudocode):

dft(n){
    mark(n)
    for(child: n.children){
        if(marked(child)) 
            explode - cycle found!!!
        dft(child)
    }
    unmark(n)
}

It may be fun to write it as recursion, or as a practice.

However, if the code is to be used in production, you need to consider the possibility of stack overflow.

Tail recursion optimization can eliminate stack overflow, but do you want to go through the trouble of making it so, and you need to know you can count on it having the optimization in your environment.

Every time the algorithm recurses, how much is the data size or n reduced by?

If you are reducing the size of data or n by half every time you recurse, then in general you don't need to worry about stack overflow. Say, if it needs to be 4,000 level deep or 10,000 level deep for the program to stack overflow, then your data size need to be roughly 2⁴⁰⁰⁰ for your program to stack overflow. To put that into perspective, a biggest storage device recently can hold 2⁶¹ bytes, and if you have 2⁶¹ of such devices, you are only dealing with 2¹²² data size. If you are looking at all the atoms in the universe, it is estimated that it may be less than 2⁸⁴. If you need to deal with all the data in the universe and their states for every millisecond since the birth of the universe estimated to be 14 billion years ago, it may only be 2¹⁵³. So if your program can handle 2⁴⁰⁰⁰ units of data or n, you can handle all data in the universe and the program will not stack overflow. If you don't need to deal with numbers that are as big as 2⁴⁰⁰⁰ (a 4000-bit integer), then in general you don't need to worry about stack overflow.

However, if you reduce the size of data or n by a constant amount every time you recurse, then you can run into stack overflow when n becomes merely 20000. That is, the program runs well when n is 1000, and you think the program is good, and then the program stack overflows when some time in the future, when n is 5000 or 20000.

So if you have a possibility of stack overflow, try to make it an iterative solution.

As far as I know, Perl does not optimize tail-recursive calls, but you can fake it.

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

When first called it will allocate space on the stack. Then it will change its arguments, and restart the subroutine, without adding anything more to the stack. It will therefore pretend that it never called its self, changing it into an iterative process.

Note that there is no "my @_;" or "local @_;", if you did it would no longer work.