Recursion

Question 1

What is Recursion?

Answer 1

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph,

Question 2

What is a Base Case?

Answer 2

the solution to base case is provided and solution of bigger problem is expressed in terms of smaller problems.

Question 3

Why stack overflow occurs?

Answer 3

Each time a function is called, it’s removed from a call stack. The nature of a stack is LIFO. Before the call stack can begin calling its functions, it needs a starting point (base case) otherwise it will be building new stacks until infinity. It should instead stop the stacks from accumulating, and begin executing the functions and popping them off one at a time.

Question 4

What is the difference between direct and indirect recursion?

Answer 4

Direct recursion happens when a function calls itself. Indirect recursion is when functions call another function which calls the original function.

void directRecFun()
{
    // Some code....

directRecFun();

    // Some code...
}

// An example of indirect recursion
void indirectRecFun1()
{
    // Some code...

indirectRecFun2();

    // Some code...
}
void indirectRecFun2()
{
    // Some code...

indirectRecFun1();

    // Some code...
}

Question 5

What is the difference between tailed and non tailed recursion

Answer 5

A recursive function is tail recursive when recursive call is the last thing executed by the function.

The tail recursive functions considered better than non tail recursive functions as tail-recursion can be optimized by compiler. The idea used by compilers to optimize tail-recursive functions is simple, since the recursive call is the last statement, there is nothing left to do in the current function, so saving the current function’s stack frame is of no use

An example of non tail is the factorial recursive function. The recursed data is used in the middle of the function, not the end.

Question 6

How is memory allocated to different function calls in recursion?

Answer 6

When any function is called from main(), the memory is allocated to it on stack. A recursive function calls itself, the memory for called function is allocated on top of memory allocated to calling function and different copy of local variables is created for each function call. When the base case is reached, the function returns its value to the function by whom it is called and memory is de-allocated and the process continues.

Question 7

What are the disadvantages of recursive programming over iterative programming?

Answer 7

Note that both recursive and iterative programs have same problem solving powers, i.e., every recursive program can be written iteratively and vice versa is also true. Recursive program has greater space requirements than iterative program as all functions will remain in stack until base case is reached. It also has greater time requirements because of function calls and return overhead.

Question 8

What are the advantages of recursive programming over iterative programming?

Answer 8

Recursion provides a clean and simple way to write code. Some problems are inherently recursive like tree traversals, Tower of Hanoi, etc. For such problems it is preferred to write recursive code. We can write such codes also iteratively with the help of stack data structure. For example refer Inorder Tree Traversal without Recursion, Iterative Tower of Hanoi.