What exact happens in the process of Recursion ?

Question

Can anyone tell me what exactly happens in a Recursion Program.. ??

Answer 1

A function calls itself. This can be used instead of iteration, but is generally less efficient as a new stack has to be allocated for each function call.

Answer 2

Recursion, as opposed to iteration, is an algorithm or function design where a function calls itself. This could make a function a lot easier to understand, but makes it slower because a new stack must be created. Also, the stack memory usage will increase linearly with each call.

Iteration, on the other hand, loops through all in one function, keeping the time complexity at O(n), and the space complexity fixed and not increasing with each iteration.

For example, consider a function that adds consecutive numbers. Note that there's a formula to do this in one simple calculation (with O(1) time complexity) but let's just do this as an example.

The recursive function might look like this:

long consecutive(long a) {
    return a > 1 ? a + consecutive(a - 1) : a + 1;
}

You could run out of stack memory very quickly with this recursive calling. However, the iterative model is better for this:

long consecutive(long a) {
    long result = 0, i;
    for (i = 1; i <= a; i++) result += i;
    return result;
}

Answer 3

A function calls itself over and over, until some condition is met.

A silly example: How to walk 100 steps recursively:

 function walk(steps) {
     if (steps > 0) { // not there yet
        take 1 step
        walk(steps - 1); // we're 1 step closer, now walk the rest of the way
     } else { // we're there already, don't walk any further than requested
        echo "You're there!"
     }
 }

 walk(100); // go!

This is what happens:

 walk(100):
   take 1 step
   walk(99):
     take 1 step
     walk(98):
       take 1 step
       walk(97):
         (...)
                   walk(2):
                     take 1 step
                     walk(1):
                       take 1 step
                       walk(0):
                         // "steps > 0" no longer true, use the "else" branch
                         echo "You're there!"

Note that the same thing could be accomplished with a loop ("iteratively"):

function walk(steps) {
  for (c=steps; c > 0; c--) { // note the condition check - "c > 0"
    take 1 step
  }
  echo "You're there!"
}

walk(100); // go!

The program flow would be a bit different, yet the result is the same:

walk(100):
  c=100
  take 1 step
  c=99
  take 1 step
  c=98
  take 1 step
  (...)
  c=2
  take 1 step
  c=1
  take 1 step
  c=0
  // "c > 0" no longer true, exit loop
  echo "You're there!"

It cannot be said whether recursion or iteration is always better. In this example, iteration (loop) is simpler to write and easier to understand than recursion; in other cases (e.g. traversing tree structures), recursion may be a better solution.

Answer 4

An example of recursion:

function foo(doRecurse)
{
    alert("Foo was called");

    if (doRecurse)
    {
        foo(false);
    }
}

foo(true);

In this example, when foo gets called with true, it calls itself again with false. So, you will get two alert messages with the above code. The bit where the function foo calls the function foo is recursion.

Answer 5

A recursive program might look like this:

def f(i):
    if i > 100:
        return 100
    else:
        return f(i+1)

print f(7)

(python)

The question is, what happens? The answer is it is better to think about this in terms of functions and try to write them out.

So, we have the statement print f(7). In order to find out what this evaluates to, we run 7 through the function and find out it evaluates to f(8). Ok great, but what is does that evaluate to? f(9). I have an exit clause in here deliberately - eventually i will equal 100 in the loop and that will be what is returned. What happens:

• f(7) = ?
• f(7) = f(8) = ?
• f(7) = f(8) = f(9) = ?
• f(7) = f(8) = f(9) = f(10) = ?
• ...
• f(7) = f(8) = ... = 100
• so f(7) is 100

This is a fairly trivial example but does demonstrate recursion quite well.

Answer 6

As others mentioned recursion is just a method calling itself. This has several advantages but also some disadvantages.

As Example the typical calculation of factorials:

Iterative version:

int factorial(int factor)
{
    int result = 1;
    int current_factor = 1;
    while (current_factor < factor)
    {
      result *= current_factor;
      ++current_factor;
    }
    return result;
}

Recursive version:

int factorial(int factor)
{
  if (factor == 1) return 1;
  return factor * factorial(factor - 1);
}

As you can see the code is a little shorter and slightly easier to read (if you are used to recursion).

Now lets check the stack:

• Interative version: 3 integer variables (factor, current_factor, result)
• Recursive version:
  factorial of 1: 1 variable (factor)
  factorial of 2: 2 variables (factor and return value of factorial(factor - 1))
  factorial of 3: 3 variables (factor, return value of factorial(factor -1) which has the return value of another factorial(factor - 1)) ...

It looks rougly like this

factorial(5):
  factorial(4):
    factorial(3):
      factorial(2):
        factorial(1):
        1
      2+1
    3+2+1
  4+3+2+1
5+4+3+2+1

As you can see recursion requires more space on the stack (you have to add the return pointers, push and pop of variables and some other stuff a function call requires) and it is usually slower. The space problem can be reduced by using tail-optimized recursion, but thats too big a topic for this post, but just for completeness, an optimized version would look like this:

int factorial(int current, int end, int *result) // result is a pointer, so changes
                                               // on result affect the original variable
{
  if (current > end) return;
  *result = *result * current;
  factorial(current + 1, end, result);
}

The only place where recursion is really helpful is (IMHO) walking through tree structures.