Pages

11/28/2014

Recursion and Tail Recursion


Consider a simple factorial function
Here is a simple Java implementation that uses recursion:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public void factorial(int n)
     {
       if (n <= 1)
         {
            return 1;
         }
        else {
               return n*factorial(n-1);
             }
     }

If you called factorial(5), this is how recursion evaluate.
factorial(5)
5 * factorial(4)
5 * (4 * factorial(3))
5 * (4 * (3 * factorial(2)))
5 * (4 * (3 * (2 * factorial(1))))
5 * (4 * (3 * (2 * 1)))
120
Note how every recursive call has to complete before the java interpreter begins to actually do the work .
Here's a tail-recursive version of function that add N Integers.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public static int sum(int a,int b)
               {
                    if ( a == 0 )
                        {
                           return b;
                        }
                    else{
                           return sum(a-1,b+a);
                        }
               }

Here's the sequence of events that would occur if you called sum(5,0).
sum(5, 0)
sum(4, 5)
sum(3, 9)
sum(2, 12)
sum(1, 14)
sum(0, 15)
15
In the tail-recursive case, with each evaluation of the recursive call, the b is updated.

No comments:

Post a Comment

widget

selenium javascript alert box

This is a easy task to capture javascript based alertbox , /* * To change this license header, choose License Headers in Project Properti...