0

I wrote a Java recursive method that calculates the summation of n from 0 to n. Here's the code:

private static long sum (long n) {
    if (n == 0) {
        return 0;
    } else {
        return n + sum(n-1);
    }
}

When I pass a large number such as 11000 and above, a stack overflow happens sometimes. Yes, I said sometimes. When n is greater than or equals to 11000 the program runs and either gives me the answer or a stack overflow.

Can anyone explain what's going on?

J.Doe
  • 1
  • 2
  • 2
    Related: [What is the maximum depth of the java call stack?](http://stackoverflow.com/questions/4734108/what-is-the-maximum-depth-of-the-java-call-stack) – Andy Turner Jul 07 '16 at 11:50
  • Consider using a [For- loop](https://docs.oracle.com/javase/tutorial/java/nutsandbolts/for.html) instead. – Shaun Wild Jul 07 '16 at 11:50
  • @AlanTuning consider using `n * (n + 1) / 2` instead :) – Andy Turner Jul 07 '16 at 11:50
  • You may be at the stack limit of your environment. An overflow may or may not result in an error depending upon what it happens to overwrite. Any time you overwrite memory that you shouldn't overwrite, it could work sometimes and sometimes not depending upon what that memory represents at that time. What you're experiencing here is the disadvantage to using recursion for certain classes of problems that are best done via iteration. – lurker Jul 07 '16 at 11:51
  • Please refer the below link as it has more details http://stackoverflow.com/questions/4734108/what-is-the-maximum-depth-of-the-java-call-stack – Naveen Potnuru Jul 07 '16 at 12:00

2 Answers2

1

Consider using a For- Loop instead

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

Or of course, you can just use a fancy formula :) Thanks @Andy Turner

public static long sum(long n) {
    return n * (n + 1) / 2;
}

The reason you get a StackOverflow exception is because you're generating a call stack waaay bigger than the JVM expects.

Shaun Wild
  • 1,237
  • 3
  • 17
  • 34
0

Every time you call a method, you need to allocate space on the call stack for that method call in order to store references to local variables and method parameters and such.

The stack is at the top of the address space and is allocated from top to bottom. At the bottom of the address space is the heap, which is allocated from bottom to top. Once the method has been dealt with, it is popped off the stack.

Basically your method will continue to allocate memory on the stack with each call, and the stack will eventually run into the heap if there are too many calls. At that point, you are trying to claim memory that is already being used and you end up with a segmentation fault in the form of a stack overflow.

This is part of the reason why recursive implementation is generally discouraged most of the time.

Matthew Anderson
  • 1