CODEWITHSUNDEEP
c++recursion
Starfy_S
Starfy_S

Reputation: 13

Recursive Cumulative Sum

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.

Upvotes: 1

Views: 3355

Answers (6)

Zac Howland
Zac Howland

Reputation: 15872

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;
}

Upvotes: 0

tly
tly

Reputation: 1262

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.

Upvotes: 0

mika314
mika314

Reputation: 173

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;
}

Upvotes: 0

Johan
Johan

Reputation: 3778

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.

Upvotes: 2

Paul Dew
Paul Dew

Reputation: 141

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

Upvotes: 0

Jacob
Jacob

Reputation: 34601

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.

Upvotes: 0

Related Questions