0

I found out the maximum of adding numbers(with recursion) to themselves is 21666. To understand what I mean: We have number 5 and we have to add all numbers below including 5 to themselves. The result will be 15. For a loop (with int) the maximum is the int max. But with an recursive method it seems the max is 21666. Why is it like that?

public class Rekursion {

    public static void main(String[] args) {
        int number = 21666;
        System.out.println("Result with a loop: " + add(number));
        System.out.println("Result with recursion: " + recursion(number));
    }

    public static int add(int x) {
        int sum = 0;
        for (int i = 0; i <= x; i++) {
            sum += i;
        }
        return sum;

    }

    public static int recursion(int x) {
        if (x==1){
            return 1;
        }
        else{
            return recursion(x-1)+x;
        }
    }

}
marvin
  • 43
  • 1
  • 6
  • 3
    what happens with 21667? StackoverflowError? – assylias Apr 07 '15 at 15:01
  • Too bad java isn't required to be tail recursive. – Andreas Apr 07 '15 at 15:02
  • @assylias yes StackOverflowError – marvin Apr 07 '15 at 15:05
  • By the way, the sum of `1 + 2 + 3 + ... + n` is equal to `n * (n + 1) / 2`. Not sure if this code was just testing for the given issue or for actual usage. – Obicere Apr 07 '15 at 15:07
  • @Obicere Thanks Obicere, the first thing that came to my mind was the solution with a loop, which works nice. But your solution seems smoother :D Thanks! Basically these are homework and the lecturer wants a random method and a recursive method for solving the "problem". – marvin Apr 07 '15 at 15:40

2 Answers2

5

Each recursive call will allocate a stack frame. Thus, you run out of stack space.

Philipp Claßen
  • 41,306
  • 31
  • 146
  • 239
0

This number is not a magic number and is totally depending on your environnement and the amount of stack memory that your JVM can use. For example it worked with 22000 for me.

rekursion

alainlompo
  • 4,414
  • 4
  • 32
  • 41