What are the advantages and disadvantages of recursion

Question

With respect to using recursion over non-recursive methods in sorting algorithms or  for that matter  any algorithm what are its pros and cons

User · Answer

Recursion means a function calls repeatedly

It uses system stack to accomplish it's task. As stack uses LIFO approach and when a function is called the controlled is moved to where function is defined which has it is stored in memory with some address, this address is stored in stack

Secondly, it reduces a time complexity of a program.

Though bit off-topic,a bit related. Must read. : Recursion vs Iteration

User · Answer

Any algorithm implemented using recursion can also be implemented using iteration   Why not to use recursion   It is usually slower due to the overhead of maintaining the stack  It usually uses more memory for the stack    Why to use recursion   Recursion adds clarity and  sometimes  reduces the time needed to write and debug code  but doesn t necessarily reduce space requirements or speed of execution   Reduces time complexity  Performs better in solving problems based on tree structures    For example  the Tower of Hanoi problem is more easily solved using recursion as opposed to iteration

User · Answer

For the most part recursion is slower  and takes up more of the stack as well  The main advantage of recursion is that for problems like tree traversal it make the algorithm a little easier or more  elegant   Check out some of the comparisons   link

User · Answer

Expressiveness  Most problems are naturally expressed by recursion such as Fibonacci  Merge sorting and quick sorting  In this respect  the code is written for humans  not  machines    Immutability  Iterative solutions often rely on varying temporary variables which makes the code hard to read  This can be avoided with recursion   Performance  Recursion is not stack friendly  Stack can overflow when the recursion is not well designed or tail optimization is not supported

User · Answer

Some situation would arise where you would have to abandon recursion in a problem where recursion appears to be to your advantage  this is because for problems where your recursion would have to occur thousand of times this would result in a stackoverflow error even though your code did not get stuck in an infinite recursion  Most programming languages limits you to a number of stack calls  so if your recursion goes beyond this limit  then you might consider not using recursion

User · Answer

All algorithms can be defined recursively   That makes it much  much easier to visualize and prove     Some algorithms  e g   the Ackermann Function  cannot  easily  be specified iteratively     A recursive implementation will use more memory than a loop if tail call optimization can t be performed   While iteration may use less memory than a recursive function that can t be optimized  it has some limitations in its expressive power

User · Answer

We should use recursion in following scenarios    when we don t know the finite number of iteration for example our fuction exit condition is based on dynamic programming  memoization  when we need to perform operations on reverse order of the elements  Meaning we want to process last element first and then n-1  n-2 and so on till first element   Recursion will save multiple traversals  And it will be useful  if we can divide the stack allocation like   int N   10  int output   process N    process N 2   public void process int n        if  n  N 2   1    n  1           return 1             return process n-1    process n-2       In this case only half stacks will be allocated at any given time

User · Answer

I personally prefer using Iterative over recursive function  Especially if you function has complex heavy logic and number of iterations are large  This because with every recursive call call stack increases  It could potentially crash the stack if you operations are too large and also slow up process

User · Answer

Recursion gets a bad rep  I m always surprised by the number of developers that wont even touch recursion because someone told them it was evil incarnate  I ve learned through trial and error that when done properly recursion can be one of the fastest ways to iterate over something  it is not a steadfast rule and each language  compiler  engine has it s own quirks so mileage will vary  In javascript I can reliably speed up almost any iterative process by introducing recursion with the added benefit of reducing side effects and making the code more clear concise and reusable  Also pro tip its possible to get around the stack overflow issue  and no you dont disable the warning   My personal Pros  amp  Cons  Pros  - Reduces side effects  - Makes code more concise and easier to reason about  - Reduces system resource usage and performs better than the traditional for loop   Cons  - Can lead to stack overflow  - More complicated to setup than a traditional for loop   Mileage will vary depending on language  complier  engine

User · Answer

To start   Pros    It is the unique way of implementing a variable number of nested loops  and the only elegant way of implementing a big constant number of nested loops     Cons    Recursive methods will often throw a StackOverflowException when processing big sets  Recursive loops don t have this problem though

[recursion] What are the advantages and disadvantages of recursion?

Examples related to recursion