Sum of an array recursively using one parameter in C

Question

How should I calculate the sum of an array recursively using only one pointer in pure C. The function prototype is given as:

int sum(int *arr);

Here is my code:

int sum(int *arr) {
    int *p, *q;
    p = &arr[0];
    q = p + sizeof(*arr) - 1;
    int total = 0;

    if(p < q) {
        return total + sum(++p);
    }
    else
        return total;
}

This question appears to be off-topic because it is implying _"Please write my code for me."_ [On-topic Reference](http://stackoverflow.com/help/on-topic) — Sourav Ghosh, Aug 17 '15 at 06:15
Welcome to Stack Overflow! Please take the [tour](http://stackoverflow.com/tour) and read [How to Ask](http://stackoverflow.com/help/how-to-ask) to learn what we expect from questions here. Please be aware that we do not provide _from-scratch_ coding service. Please show us what you've tried already, how it failed and we might be able to help.:-) — Sourav Ghosh, Aug 17 '15 at 06:15
@haris Would you mind to talk about it more specifically? I don't know how to end the recursion when it reaches the end of the array. — czqlfy, Aug 17 '15 at 06:20
@czqlfy I'd suggest looking into *sentinel values*. You need a means to mark the end of the array. — juanchopanza, Aug 17 '15 at 06:25
@juanchopanza Thanks for your advice and I did try to write something, as shown on my edit. However I still cannot make it work, and I don't know where the problem is at. — czqlfy, Aug 17 '15 at 06:37
@czqlfy Hint: `sizeof(*arr)` is just `sizeof(int)`. You really need a sentinel value. You can't get the length of an array from a pointer. — juanchopanza, Aug 17 '15 at 06:38
@juanchopanza But the function prototype is given as int sum(int *arr); I can't add another parameter although things would be so much easier if I do so. — czqlfy, Aug 17 '15 at 06:41
@czqlfy For the third time, use a sentinel value. If you don't know what that is, then look it up. — juanchopanza, Aug 17 '15 at 06:43
@juanchopanza All the examples about sentinel values are using loops. I cannot use loop but recursion ONLY for this function. — czqlfy, Aug 17 '15 at 06:47
Is the 'end' of the array perhaps indicated with the value `0`? — meaning-matters, Aug 17 '15 at 07:11

score 2 · Accepted Answer · edited May 23 '17 at 12:23

Not Possible

Two problems:

Where does the array end?

In C, arrays are simply blocks of memory and do not have a length property. It is possible to read unpredictable numbers off the end of the array, from other portions of memory.

In the posted code, sizeof(*arr) apparently is being used to get the length of the array in the pointer arithmetic q = p + sizeof(*arr) - 1

But does sizeof determine array length? Let's find out...

#include <stdio.h>
void main(){
  int a[10] = {0,1,2,3,4,5,6,7,8,9};
  int * p = a;
  int l = sizeof(*p);
  printf("%d\n",l);
}

This prints 4 when compiled and run with gcc, not 10.

Why 4? Because 4 is the size of an int.

And this demonstrates that sizeof will not provide array length.

Therefore, a function int sum(int *arr) will not know when to stop reading unless it is either given a sentinel value for termination or an explicit length of the sum. In strings, the terminal value is 0 but the problem with using 0 here is that it is a perfectly valid number to add in to a sum.

Need for an accumulator.

Most recursive sum functions are essentially fold operations and as such need an accumulator to store the partial result.

Now the accumulator might be put in a static variable, but it isn't generally done that way because it isn't thread safe and leads to more complex code involving copying the final result and resetting the accumulator.

This suggests including an accumulator parameter to hold the sum.

If we also add a parameter for length, we could write:

int sum(int *arr, int len, int accumulator){ 
    if (len==0) return accumulator;
    else return sum(arr+1,len-1,accumulator+*arr);
}

Alternatively, you can use the function stack to store the accumulations and cut out the accumulator parameter like this:

int sum(int *arr, int len){ 
    if (len==0) return 0;
    else return sum(arr+1,len-1)+*arr
}

But a single parameter int sum(int *arr) is impossible as it lacks a parameter to terminate the summing procedure.

score 2 · Answer 2 · answered Aug 17 '15 at 07:33

2

You could use a function like this :

int sum(int *array, int offset, int length)
{   
    if (offset < length - 1)
        return (array[offset] + sum(array, offset + 1, length));
    else
        return (array[offset]);
}

array represents your array / offset the position in your array so when you are using the function use 0 and length will be the length of your array.

Regards.

answered Aug 17 '15 at 07:33

V. Couvignou

109
8

This looks OK. I momentarily forgot you can put the accumulator on the stack this way. – Paul Aug 17 '15 at 07:59

Sum of an array recursively using one parameter in C

2 Answers2

Not Possible