Jun 112012

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


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…

  8 Responses to “Understanding Recursion”

Comments (2) Pingbacks (6)
  1. Best explanation so far found on internet

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>