Understanding Recursion

What is recursion? What is head-recursion and tail-recursion? Should we use recursive or non-recursive functions?

Answer:

In programming, Recursion is way of designing an Algorithm where a function is defined in terms of itself. Typically the function performs some part of the task and rest is defined in terms of itself.

For example: Sum of first n numbers (n being positive) can be defined in terms of Sum of first (n-1) numbers as below.

Few points to note in the above recursion:

 1. A recursion always have a terminating condition (else it will be infinite recursion).
    In the above case the condition that if (n==1) then stop recursion and return 1.
 2. The function performs some tasks and delegate some.
    In the above example, the function performs the addition of n with the return value of the Sum(n-1)
    but delegate the computation of Sum(n-1).

The function (in C language) for the above recursion will be (Not putting a check for n being non-positive)

or to write it in more compact form:

A Iterative version of the above recursion will be

As seen above a recursion can normally be mapped to a loop. So we have two versions a recursive version and an iterative version. Which one of the above do you think is better from a performance point of view?

Next Page : How recursions happens internally... How it happens internally ? Lets see what happens when we call the recursive function as sum(3); Sum(3); will call Sum(2); which will in-turn call sum(1); So the memory stack will have activation records of three functions with each having a local variable n, something like below:

Also consider the fact that when a function calls another, then the state of the calling function (the value of temporary variables, the Instruction Pointer and other register values) is saved in the memory. This state will be reloaded into the memory when the called function will return the control to the calling function (This is conceptually similar to the Context switch which happens in a muti-processing Operating system when one process is preempted to execute the another process and at sometime the control returns back to this process). In the iterative version there will be only one function call to Sum(3) and two local variables i & s on the Activation Record(AR) of the function. We have compared the two for n=3. You may want to compare them for n=1000. The recursive version will take

• Time: O(n)
• Memory: O(n)

While the Iterative version will take:

• Time: O(n)
• Memory: O(1)

The Time may look the same O(n) for both cases, but the constant multiplier with the recursive version will be much bigger than the Iterative version. So recursion is a huge overhead. Both from memory point-of-view and execution time point-of-view. Why should we use Recursion then?

Recursion wins in its Simplicity and Intuitive approach. Not every recursive function can be written in an iterative version with such an ease. For example, Tree traversal functions are very easy & intuitive to write in a recursive manner, but a pain to write the non-recursive version (By non-recursive I does not mean the Stack simulation version of recursive).

If the size of Input is large or Unbounded then recursion is not a good idea.

  Next: Head and Tail Recursion ... Head & Tail Recursion:

A Recursive function typically perform some task and call the recursive function.

If a recursive call is made before the function performs its own task, then it is called Head-recursion. (Recursion is performed at the head of the function body).

In the Above Example, In funciton Sum(3) a call to recursive function Sum(2) will be made first and then the return value from Sum(2) will be added with n. This makes the function Sum, a head-recursive function.

Tip: In C language the order of e valuation of operands for operator + is not defined. It means that in the below statement (where x is an int variable and fun1 and fun2 are functions returning int):

x = fun1() + fun2();

whether fun1 will be called first or fun2 is not defined in the language. This has to be defined by the compiler.

A call to a recursive function is tail-recursive if it is made at the end of the function (after the function performs its own tasks).

Just to see the difference, consider the recursive function to traverse a link list:

If the below link list is send as an input to the above two funcitons:

then the outputs will be:

Head Recursion: 4  3  2  1 (Print the list in reverse order)

Tail Recursion: 1  2  3  4 (Print the list in forward order)

A tail-recursion is very easy to write in the form of a loop. So there should ideally be no reason to write a tail recursion in the code unless you are writing to demonstrate tail-recursion itself. (At least I don't see any convincing example).

  Next: Mixed Recursions ... Mixed recursions:

We have taken simple example above, There can examples of  recursions also which is neither a head recursion nor a tail recursion. Plus, there can be multiple recursive calls to the function within a function. For example Consider the recursive code to traverse a tree in in-order:

The recursive call is made at both, the head and tail. such example are difficult to convert to iterative version, because they do not map to a single loop.