recursion versus iteration

Question

Is it correct to say that everywhere recursion is used a for loop could be used  And if recursion is usually slower what is the technical reason for ever using it over for loop iteration   And if it is always possible to convert an recursion into a for loop is there a rule of thumb way to do it

User · Accepted Answer

Recursion is usually much slower because all function calls must be stored in a stack to allow the return back to the caller functions. In many cases, memory has to be allocated and copied to implement scope isolation.

Some optimizations, like tail call optimization, make recursions faster but aren't always possible, and aren't implemented in all languages.

The main reasons to use recursion are

that it's more intuitive in many cases when it mimics our approach of the problem
that some data structures like trees are easier to explore using recursion (or would need stacks in any case)

Of course every recursion can be modeled as a kind of loop : that's what the CPU will ultimately do. And the recursion itself, more directly, means putting the function calls and scopes in a stack. But changing your recursive algorithm to a looping one might need a lot of work and make your code less maintainable : as for every optimization, it should only be attempted when some profiling or evidence showed it to be necessary.

User · Answer

Besides being slower  recursion can also result in stack overflow errors depending on how deep it goes

User · Answer

Question    And if recursion is usually slower what is the technical reason for ever using it over for loop iteration   Answer   Because in some algorithms are hard to solve it iteratively  Try to solve depth-first search in both recursively and iteratively  You will get the idea that it is plain hard to solve DFS with iteration  Another good thing to try out   Try to write Merge sort iteratively  It will take you quite some time  Question    Is it correct to say that everywhere recursion is used a for loop could be used   Answer   Yes  This thread has a very good answer for this  Question    And if it is always possible to convert an recursion into a for loop is there a rule of thumb way to do it   Answer   Trust me  Try to write your own version to solve depth-first search iteratively  You will notice that some problems are easier to solve it recursively  Hint   Recursion is good when you are solving a problem that can be solved by divide and conquer technique

User · Answer

Yes  as said by Thanakron Tandavas      Recursion is good when you are solving a problem that can be solved by divide and conquer technique    For example  Towers of Hanoi   N rings in increasing size 3 poles Rings start stacked on pole 1  Goal is to move rings so that they are stacked on pole 3    But   Can only move one ring at a time   Can   t put larger ring on top of smaller   Iterative solution is    powerful yet ugly     recursive solution is    elegant

User · Answer

recursion   memorization could lead to a more efficient solution compare with a pure iterative approach  e g  check this  http   jsperf com fibonacci-memoized-vs-iterative-for-large-n

User · Answer

Most of the answers seem to assume that iterative   for loop  If your for loop is unrestricted  a la C  you can do whatever you want with your loop counter   then that is correct  If it s a real for loop  say as in Python or most functional languages where you cannot manually modify the loop counter   then it is not correct    All  computable  functions can be implemented both recursively and using while loops  or conditional jumps  which are basically the same thing   If you truly restrict yourself to for loops  you will only get a subset of those functions  the primitive recursive ones  if your elementary operations are reasonable   Granted  it s a pretty large subset which happens to contain every single function you re likely to encouter in practice   What is much more important is that a lot of functions are very easy to implement recursively and awfully hard to implement iteratively  manually managing your call stack does not count

User · Answer

Is it correct to say that everywhere recursion is used a for loop could be used    Yes  because recursion in most CPUs is modeled with loops and a stack data structure      And if recursion is usually slower what is the technical reason for using it    It is not  usually slower   it s recursion that is applied incorrectly that s slower  On top of that  modern compilers are good at converting some recursions to loops without even asking      And if it is always possible to convert an recursion into a for loop is there a rule of thumb way to do it    Write iterative programs for algorithms best understood when explained iteratively  write recursive programs for algorithms best explained recursively   For example  searching binary trees  running quicksort  and parsing expressions in many programming languages is often explained recursively  These are best coded recursively as well  On the other hand  computing factorials and calculating Fibonacci numbers are much easier to explain in terms of iterations  Using recursion for them is like swatting flies with a sledgehammer  it is not a good idea  even when the sledgehammer does a really good job at it      I borrowed the sledgehammer analogy from Dijkstra s  Discipline of Programming

User · Answer

To write an equivalent method using iteration  we must explicitly use a stack  The fact that the iterative version requires a stack for its solution indicates that the problem is difficult enough that it can benefit from recursion  As a general rule  recursion is most suitable for problems that cannot be solved with a fixed amount of memory and consequently require a stack when solved iteratively  Having said that  recursion and iteration can show the same outcome while they follow different pattern To decide which method works better is case by case and best practice is to choose based on the pattern that problem follows   For example  to find the nth triangular number of  Triangular sequence  1 3 6 10 15     A program that uses an iterative algorithm to find the n th triangular number   Using an iterative algorithm     Triangular java import java util    class Triangular      public static int iterativeTriangular int n          int sum   0        for  int i   1  i  lt   n  i              sum    i        return sum          public static void main String args            Scanner stdin   new Scanner System in         System out print  Please enter a number            int n   stdin nextInt          System out println  The     n    -th triangular number is                                   iterativeTriangular n            enter code here   Using a recursive algorithm     Triangular java import java util    class Triangular      public static int recursiveTriangular int n          if  n    1       return 1          return recursiveTriangular n-1    n            public static void main String args            Scanner stdin   new Scanner System in         System out print  Please enter a number            int n   stdin nextInt          System out println  The     n    -th triangular number is                                    recursiveTriangular n

User · Answer

I seem to remember my computer science professor say back in the day that all problems that have recursive solutions also have iterative solutions   He says that a recursive solution is usually slower  but they are frequently used when they are easier to reason about and code than iterative solutions   However  in the case of more advanced recursive solutions  I don t believe that it will always be able to implement them using a simple for loop

User · Answer

Short answer  the trade off is recursion is faster and for loops take up less memory in almost all cases  However there are usually ways to change the for loop or recursion to make it run faster

[algorithm] recursion versus iteration

Examples related to algorithm

Examples related to recursion

Examples related to iteration