summing numbers recursive C++

Question

I'm trying to make a recursive program that sums an array or a list of numbers. Using visual studio 2013, C++ console application.

My 1st question is: Now I know how many numbers I have and I know the size of my array. How can I program it the way that don't know the numbers in advance, like while it's calculating the numbers there are still new numbers adding up, with the least space usage?

My 2nd question is that: How can i improve the program that still works recursively and its time and space usage be optimal?

Here is my code:

// summing a list of number.cpp
#include "stdafx.h"
#include "iostream"
int array[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int sum = 0, i = 0;
int sumarray(int i){
    if (i < 9){
        sum += array[i];
        i++;
        sumarray(i);
    }
    else
        return sum;
}
int main(){
    std::cout << "sum is ::: " << sumarray(i);
    getchar();
}

Answer 1

here is a working C++ code in Qt, which i wrote - Good Luck I added some debug points outputs to make its understanding clearer

#include <QCoreApplication>
#include <QDebug>
int sum=0;
int sumrec(int *array,int n)
{

    if (n>=0)
    {
       int element=*(array+n); // note *(array+n) -> moving the pointer
                               //      *array+n   -> this is adding n to the pointer data (wrong)
                               // what is array ?
       qDebug() << " element value " << *(array+n) << " at n=" << n << " array address = " << array;
       n--;
       sum=sum+element;
       qDebug() << "sum = " << sum;
       sumrec(array,n);
       return sum;
   }
   else
   {
       return 0;
   }

}


int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    int A[10]={12,13,14,15,16,17,18,19,20,11};
    int b=sumrec(&A[0],9);

    qDebug() << "answer = " << b;

    //return a.exec();
}

here is the output of the terminal

element value  11  at n= 9  array address =  0x7fff5fbffb78 
sum =  11 
 element value  20  at n= 8  array address =  0x7fff5fbffb78 
sum =  31 
 element value  19  at n= 7  array address =  0x7fff5fbffb78 
sum =  50 
 element value  18  at n= 6  array address =  0x7fff5fbffb78 
sum =  68 
 element value  17  at n= 5  array address =  0x7fff5fbffb78 
sum =  85 
 element value  16  at n= 4  array address =  0x7fff5fbffb78 
sum =  101 
 element value  15  at n= 3  array address =  0x7fff5fbffb78 
sum =  116 
 element value  14  at n= 2  array address =  0x7fff5fbffb78 
sum =  130 
 element value  13  at n= 1  array address =  0x7fff5fbffb78 
sum =  143 
 element value  12  at n= 0  array address =  0x7fff5fbffb78 
sum =  155 
answer =  155 

Answer 2

A function to sum the elements of an array would normally accept the array as an argument. In that case, as a practical matter it must also accept the size of the array. Something like this:

int sumarray(int a[], size_t size) {

A signature like that furthermore gives you access to better recursive approaches. In particular, you could recursively compute the sum of the first and second halves of the array, and return their sum:

        size_t midpoint = size / 2;
        return sumarray(a, midpoint) + summaray(a + midpoint, size - midpoint);

That's not a complete solution: you need a termination condition (when size is less than 2). Putting that in and finishing off the function are left as an exercise for you, since you'll learn better if you have to put some work into it yourself.

That approach limits the recursion depth and thus stack size (memory overhead) to be proportional to the logarithm of the array size, though it still involves total numbers of function calls and integer additions proportional to the array size. I don't think you can achieve better asymptotic space or time complexity with a recursive algorithm. (A non-recursive algorithm for this task requires only a fixed number of function calls and and a fixed amount of memory overhead, however.)

Answer 3

If i >= 9, your function does a return sum;.
(that is fine and good)

Where does your function return if i < 9???

if (i < 9){
    sum += array[i];
    i++;
    sumarray(i);  // I see no return statement here!!
}

Basically, if you call sumarray(3), there is no return statement that gets hit.

---

In your program, there is a global variable called i. There is also a local parameter to the function also called i.

The local variable shadows the global variable, so there is no clear purpose to the global i.

---

I'd do it like this:

int array[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

// Pass in the current index, and the size of the array
int sumarray(int i, int sz)
{
    if (sz == 0)
    {
        return 0;
    }
    return array[i] + sumarray(i+1, sz-1);
}

int main(){
    std::cout << "sum is ::: " << sumarray(0, 10);
    // Start at the beginning (index 0)
    // Run for 10 elements.
    getchar();
}

The first recursive call will be to sumarray(1,9); then to sumarray(2,8);... when finally sumarray(10,0) is called, it will return 0.

Answer 4

I hope you'll stop writing functions that depend on global variables to work when they can be easily made to work only with the input they have been provided.

Here's a version that works for me.

#include <iostream>

int sumarray(int array[], int i)
{
   if ( i <= 0 )
   {
      return 0;
   }

   return sumarray(array, i-1) + array[i-1];
}

int main()
{
   int array[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
   std::cout << "sum is : " << sumarray(array, 0) << std::endl;
   std::cout << "sum is : " << sumarray(array, 5) << std::endl;
   std::cout << "sum is : " << sumarray(array, 10) << std::endl;
}

Output:

sum is : 0
sum is : 15
sum is : 55

Answer 5

In C++ you have all the tools to do that in a very simple, readable and safe way. Check out the valarray container:

#include <iostream>
#include <valarray>

int main () {
  std::valarray<int> array{1,2,3,4,5,6,7,8,9,10};
  std::cout << array.sum() << '\n';
  return 0;
}