summing numbers recursively C++

Question

2.00/5 (2 votes)

See more:

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 that:
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:

C++

    // 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();
}

thanks,

Posted 27-Jan-15 7:22am

m.r.m.40

Add a Solution

Comments

Kornfeld Eliyahu Peter 27-Jan-15 13:26pm

Are you aware of the fact that for this sample recursion is a waste of time and resources?

m.r.m.40 27-Jan-15 14:47pm

You're right. There is no need of recursion here, but I'm a beginner and I'm training from the basic problems. see the educational link here if you liked, cs.utah.edu/~germain/PPS/Topics/recursion.html

CHill60 27-Jan-15 13:57pm

Don't use recursion on arrays.
Consider using a vector class[^] instead of an array

Sergey Alexandrovich Kryukov 27-Jan-15 14:38pm

Aren't you trying to advise using recursion on vectors instead? It won't change anything, in this case.
—SA

m.r.m.40 27-Jan-15 16:06pm

Thank you, I didn't know about vectors.

Sergey Alexandrovich Kryukov 27-Jan-15 14:37pm

Why, why recursive?
—SA

m.r.m.40 27-Jan-15 14:47pm

You're right. There is no need of recursion here, but I'm a beginner and I'm training from the basic problems. see the educational link here if you liked, cs.utah.edu/~germain/PPS/Topics/recursion.html

[no name] 27-Jan-15 14:42pm

I can't understand the comments until now. It is a simple example where one can observe how recursion works. Simply to observe and learn, why this should be bad?

N.B: A lot of examples do not make sense, one can see this e.g. in 95% of the article examples.
Bruno

m.r.m.40 27-Jan-15 14:55pm

Thanks,

Sergey Alexandrovich Kryukov 27-Jan-15 15:02pm

Basically, you are right, but it's better to create just a bit more adequate examples.
Perhaps it could be useful to show both bad and good example of recursion and perhaps solve even the bad ones.
In practice, it's very usual that some "teach" students into conclusion that recursion is something bad in general...

After all, I decided to put the Solution 1, please see.

—SA

[no name] 28-Jan-15 1:40am

Great, that you decided to help. And also to go on and explain more about the example of OP. My 5.
Bruno

Sergey Alexandrovich Kryukov 28-Jan-15 2:10am

Thank you, Bruno.
—SA

CHill60 27-Jan-15 19:27pm

Good point. I'd missed it as demonstrating a technique in a learning situation

Andreas Gieriet 27-Jan-15 19:50pm

Each recursion can be converted into an iteration. But some problems are easier implemented and maintained if programmed as recursion. E.g. the Visitor Pattern is a good example for a recursive approach: traversing nested structures may be conveniently done by a visitor.

Or Divide and Conquer is often implemented recursively.

Other cases where recursion is handy: serializing data structures, analyzing graphs (e.g. file trees, network topologies, etc.).

Suggestion: try to implement a file tree visitor that performs some action on each file (e.g. get the file size and sum up all file sizes). This is a more realistic case for a recursive exercise. Caution: a file tree may nest itself by means of links (i.e. leading to infinite recursion --> stack overflow). So, you might need to filter out links.

Cheers
Andi

3 solutions

Solution 1

Please see my comment: using recursion here is a bad thing. So, first of all, forget "its time and space usage be optimal". After you solve the problem, you can discuss the performance problems of such design.

Start with removing 9 and 10 immediate constants from code. Your code should work with all arrays, of any reasonable length, but you are hard-coding it. This is unacceptable. In the test (only in the test), introduce the single length constant and use it everywhere, in particular, pass as a parameter to your function (see below).

When this is done, look at main. In somearray(i), i is undefined (by the way, never use so short names). Your could design the algorithm calculating the sum if one calls, say, sumArray(array, arrayLength, 0) (0 would be where you start your recursion with; you need this parameter for recursion). You really need another parameter to pass the array, because you should not assume that the array is declared on top of code, with this exact name; and another parameter to pass the array length; in C or C++, you don't know the array length from it's pointer.

I hope this is enough for you to continue independently. Fix the problems I explained and proceed. It's important to use the debugger in case of any runtime problems, any at all.

—SA

Posted 27-Jan-15 9:12am

Sergey Alexandrovich Kryukov

Updated 27-Jan-15 9:18am

v5

Comments

m.r.m.40 27-Jan-15 16:15pm

I got it.
one question:
for example for an array with 5 elements we'll have 5 recursion, right? at each recursion it will produce one more array and allocate more memory as much as the array size ?

Sergey Alexandrovich Kryukov 27-Jan-15 16:25pm

Well, 5 recursion iterations... how else? Maybe 6, with 6th iteration incomplete, just calculating that all elements are taken into account and returning the same some. (Think how to avoid the 6th.)
No, not "one more array", but one more element will be added to the sum. Think of it as of the loop without loop statement.
—SA

m.r.m.40 27-Jan-15 16:28pm

Thank you.

Sergey Alexandrovich Kryukov 27-Jan-15 16:29pm

Sure. Are you going to accept the answer formally? In all cases, your follow-up questions will be welcome.
—SA

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Andreas Gieriet · Accepted Answer · 2015-01-27T10:49:00

You may make the example a bit more challenging by employing Divide and conquer algorithms[^].

E.g. calculate the sum by calculating the sum of the left "half" plus the sum of the right "half" of your array.

C++

int sum(int a[], int size)
{
  int result = 0;
  if (size == 1)
  {
    result = a[0];
  }
  else if (size > 1)
  {
    int midpoint = size/2;
    int left = sum(a, midpoint);
    int right = sum(a+midpoint, size-midpoint);
    result = left + right;
  }
  return result;
}

For the purpose of this exercise, add some more arguments to trace the algorithm, e.g.

C++

int sum(int a[], int from, int size, const string& context, int depth)
{
  string indent(depth, '|');
  cout << indent << context << "(a, " << from << ", " << size << ")" << endl;
  int result = 0;
  if (size == 1)
  {
    result = a[from];
  }
  else if (size > 1)
  {
    int midpoint = size/2;
    int left = sum(a, from, midpoint, "left", depth+1);
    int right = sum(a, from+midpoint, size-midpoint, "right", depth+1);
    result = left + right;
    cout << indent << "=" << left << "+" << right << endl;
  }
  cout << indent << "=" << result << endl;
  return result;
}
...
int a[] = { 1,2,3,4,5,6,7,8,9, 10};
cout << "sum = " << sum(a, 0, 10, "sum", 0) << endl;

This results in

sum(a, 0, 10)
|left(a, 0, 5)
||left(a, 0, 2)
|||left(a, 0, 1)
|||=1
|||right(a, 1, 1)
|||=2
||=1+2
||=3
||right(a, 2, 3)
|||left(a, 2, 1)
|||=3
|||right(a, 3, 2)
||||left(a, 3, 1)
||||=4
||||right(a, 4, 1)
||||=5
|||=4+5
|||=9
||=3+9
||=12
|=3+12
|=15
|right(a, 5, 5)
||left(a, 5, 2)
|||left(a, 5, 1)
|||=6
|||right(a, 6, 1)
|||=7
||=6+7
||=13
||right(a, 7, 3)
|||left(a, 7, 1)
|||=8
|||right(a, 8, 2)
||||left(a, 8, 1)
||||=9
||||right(a, 9, 1)
||||=10
|||=9+10
|||=19
||=8+19
||=27
|=13+27
|=40
=15+40
=55
sum = 55

This is a more realistic situation(not for an array, but for some kind of problems). And the recursion depth is reduced too. You are not bound to calculate the left half and the right half. E.g. if you want to take benefit of concurrent calculation of some values, you may divide into multiple parts and conquer ;-)

Cheers
Andi

CPallini · Accepted Answer · 2015-01-27T09:57:00

Solution 2

To stop recursion you either pass the array size or use a special value in the array (say 'the sentinel') to signal end-of-the-array condition (you know, C strings work this way).
Please note the second option is viable only if you know in advance the the array items are a subset of the available int values (e.g. if your program is supposed to add up only positive integers then, for instance, a negative value could be 'the sentinel').

As correctly pointed out by Sergey, forget about 'space and time optimization': recursion is justified here only as an exercise for the coder (but, according to Wirth, such kind of 'recursion exercises' just contribute to the bad reputation of the recursion itself).

Posted 27-Jan-15 9:57am

CPallini

Comments

Sergey Alexandrovich Kryukov 27-Jan-15 16:10pm

5ed, but I want to add that the technique of using "special value" in the array at the end is potentially dangerous and limit the possible set of array to those not containing this value in the middle, this technique is notorious with the huge number of screw-up bugs. Passing the correct length of the array does not cause this problem.

Also your post could be confusing: it may create impression that recursion itself is really bad, not only its reputation in some developers.

—SA

m.r.m.40 27-Jan-15 16:31pm

In the divide and conquer algorithm, would you still say that recursion is bad? and maybe we should use another way to solve a problem?

Sergey Alexandrovich Kryukov 27-Jan-15 16:41pm

Of course recursive can be good in many cases, including divide and conquer; it all depends on other detail. And of course, in the case of array summation, recursion is absolutely bad; and the good is the regular for loop.
—SA

m.r.m.40 27-Jan-15 16:21pm

Thanks.

summing numbers recursively C++

3 solutions

Solution 3

Solution 2

Solution 1

Add your solution here

Preview 0

Existing Members

...or Join us