Recursive Cumulative Sum

Question

I'm trying to write a simple recursive sum function in c++:

long long int recursum(long long int n){
    if(n==1)
        return 1;
    else
        return recursum(n-1)+n;
}

This should work, but I get segfaults with values greater than ~250000.I am very sure that this should work, as it is a very simple recursion with a terminal statement.

The stack is finite. How big do you need it to be? How big is it actually? Bonus points: could you make your code tail-recursive? — Alan Stokes, Dec 08 '13 at 19:46
you'll also get stack overflows if you call `recursum` passing a negative value or zero — brunocodutra, Dec 08 '13 at 19:46
@brunocodutra: Or zero, for that matter. But in both those cases, even an infinite depth stack wouldn't help, because the recursion won't terminate. — Joe Z, Dec 08 '13 at 19:47
@JoeZ I added zero to the set of forbidden input values just before your comment, but anyways, you are right and that's exactly what I meant. I just meant to call attention to the fact the algorithm does not check if its input is valid. — brunocodutra, Dec 08 '13 at 19:51
@bruno A function is not required to behave sensibly if its precondition is violated. — Alan Stokes, Dec 08 '13 at 19:53
@JoeZ: If you choose to put down an answer, I'll delete mine. — Jacob, Dec 08 '13 at 19:53
@AlanStokes Sure, but you must agree with me that there are ways of avoiding having to even deal with this caveat. To mention a very straightforward one, why not use an unsigned integer and use n==0 as the recursion guard? This is not directly related to the OP's question, that's true, but I believe calling attention to an arguably bad programming practice to be a very sensible advice to be given as a side comment on a place meant for helping us programmers to improve our skills. — brunocodutra, Dec 08 '13 at 20:24
@bruno Yes. Documenting the precondition would also work, but avoiding it is good if doing so is cheap. (Sometimes the check is expensive, in which case it is reasonable to require the caller to supply valid input ) — Alan Stokes, Dec 08 '13 at 20:45
@AlanStokes I must disagree with you on your assertion that *documenting the precondition would also work*. It does not *work*. The only thing it does is to explicitly blame the user for any unexpected behavior caused by an invalid input. That's shameful. I do understand checks can be expensive on some specific contexts, but overcoming these obstacles without forcing the user to put up with a hideous API is what distinguishes a good programmer from a bad one. Nonetheless, it must be pointed out, that we are not dealing with an example of such constrained contexts here. — brunocodutra, Dec 08 '13 at 21:07
@bruno we are getting very off-topic. But I don't think you are getting what precondition means. If you call a function violating its precondition, it may do anything at all. See also "undefined behaviour". — Alan Stokes, Dec 08 '13 at 22:12
@AlanStokes I do believe I get what you mean by *violation of preconditions*. I believe thus I wasn't clear myself. On the example, there is no *preconditions* imposed by the **language standards**, requiring the user not to call the function passing either a negative value or zero. This requirement is solely implicit to the algorithm. Adding a documentation note stating preconditions and expect the user to take responsibility for it is horrible, for it leads to a hideous API. I defend it is the duty of a good programmer to preserve an intuitive API while attending to resources constraints. — brunocodutra, Dec 08 '13 at 23:09

score 2 · Accepted Answer · answered Dec 08 '13 at 19:54

You have to activate the optimization for your compiler to try to "unrecurse" functions in order to not explode your call stack.

Example tested here on my computer

#include <iostream>

long long int recursum(long long int n){
    if(n==1)
        return 1;
    else
        return recursum(n-1)+n;
}


int main(int argc, char const *argv[])
{
    std::cout << recursum(99000) << std::endl;
    return 0;
}

No optim:

$ ./a.exe
Segmentation fault (core dumped)

With g++ -O3:

$ ./a.exe
4900549500

And I even try with 500000.

Tail recursion optimization and things like that (I don't know the name of the others) are not done without specific demand for optimizatin.

@AlanStokes Yep, I was aware of optim in C++ for TRC, but not for more general recursive calls. — Johan, Dec 08 '13 at 20:03

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

0

Your code is fine for positive n. For integer n < 1, it will never terminate.

For your specific problem, your stack is exhausted which causes a segfault.

edited May 23 '17 at 12:14

Community

1
1

answered Dec 08 '13 at 19:51

Jacob

34,255
14
110
165

score 0 · Answer 3 · answered Dec 08 '13 at 19:53

0

For that trivial problem or sum there are better ways to count this. try N * (N+1) / 2 or iteration (for ...)

answered Dec 08 '13 at 19:53

Paul Dew

159
1
12

Zac Howland · Answer 4 · 2013-12-08T20:00:42.763

0

For starters, you'll want to limit it to unsigned integers:

unsigned long long recursum(unsigned long long n)

To prevent the stack from filling up, see if your compiler supports Tail Recursion Optimization. This will basically prevent it from having to flood the call stack with recursive functions like this. I would also modify your function to handle 0 (which yours currently does not do):

unsigned long long recursum(unsigned long long n)
{
    return n ? n + recursum(n - 1) : n;
}

Or a version that supports TRO:

unsigned long long recursum(unsigned long long n, unsigned long long result = 0)
{
    return n ? recursum(n - 1, result + n) : result;
}

edited Dec 08 '13 at 20:00

answered Dec 08 '13 at 19:54

Zac Howland

15,777
1
26
42

This function is not tail recursive. (Although it could be transformed to one that is.) – Alan Stokes Dec 08 '13 at 19:56
@AlanStokes True. I've added a version that does. – Zac Howland Dec 08 '13 at 20:00
I took your suggestions and changed the variables to unsigned. I'm not sure how your code works, though. You use some operators I have never seen before. – Starfy_S Dec 08 '13 at 21:32
`x ? a : b` is called the ternary operator. Basically, it is a short-hand way to write `if (x) a else b`. – Zac Howland Dec 09 '13 at 00:43

score 0 · Answer 5 · answered Dec 08 '13 at 19:54

Looks like your compiler does not doing tail recursion optimization and you are getting stackoverflow error. Try to play around with optimization flags from your compiler or rewrite your function without recursion.

long long int recursum(long long int n)
{
  long long int result = 0;
  for (int i = 1; i <= n; ++i)
    result += i;
  return result;
}

score 0 · Answer 6 · answered Dec 08 '13 at 19:54

0

Id guess that the stack is not big enough for more than 250000 recursive method calls.

The program has to remember the return adress for every recursive call, so 250000 jump adresses have to be saved in the stack. This possibly exceeds the stack.

answered Dec 08 '13 at 19:54

tly

1,202
14
17

Recursive Cumulative Sum

6 Answers6