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

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

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.

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.

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 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 & 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.

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.

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

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.

Any algorithm implemented using recursion can also be implemented using iteration.

Why not to use recursion

1. It is usually slower due to the overhead of maintaining the stack.
2. It usually uses more memory for the stack.

Why to use recursion

1. 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).
2. Reduces time complexity.
3. 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.

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.