Recursion

Recursive Algorithm

- A function called by another function

- Function calls itself

- Direct and Indirect Recursions

- Establish boundary condition that terminate the recursive calls

- Each call must bring nearer to the solution

Recursion Vs Iteration

- Iterative implementation is likely to be slightly faster in practice than the recursive one, as do not pay the "function-call overhead".

- Recursion is used for other types of problems whose solutions are inherently recursive, because they need to keep track of prior state.

- Iterative approach is used as the stack space available to a thread is often much less than the space available in the heap, and recursive algorithms tend to require more stack space than iterative algorithms. This causes stack overflow.

Tail-recursive functions are functions ending in a recursive call that does not build-up any deferred operations. For example, the gcd function (re-shown below) is tail-recursive; however, the factorial function (also re-shown below) is "augmenting recursive" because it builds up deferred operations that must be performed even after the final recursive call completes. With a compiler that automatically optimizes tail-recursive calls, a tail-recursive function such as gcd will execute using constant space. Thus the process it generates is iterative and equivalent to using imperative language control structures like the "for" and "while" loops.

The significance of tail recursion is that when making a tail-recursive call, the caller's return position need not be saved on the call stack; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, on compilers which support tail-recursion optimization, tail recursion saves both space and time.