Adding integers to arrays in C++?

Question

Consider:

int sum(const int numbers[], const int size){
    if (size == 0)
        return 0;
    else
        return numbers[0] + sum(numbers+1, size-1);
}

This is a simple recursive function from MIT 6.096 for adding an arbitrary number of integers, and it works.

The thing I cannot understand is in the last line:

How does numbers+1 work, given numbers[] is an int array and you shouldn't be able to add an integer to an int[] constant?

Answer 1

numbers is a pointer ; on each iteration the function sum() advances through the array (this is what numbers+1 does), at the same time decreasing size by 1 (--size would work just as well).

When size reaches 0 this is the exit condition, and the recursion ends.

Answer 2

As πάντα ῥεῖ says int[] decays to int*.

But this sum function is the poor man's solution, you should prefer accumulate:

cout << accumulate(numbers, next(numbers, size), decay_t<decltype(numbers[0])>{});

Live Example

If you have C++17 and a statically allocated array, such as int numbers[size], you can take advantage of cbegin and cend:

cout << accumulate(cbegin(numbers), cend(numbers), decay_t<decltype(numbers[0])>{});

I've attempted to benchmark the recursive sum against accumulate, however sum runs out of stack space before I am able to reach a vector size with a meaningful difference, making accumulate the clear winner.

---

I associate the type of accumulate's init agument with the type of numbers' elements: decay_t<decltype(numbers[0])>{}. The reason for this is if someone was to come back and change the type of numbers, and not change the type of accumulate's init argument the accumulation would be assigned to the wrong type.

For example if we use the accumulation line: cout << accumulate(cbegin(numbers), cend(numbers), 0), this is fine for int numbers[]. The problem would arise if we switched to define: double numbers[] = {1.3, 2.3, 3.3, 4.3}; but we failed to change the init argument we would sum doubles into an int. This would result in 10 rather than 11.2: http://ideone.com/A12xin

Answer 3

int sum(int *num,int size)
{
int total=0;
                                   /* function to sum integer array */
if (size <= 0) return(ERROR);
while(size--) total+= *num++;
return total;
}

Is faster, more compact, and error tolerant.

Answer 4

As a side note to @πάντα ῥεῖ's answer, here are a few clarifications on the terminology:

The following is another way to depict array notation:

The phrase numbers[1] can also be expressed as *(numbers + 1) Where the * operator is said to dereference the pointer address numbers + 1. dereference can be thought of in this case as read the value pointed to by.

So, the code in your example is using pointer arithmetic. The phrase numbers + 1 is pointer notation, pointing to the second int location of the pointer numbers. size - 1 is a count of bytes from the memory location starting at numbers to the end of the array.

As to the meaning of decayed:
Generally, within the context of C array arguments, decay conveys the idea that the array argument experiences loss of type and dimension information. Your const int numbers[] is said (arguably) to decay into an int *, therefore no longer able to provide array size information. (Using the sizeof() macro for example does not provide length of array, but size of the pointer.) This also is the reason a second argument is provided, to convey size information.

However, in the context of this question, the meaning of decay is academic, as pointed out by @Ben Voigt: The token sequence const int numbers[], when it appears in a formal parameter list, declares a pointer and not an array. (It never decayed into a pointer because it was a pointer to begin with.)

Answer 5

how does "numbers+1" work, given numbers[] is an int array and you shouldn't be able to add an integer to an int[] constant?

There's no int[] constant. numbers is decayed to a pointer and numbers+1 is simple pointer arithmetic applied to the parameter passed to the recursive call.