Recursion or Iteration

Question

Is there a performance hit if we use a loop instead of recursion or vice versa in algorithms where both can serve the same purpose  Eg  Check if the given string is a palindrome  I have seen many programmers using recursion as a means to show off when a simple iteration algorithm can fit the bill  Does the compiler play a vital role in deciding what to use

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

In C   if the recursive function is a templated one  then the compiler has more chance to optimize it  as all the type deduction and function instantiations will occur in compile time  Modern compilers can also inline the function if possible  So if one uses optimization flags like -O3 or -O2 in g    then recursions may have the chance to be faster than iterations  In iterative codes  the compiler gets less chance to optimize it  as it is already in the more or less optimal state  if written well enough    In my case  I was trying to implement matrix exponentiation by squaring using Armadillo matrix objects  in both recursive and iterative way  The algorithm can be found here    https   en wikipedia org wiki Exponentiation by squaring  My functions were templated and I have calculated 1 000 000 12x12 matrices raised to the power 10  I got the following result   iterative   optimisation flag -O3 - gt  2 79   sec recursive   optimisation flag -O3 - gt  1 32   sec  iterative   No-optimisation flag  - gt  2 83   sec recursive   No-optimisation flag  - gt  4 15   sec   These results have been obtained using gcc-4 8 with c  11 flag  -std c  11  and Armadillo 6 1 with Intel mkl  Intel compiler also shows similar results

User · Answer

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

User · Answer

Using just Chrome 45 0 2454 85 m  recursion seems to be a nice amount faster    Here is the code    function recursionVsForLoop global         use strict           Perf test     function perfTest           perfTest prototype do   function ns  fn            console time ns           fn            console timeEnd ns                  Recursion method      function recur             var count   0          global recurFn   function recurFn fn  cycles                fn                count   count   1              if  count     cycles  recurFn fn  cycles                                Looped method     function loopFn fn  cycles            for  var i   0  i  lt  cycles  i                  fn                            Tests     var curTest   new perfTest            testsToRun   100       curTest do  recursion   function             recurFn function                 console log  a recur run                testsToRun                curTest do  loop   function             loopFn function                 console log  a loop run                testsToRun               window     RESULTS     100 runs using standard for loop  100x for loop run  Time to complete  7 683ms     100 runs using functional recursive approach w  tail recursion  100x recursion run  Time to complete  4 841ms  In the screenshot below  recursion wins again by a bigger margin when run at 300 cycles per test

User · Answer

I m going to answer your question by designing a Haskell data structure by  induction   which is a sort of  dual  to recursion   And then I will show how this duality leads to nice things   We introduce a type for a simple tree   data Tree a   Branch  Tree a   Tree a                Leaf a             deriving  Eq    We can read this definition as saying  A tree is a Branch  which contains two trees  or is a leaf  which contains a data value     So the leaf is a sort of minimal case   If a tree isn t a leaf  then it must be a compound tree containing two trees   These are the only cases   Let s make a tree   example    Tree Int example   Branch  Leaf 1                     Branch  Leaf 2                             Leaf 3     Now  let s suppose we want to add 1 to each value in the tree   We can do this by calling   addOne    Tree Int - gt  Tree Int addOne  Branch a b    Branch  addOne a   addOne b  addOne  Leaf a        Leaf  a   1    First  notice that this is in fact a recursive definition   It takes the data constructors Branch and Leaf as cases  and since Leaf is minimal and these are the only possible cases   we are sure that the function will terminate   What would it take to write addOne in an iterative style   What will looping into an arbitrary number of branches look like   Also  this kind of recursion can often be factored out  in terms of a  functor    We can make Trees into Functors by defining   instance Functor Tree where fmap f  Leaf a        Leaf  f a                              fmap f  Branch a b    Branch  fmap f a   fmap f b    and defining   addOne    fmap   1    We can factor out other recursion schemes  such as the catamorphism  or fold  for an algebraic data type   Using a catamorphism  we can write   addOne     cata go where            go  Leaf a    Leaf  a   1             go  Branch a b    Branch a b

User · Answer

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

User · Answer

Recursion is better than iteration for problems that can be broken down into multiple  smaller pieces   For example  to make a recursive Fibonnaci algorithm  you break down fib n  into fib n-1  and fib n-2  and compute both parts  Iteration only allows you to repeat a single function over and over again   However  Fibonacci is actually a broken example and I think iteration is actually more efficient  Notice that fib n    fib n-1    fib n-2  and fib n-1    fib n-2    fib n-3   fib n-1  gets calculated twice   A better example is a recursive algorithm for a tree  The problem of analyzing the parent node can be broken down into multiple smaller problems of analyzing each child node  Unlike the Fibonacci example  the smaller problems are independent of each other   So yeah - recursion is better than iteration for problems that can be broken down into multiple  smaller  independent  similar problems

User · Answer

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  gt   100000000   i   count i 1

User · Answer

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

User · Answer

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

User · Answer

Recursion  Where do I start  wiki will tell you    it   s the process of repeating items in a self-similar way   Back in day when I was doing C  C   recursion was a god send  stuff like  Tail recursion   You ll also find many sorting algorithms use recursion  Quick sort example  http   alienryderflex com quicksort   Recursion is like any other algorithm useful for a specific problem  Perhaps you mightn t find a use straight away or often but there will be problem you   ll be glad it   s available

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

You have to keep in mind that utilizing too deep recursion you will run into Stack Overflow  depending on allowed stack size  To prevent this make sure to provide some base case which ends you recursion

User · Answer

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  gt   100000000   i   count i 1

User · Answer

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

User · Answer

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

User · Answer

You have to keep in mind that utilizing too deep recursion you will run into Stack Overflow  depending on allowed stack size  To prevent this make sure to provide some base case which ends you recursion

User · Answer

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  gt   100000000   i   count i 1

User · Answer

Recursion is more simple  and thus - more fundamental  than any possible definition of an iteration  You can define a Turing-complete system with only a pair of combinators  yes  even a recursion itself is a derivative notion in such a system   Lambda calculus is an equally powerful fundamental system  featuring recursive functions  But if you want to define an iteration properly  you d need much more primitives to start with   As for the code - no  recursive code is in fact much easier to understand and to maintain than a purely iterative one  since most data structures are recursive  Of course  in order to get it right one would need a language with a support for high order functions and closures  at least - to get all the standard combinators and iterators in a neat way  In C    of course  complicated recursive solutions can look a bit ugly  unless you re a hardcore user of FC   and alike

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

Comparing recursion to iteration is like comparing a phillips head screwdriver to a flat head screwdriver   For the most part you could remove any phillips head screw with a flat head  but it would just be easier if you used the screwdriver designed for that screw right    Some algorithms just lend themselves to recursion because of the way they are designed  Fibonacci sequences  traversing a tree like structure  etc     Recursion makes the algorithm more succinct and easier to understand  therefore shareable and reusable    Also  some recursive algorithms use  Lazy Evaluation  which makes them more efficient than their iterative brothers  This means that they only do the expensive calculations at the time they are needed rather than each time the loop runs   That should be enough to get you started  I ll dig up some articles and examples for you too   Link 1  Haskel vs PHP  Recursion vs Iteration   Here is an example where the programmer had to process a large data set using PHP   He shows how easy it would have been to deal with in Haskel using recursion  but since PHP had no easy way to accomplish the same method  he was forced to use iteration to get the result      http   blog webspecies co uk 2011-05-31 lazy-evaluation-with-php html   Link 2  Mastering Recursion  Most of recursion s bad reputation comes from the high costs and inefficiency in imperative languages   The author of this article talks about how to optimize recursive algorithms to make them faster and more efficient   He also goes over how to convert a traditional loop into a recursive function and the benefits of using tail-end recursion   His closing words really summed up some of my key points I think        recursive programming gives the programmer a better way of organizing   code in a way that is both maintainable and logically consistent        https   developer ibm com articles l-recurs    Link 3  Is recursion ever faster than looping   Answer   Here is a link to an answer for a stackoverflow question that is similar to yours  The author points out that a lot of the benchmarks associated with either recursing or looping are very language specific   Imperative languages are typically faster using a loop and slower with recursion and vice-versa for functional languages   I guess the main point to take from this link is that it is very difficult to answer the question in a language agnostic   situation blind sense      Is recursion ever faster than looping

User · Answer

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

User · Answer

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 lt Integer  List lt Integer gt  gt  tasksMap   new HashMap lt  gt         tasksMap put 0  new ArrayList lt  gt          tasksMap put 1  new ArrayList lt  gt           List lt Integer gt  t2   new ArrayList lt  gt         t2 add 0       t2 add 1       tasksMap put 2  t2        List lt Integer gt  t3   new ArrayList lt  gt         t3 add 2       t3 add 10       tasksMap put 3  t3        List lt Integer gt  t4   new ArrayList lt  gt         t4 add 3       tasksMap put 4  t4        List lt Integer gt  t5   new ArrayList lt  gt         t5 add 3       tasksMap put 5  t5        tasksMap put 6  new ArrayList lt  gt          tasksMap put 7  new ArrayList lt  gt           List lt Integer gt  t8   new ArrayList lt  gt         t8 add 5       tasksMap put 8  t8        List lt Integer gt  t9   new ArrayList lt  gt         t9 add 4       tasksMap put 9  t9        tasksMap put 10  new ArrayList lt  gt             task to analyze      int task   5        List lt Integer gt  res11   getTasksInOrderDftReqPostOrder tasksMap  task       System out println res11      note  no reverse required        List lt Integer gt  res12   getTasksInOrderDftReqPreOrder tasksMap  task       Collections reverse res12    note reverse      System out println res12        private static List lt Integer gt  getTasksInOrderDftReqPreOrder Map lt Integer  List lt Integer gt  gt  tasksMap  int task             List lt Integer gt  result   new ArrayList lt  gt              Set lt Integer gt  visited   new HashSet lt  gt              reqPreOrder tasksMap task result  visited            return result         private static void reqPreOrder Map lt Integer  List lt Integer gt  gt  tasksMap  int task  List lt Integer gt  result  Set lt Integer gt  visited         if  visited contains task             visited add task           result add task    pre order          List lt Integer gt  children   tasksMap get task           if  children    null  amp  amp  children size    gt  0                for  Integer child   children                    reqPreOrder tasksMap child result  visited                                    private static List lt Integer gt  getTasksInOrderDftReqPostOrder Map lt Integer  List lt Integer gt  gt  tasksMap  int task        List lt Integer gt  result   new ArrayList lt  gt         Set lt Integer gt  visited   new HashSet lt  gt         reqPostOrder tasksMap task result  visited       return result     private static void reqPostOrder Map lt Integer  List lt Integer gt  gt  tasksMap  int task  List lt Integer gt  result  Set lt Integer gt  visited        if  visited contains task             visited add task           List lt Integer gt  children   tasksMap get task           if  children    null  amp  amp  children size    gt  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 lt Integer gt  res1   getTasksInOrderDftStack tasksMap  task       Collections reverse res1    note reverse      System out println res1        private static List lt Integer gt  getTasksInOrderDftStack Map lt Integer  List lt Integer gt  gt  tasksMap  int task        List lt Integer gt  result   new ArrayList lt  gt         Set lt Integer gt  visited   new HashSet lt  gt         Stack lt Integer gt  st   new Stack lt  gt           st add task       visited add task        while  st isEmpty             Integer node   st pop            List lt Integer gt  children   tasksMap get node           result add node           if children  null  amp  amp  children size    gt  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

User · Answer

Recursion is very useful is some situations  For example consider the code for finding the factorial    int factorial   int input       int x  fact   1    for   x   input  x  gt  1  x--       fact    x    return fact      Now consider it by using the recursive function  int factorial   int input       if  input    0           return 1        return input   factorial input - 1       By observing these two  we can see that recursion is easy to understand  But if it is not used with care it can be so much error prone too   Suppose if we miss if  input    0   then the code will be executed for some time and ends with usually a stack overflow

User · Answer

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

User · Answer

Recursion is more simple  and thus - more fundamental  than any possible definition of an iteration  You can define a Turing-complete system with only a pair of combinators  yes  even a recursion itself is a derivative notion in such a system   Lambda calculus is an equally powerful fundamental system  featuring recursive functions  But if you want to define an iteration properly  you d need much more primitives to start with   As for the code - no  recursive code is in fact much easier to understand and to maintain than a purely iterative one  since most data structures are recursive  Of course  in order to get it right one would need a language with a support for high order functions and closures  at least - to get all the standard combinators and iterators in a neat way  In C    of course  complicated recursive solutions can look a bit ugly  unless you re a hardcore user of FC   and alike

User · Answer

As far as I know  Perl does not optimize tail-recursive calls  but you can fake it   sub f    my  l  r           if   l  gt    r        return  l      else          return f   l 1   r                 l 1   r        goto  amp 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

User · Answer

Recursion is very useful is some situations  For example consider the code for finding the factorial    int factorial   int input       int x  fact   1    for   x   input  x  gt  1  x--       fact    x    return fact      Now consider it by using the recursive function  int factorial   int input       if  input    0           return 1        return input   factorial input - 1       By observing these two  we can see that recursion is easy to understand  But if it is not used with care it can be so much error prone too   Suppose if we miss if  input    0   then the code will be executed for some time and ends with usually a stack overflow

User · Answer

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 24000 for your program to stack overflow  To put that into perspective  a biggest storage device recently can hold 261 bytes  and if you have  261 of such devices  you are only dealing with 2122 data size  If you are looking at all the atoms in the universe  it is estimated that it may be less than 284  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 2153  So if your program can handle 24000 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 24000  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

User · Answer

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

User · Answer

If you re just iterating over a list  then sure  iterate away   A couple of other answers have mentioned  depth-first  tree traversal  It really is such a great example  because it s a very common thing to do to a very common data structure  Recursion is extremely intuitive for this problem   Check out the  find  methods here  http   penguin ewu edu cscd300 Topic BSTintro index html

User · Answer

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

User · Answer

In many cases recursion is faster because of caching  which improves performance  For example  here is an iterative version of merge sort using the traditional merge routine  It will run slower than the recursive implementation because of caching improved performances   Iterative implementation  public static void sort Comparable   a        int N   a length      aux   new Comparable N       for  int sz   1  sz  lt  N  sz   sz sz          for  int lo   0  lo  lt  N-sz  lo    sz sz              merge a  lo  lo sz-1  Math min lo sz sz-1  N-1        Recursive implementation  private static void sort Comparable   a  Comparable   aux  int lo  int hi        if  hi  lt   lo  return      int mid   lo    hi - lo    2      sort a  aux  lo  mid       sort a  aux  mid 1  hi       merge a  aux  lo  mid  hi       PS - this is what was told by Professor Kevin Wayne  Princeton University   on the course on algorithms presented on Coursera

User · Answer

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

User · Answer

Recursion has a disadvantage that the algorithm that you write using recursion has O n  space complexity  While iterative aproach have a space complexity of O 1  This is the advantange of using iteration over recursion  Then why do we use recursion    See below   Sometimes it is easier to write an algorithm using recursion while it s slightly tougher to write the same algorithm using iteration In this case if you opt to follow the iteration approach you would have to handle stack yourself

User · Answer

Using just Chrome 45 0 2454 85 m  recursion seems to be a nice amount faster    Here is the code    function recursionVsForLoop global         use strict           Perf test     function perfTest           perfTest prototype do   function ns  fn            console time ns           fn            console timeEnd ns                  Recursion method      function recur             var count   0          global recurFn   function recurFn fn  cycles                fn                count   count   1              if  count     cycles  recurFn fn  cycles                                Looped method     function loopFn fn  cycles            for  var i   0  i  lt  cycles  i                  fn                            Tests     var curTest   new perfTest            testsToRun   100       curTest do  recursion   function             recurFn function                 console log  a recur run                testsToRun                curTest do  loop   function             loopFn function                 console log  a loop run                testsToRun               window     RESULTS     100 runs using standard for loop  100x for loop run  Time to complete  7 683ms     100 runs using functional recursive approach w  tail recursion  100x recursion run  Time to complete  4 841ms  In the screenshot below  recursion wins again by a bigger margin when run at 300 cycles per test

User · Answer

There are many cases where it gives a much more elegant solution over the iterative method  the common example being traversal of a binary tree  so it isn t necessarily more difficult to maintain  In general  iterative versions are usually a bit faster  and during optimization may well replace a recursive version   but recursive versions are simpler to comprehend and implement correctly

User · Answer

As far as I know  Perl does not optimize tail-recursive calls  but you can fake it   sub f    my  l  r           if   l  gt    r        return  l      else          return f   l 1   r                 l 1   r        goto  amp 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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

If the iterations are atomic and orders of magnitude more expensive than pushing a new stack frame and creating a new thread and you have multiple cores and your runtime environment can use all of them  then a recursive approach could yield a huge performance boost when combined with multithreading  If the average number of iterations is not predictable then it might be a good idea to use a thread pool which will control thread allocation and prevent your process from creating too many threads and hogging the system   For example  in some languages  there are recursive multithreaded merge sort implementations   But again  multithreading can be used with looping rather than recursion  so how well this combination will work depends on more factors including the OS and its thread allocation mechanism

User · Answer

In C   if the recursive function is a templated one  then the compiler has more chance to optimize it  as all the type deduction and function instantiations will occur in compile time  Modern compilers can also inline the function if possible  So if one uses optimization flags like -O3 or -O2 in g    then recursions may have the chance to be faster than iterations  In iterative codes  the compiler gets less chance to optimize it  as it is already in the more or less optimal state  if written well enough    In my case  I was trying to implement matrix exponentiation by squaring using Armadillo matrix objects  in both recursive and iterative way  The algorithm can be found here    https   en wikipedia org wiki Exponentiation by squaring  My functions were templated and I have calculated 1 000 000 12x12 matrices raised to the power 10  I got the following result   iterative   optimisation flag -O3 - gt  2 79   sec recursive   optimisation flag -O3 - gt  1 32   sec  iterative   No-optimisation flag  - gt  2 83   sec recursive   No-optimisation flag  - gt  4 15   sec   These results have been obtained using gcc-4 8 with c  11 flag  -std c  11  and Armadillo 6 1 with Intel mkl  Intel compiler also shows similar results

User · Answer

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

User · Answer

Stack overflow will only occur if you re programming in a language that doesn t have in built memory management     Otherwise  make sure you have something in your function  or a function call  STDLbs  etc   Without recursion it would simply not be possible to have things like    Google or SQL  or any place one must efficiently sort through large data structures  classes  or databases    Recursion is the way to go if you want to iterate through files  pretty sure that s how  find      grep    works  Kinda dual recursion  especially with the pipe  but don t do a bunch of syscalls like so many like to do if it s anything you re going to put out there for others to use    Higher level languages and even clang cpp may implement it the same in the background

User · Answer

Stack overflow will only occur if you re programming in a language that doesn t have in built memory management     Otherwise  make sure you have something in your function  or a function call  STDLbs  etc   Without recursion it would simply not be possible to have things like    Google or SQL  or any place one must efficiently sort through large data structures  classes  or databases    Recursion is the way to go if you want to iterate through files  pretty sure that s how  find      grep    works  Kinda dual recursion  especially with the pipe  but don t do a bunch of syscalls like so many like to do if it s anything you re going to put out there for others to use    Higher level languages and even clang cpp may implement it the same in the background

User · Answer

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  gt   100000000   i   count i 1

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

As far as I know  Perl does not optimize tail-recursive calls  but you can fake it   sub f    my  l  r           if   l  gt    r        return  l      else          return f   l 1   r                 l 1   r        goto  amp 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

User · Answer

I m going to answer your question by designing a Haskell data structure by  induction   which is a sort of  dual  to recursion   And then I will show how this duality leads to nice things   We introduce a type for a simple tree   data Tree a   Branch  Tree a   Tree a                Leaf a             deriving  Eq    We can read this definition as saying  A tree is a Branch  which contains two trees  or is a leaf  which contains a data value     So the leaf is a sort of minimal case   If a tree isn t a leaf  then it must be a compound tree containing two trees   These are the only cases   Let s make a tree   example    Tree Int example   Branch  Leaf 1                     Branch  Leaf 2                             Leaf 3     Now  let s suppose we want to add 1 to each value in the tree   We can do this by calling   addOne    Tree Int - gt  Tree Int addOne  Branch a b    Branch  addOne a   addOne b  addOne  Leaf a        Leaf  a   1    First  notice that this is in fact a recursive definition   It takes the data constructors Branch and Leaf as cases  and since Leaf is minimal and these are the only possible cases   we are sure that the function will terminate   What would it take to write addOne in an iterative style   What will looping into an arbitrary number of branches look like   Also  this kind of recursion can often be factored out  in terms of a  functor    We can make Trees into Functors by defining   instance Functor Tree where fmap f  Leaf a        Leaf  f a                              fmap f  Branch a b    Branch  fmap f a   fmap f b    and defining   addOne    fmap   1    We can factor out other recursion schemes  such as the catamorphism  or fold  for an algebraic data type   Using a catamorphism  we can write   addOne     cata go where            go  Leaf a    Leaf  a   1             go  Branch a b    Branch a b

User · Answer

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

User · Answer

Recursion has a disadvantage that the algorithm that you write using recursion has O n  space complexity  While iterative aproach have a space complexity of O 1  This is the advantange of using iteration over recursion  Then why do we use recursion    See below   Sometimes it is easier to write an algorithm using recursion while it s slightly tougher to write the same algorithm using iteration In this case if you opt to follow the iteration approach you would have to handle stack yourself

User · Answer

Recursion  Where do I start  wiki will tell you    it   s the process of repeating items in a self-similar way   Back in day when I was doing C  C   recursion was a god send  stuff like  Tail recursion   You ll also find many sorting algorithms use recursion  Quick sort example  http   alienryderflex com quicksort   Recursion is like any other algorithm useful for a specific problem  Perhaps you mightn t find a use straight away or often but there will be problem you   ll be glad it   s available

User · Answer

There are many cases where it gives a much more elegant solution over the iterative method  the common example being traversal of a binary tree  so it isn t necessarily more difficult to maintain  In general  iterative versions are usually a bit faster  and during optimization may well replace a recursive version   but recursive versions are simpler to comprehend and implement correctly

User · Answer

In many cases recursion is faster because of caching  which improves performance  For example  here is an iterative version of merge sort using the traditional merge routine  It will run slower than the recursive implementation because of caching improved performances   Iterative implementation  public static void sort Comparable   a        int N   a length      aux   new Comparable N       for  int sz   1  sz  lt  N  sz   sz sz          for  int lo   0  lo  lt  N-sz  lo    sz sz              merge a  lo  lo sz-1  Math min lo sz sz-1  N-1        Recursive implementation  private static void sort Comparable   a  Comparable   aux  int lo  int hi        if  hi  lt   lo  return      int mid   lo    hi - lo    2      sort a  aux  lo  mid       sort a  aux  mid 1  hi       merge a  aux  lo  mid  hi       PS - this is what was told by Professor Kevin Wayne  Princeton University   on the course on algorithms presented on Coursera

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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 24000 for your program to stack overflow  To put that into perspective  a biggest storage device recently can hold 261 bytes  and if you have  261 of such devices  you are only dealing with 2122 data size  If you are looking at all the atoms in the universe  it is estimated that it may be less than 284  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 2153  So if your program can handle 24000 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 24000  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

User · Answer

If the iterations are atomic and orders of magnitude more expensive than pushing a new stack frame and creating a new thread and you have multiple cores and your runtime environment can use all of them  then a recursive approach could yield a huge performance boost when combined with multithreading  If the average number of iterations is not predictable then it might be a good idea to use a thread pool which will control thread allocation and prevent your process from creating too many threads and hogging the system   For example  in some languages  there are recursive multithreaded merge sort implementations   But again  multithreading can be used with looping rather than recursion  so how well this combination will work depends on more factors including the OS and its thread allocation mechanism

User · Answer

If you re just iterating over a list  then sure  iterate away   A couple of other answers have mentioned  depth-first  tree traversal  It really is such a great example  because it s a very common thing to do to a very common data structure  Recursion is extremely intuitive for this problem   Check out the  find  methods here  http   penguin ewu edu cscd300 Topic BSTintro index html

User · Answer

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

User · Answer

As far as I know  Perl does not optimize tail-recursive calls  but you can fake it   sub f    my  l  r           if   l  gt    r        return  l      else          return f   l 1   r                 l 1   r        goto  amp 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

User · Answer

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

User · Answer

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

User · Answer

Comparing recursion to iteration is like comparing a phillips head screwdriver to a flat head screwdriver   For the most part you could remove any phillips head screw with a flat head  but it would just be easier if you used the screwdriver designed for that screw right    Some algorithms just lend themselves to recursion because of the way they are designed  Fibonacci sequences  traversing a tree like structure  etc     Recursion makes the algorithm more succinct and easier to understand  therefore shareable and reusable    Also  some recursive algorithms use  Lazy Evaluation  which makes them more efficient than their iterative brothers  This means that they only do the expensive calculations at the time they are needed rather than each time the loop runs   That should be enough to get you started  I ll dig up some articles and examples for you too   Link 1  Haskel vs PHP  Recursion vs Iteration   Here is an example where the programmer had to process a large data set using PHP   He shows how easy it would have been to deal with in Haskel using recursion  but since PHP had no easy way to accomplish the same method  he was forced to use iteration to get the result      http   blog webspecies co uk 2011-05-31 lazy-evaluation-with-php html   Link 2  Mastering Recursion  Most of recursion s bad reputation comes from the high costs and inefficiency in imperative languages   The author of this article talks about how to optimize recursive algorithms to make them faster and more efficient   He also goes over how to convert a traditional loop into a recursive function and the benefits of using tail-end recursion   His closing words really summed up some of my key points I think        recursive programming gives the programmer a better way of organizing   code in a way that is both maintainable and logically consistent        https   developer ibm com articles l-recurs    Link 3  Is recursion ever faster than looping   Answer   Here is a link to an answer for a stackoverflow question that is similar to yours  The author points out that a lot of the benchmarks associated with either recursing or looping are very language specific   Imperative languages are typically faster using a loop and slower with recursion and vice-versa for functional languages   I guess the main point to take from this link is that it is very difficult to answer the question in a language agnostic   situation blind sense      Is recursion ever faster than looping

User · Answer

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 lt Integer  List lt Integer gt  gt  tasksMap   new HashMap lt  gt         tasksMap put 0  new ArrayList lt  gt          tasksMap put 1  new ArrayList lt  gt           List lt Integer gt  t2   new ArrayList lt  gt         t2 add 0       t2 add 1       tasksMap put 2  t2        List lt Integer gt  t3   new ArrayList lt  gt         t3 add 2       t3 add 10       tasksMap put 3  t3        List lt Integer gt  t4   new ArrayList lt  gt         t4 add 3       tasksMap put 4  t4        List lt Integer gt  t5   new ArrayList lt  gt         t5 add 3       tasksMap put 5  t5        tasksMap put 6  new ArrayList lt  gt          tasksMap put 7  new ArrayList lt  gt           List lt Integer gt  t8   new ArrayList lt  gt         t8 add 5       tasksMap put 8  t8        List lt Integer gt  t9   new ArrayList lt  gt         t9 add 4       tasksMap put 9  t9        tasksMap put 10  new ArrayList lt  gt             task to analyze      int task   5        List lt Integer gt  res11   getTasksInOrderDftReqPostOrder tasksMap  task       System out println res11      note  no reverse required        List lt Integer gt  res12   getTasksInOrderDftReqPreOrder tasksMap  task       Collections reverse res12    note reverse      System out println res12        private static List lt Integer gt  getTasksInOrderDftReqPreOrder Map lt Integer  List lt Integer gt  gt  tasksMap  int task             List lt Integer gt  result   new ArrayList lt  gt              Set lt Integer gt  visited   new HashSet lt  gt              reqPreOrder tasksMap task result  visited            return result         private static void reqPreOrder Map lt Integer  List lt Integer gt  gt  tasksMap  int task  List lt Integer gt  result  Set lt Integer gt  visited         if  visited contains task             visited add task           result add task    pre order          List lt Integer gt  children   tasksMap get task           if  children    null  amp  amp  children size    gt  0                for  Integer child   children                    reqPreOrder tasksMap child result  visited                                    private static List lt Integer gt  getTasksInOrderDftReqPostOrder Map lt Integer  List lt Integer gt  gt  tasksMap  int task        List lt Integer gt  result   new ArrayList lt  gt         Set lt Integer gt  visited   new HashSet lt  gt         reqPostOrder tasksMap task result  visited       return result     private static void reqPostOrder Map lt Integer  List lt Integer gt  gt  tasksMap  int task  List lt Integer gt  result  Set lt Integer gt  visited        if  visited contains task             visited add task           List lt Integer gt  children   tasksMap get task           if  children    null  amp  amp  children size    gt  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 lt Integer gt  res1   getTasksInOrderDftStack tasksMap  task       Collections reverse res1    note reverse      System out println res1        private static List lt Integer gt  getTasksInOrderDftStack Map lt Integer  List lt Integer gt  gt  tasksMap  int task        List lt Integer gt  result   new ArrayList lt  gt         Set lt Integer gt  visited   new HashSet lt  gt         Stack lt Integer gt  st   new Stack lt  gt           st add task       visited add task        while  st isEmpty             Integer node   st pop            List lt Integer gt  children   tasksMap get node           result add node           if children  null  amp  amp  children size    gt  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

User · Answer

Recursion is better than iteration for problems that can be broken down into multiple  smaller pieces   For example  to make a recursive Fibonnaci algorithm  you break down fib n  into fib n-1  and fib n-2  and compute both parts  Iteration only allows you to repeat a single function over and over again   However  Fibonacci is actually a broken example and I think iteration is actually more efficient  Notice that fib n    fib n-1    fib n-2  and fib n-1    fib n-2    fib n-3   fib n-1  gets calculated twice   A better example is a recursive algorithm for a tree  The problem of analyzing the parent node can be broken down into multiple smaller problems of analyzing each child node  Unlike the Fibonacci example  the smaller problems are independent of each other   So yeah - recursion is better than iteration for problems that can be broken down into multiple  smaller  independent  similar problems

[performance] Recursion or Iteration?

Examples related to performance

Examples related to algorithm

Examples related to language-agnostic

Examples related to recursion