CODEWITHSUNDEEP
crecursiontail-recursion
want2
want2

Reputation: 49

Apply Tail Recursion for the piece of code in C language?

The below is a piece of code which uses recursion to find the product of numbers in an array, but i am not getting how to do the same tail recursively any suggestions?

  int Product(int a[], int i, int n) 
   {
    return (i >= n) ? 1 : a[i] * Product(a, i + 1, n);
   }

Upvotes: 1

Views: 62

Answers (1)

Thomas Levesque
Thomas Levesque

Reputation: 292425

In its current form, your code isn't tail recursive. The recursive call has to be the last instruction in the function, and in your code the multiplication happens after the recursive call. So you have to change the signature to take an accumulator that will hold the product of the numbers so far:

int Product(int a[], int i, int n, int acc) 
{
   return (i >= n) ? 1 : Product(a, i + 1, n, a[i] * acc);
}

For the initial call, you should pass 1 as the accumulator value. Since the tail recursive form isn't very convenient to use, you can separate the function into a helper function and another function with the actual implementation:

int Product(int a[], int i, int n)
{
    return TailProduct(a, i, n, 1);
}

int TailProduct(int a[], int i, int n, int acc) 
{
   return (i >= n) ? 1 : Product(a, i + 1, n, a[i] * acc);
}

Upvotes: 2

Related Questions