CODEWITHSUNDEEP
carraysfunctionpointersrecursion
Patrick Son
Patrick Son

Reputation: 37

Recursive function returning incomprehensible answers

I'm writing a small program for my Computing I class in which the program takes in a number of integers decided by the user and calculates the dot product. I was able to do it successfully using an iterative method, but now we also have to do it using recursion. My function to calculate dot product returns a wide range of incorrect numbers. Sometimes it will just return the value of double the product of the last two values in the arrays, when there were 4 other sets that didn't get added in. Other times, I'll have 2 arrays of 3 small numbers, and the value returned is in the 80 thousands. Here is the recursive function:

//A and B are the arrays that will be dotted together, and n is number of
//elements in each array
int dotP( int *A, int *B, int n ) {
   if( n==1 ) return A[0] * B[0] ;
   return A[n-1] * B[n-1] + dotP( &A[n-1], &B[n-1], n-1);
}

Upvotes: 1

Views: 138

Answers (3)

Luis Colorado
Luis Colorado

Reputation: 12668

Why don't even better use:

int dotP( int *A, int *B, int n ) 
{
   if (n) return A[0] * B[0] + dotP(A + 1, B + 1, n-1);
   else return 0;
}

or in more compact form:

int dotP(int *A, int *B, int n)
{
    if (n) return A[0] * B[0] + dotP(++A, ++B, --n);
    else return 0;
}

Upvotes: 0

DarenW
DarenW

Reputation: 16906

Not

... + dotP( &A[n-1], &B[n-1], n-1 );

but

... + dotP( &A[0], &B[0], n-1 );

since it appears you want to process the last item of the array, then pass the first (n-1) elements to the recursive call. Remember arrays are always dealt with as pointers to their first element, unless you are doing something much trickier than this.

Problem solved but, for educational purposes, try this alternative: you could process the first element and pass the rest, the "tail", which may be more pleasing to the LISP fans:

return A[0] * B[0] + dotP( &A[1], &B[1], n-1 );

Alternatively to that, you could pass A+1 instead of &A[1].

Upvotes: 2

nitish712
nitish712

Reputation: 19764

What exactly happens is 

A[n-1]*B[n-1] + A[n-1 + n-2]*B[n-1 + n-2]+....

It was happening because for the 2nd recursive call, you are passing n-1th element's address. When it calculates A[n-2] in the 2nd call,its pointing effectively to n-2nd element starting from n-1th element, which is 2*n-3rd from the first element of the array.

The values in the array after n are garbage (Assuming you allocated n elements or you may have allocated more than n but did not initialize them). Hence you were getting random answers. You need not pass the address of the current array element to each recursive call. You just pass first element's address which is either A or &A[0]. Then your code works fine. Here's how to do:

int dotP( int *A, int *B, int n ) {
if( n==1 ) return A[0] * B[0] ;
return A[n-1] * B[n-1] + dotP( A, B, n-1) ;
}

Since A and B are pointers already, you just pass them directly.Hope this helps.

Upvotes: 3

Related Questions