Avoiding stack overflow error for Fibonacci sequence

Question

I was originally solving the Project Euler problem #2 which computes even numbers of the fibonacci sequence up to 4,000,000. I completed this and then I wanted to increase the maximum number so that it would continue infinitely, producing results more slowing as it took longer to compute.

I got a Stack Overflow Error and wondered if there was an alternative solution for the code so that it would be able to continue running, albeit slowly, without encountering a stack overflow error.

Can someone please provide assistance in refactoring my solution? Thanks.

The relevant code for this problem has been provided below.

public static void main(String[] args) {
    fibonacci(1,2,2);
  }

  private static void fibonacci(long first, long second, long sum) {
       long number = first + second;       
         if (number % 2 == 0){ //Checks for even number
           sum = sum + number;
         }
         System.out.println(sum);
         fibonacci(second, number, sum);
         // Produces the following error:
         // Exception in thread "main" java.lang.StackOverflowError
  }

http://stackoverflow.com/questions/849813/large-numbers-in-java — Joseph Boyle, Apr 27 '16 at 14:22
@Gangaraju Looks like he's doing fibo backwards... Starts at 1 and tends towards infinity. He wants the recursion to never stop so he doesn't have a base case. — Joseph Boyle, Apr 27 '16 at 14:24

score 1 · Answer 1 · answered Apr 27 '16 at 14:24

1

You're problem is that you don't have a terminating condition to stop the recursion, you are keep on going until your run out of stack space.

The general format of a recursive function in pseudo code is:

return-typo function(some, values)
{
  if(got to the end of recursion based on some values)
  {
    return something;
  }
  else
  {
    // Recurse
    return function(changes to some values);
  }
}

NOTE: This isn't a hard and fast rule, just a general outline.

answered Apr 27 '16 at 14:24

Sean

60,939
11
97
136

Thanks, I'm not looking to have a boundary condition because I would like to calculate infinitely. – Hiphop03199 Apr 27 '16 at 14:32
@Hiphop03199 - You can't count infinitely If nothing else your data type, `long`, will overflow at some point. – Sean Apr 27 '16 at 14:34

score 1 · Answer 2 · answered Apr 27 '16 at 14:26

This calculates fibonacci memorizing 2 numbers

private static BigDecimal fibonacci(int n) {

        BigDecimal cur = new BigDecimal(1);
        BigDecimal prev = new BigDecimal(0);

        //System.out.println(0+") "+1);

        for (int i=1; i<n; i++) {
            final BigDecimal next = cur.add(prev);
            prev = cur;
            cur = next;
            //System.out.println(i+") "+next);
        }

        return cur;
    }

score 0 · Answer 3 · answered Apr 27 '16 at 14:26

0

The following is functionally the same as your code, just without the recursive call; as such, it will run indefinitely without a StackOverflowError:

  private static void fibonacci(long first, long second, long sum) {
    while(true) {
      long number = first + second;       
      if (number % 2 == 0){ //Checks for even number
        sum = sum + number;
      }
      System.out.println(sum);

      first = second;
      second = number;
    }
  }

However, as noted by others, it will run literally indefinitely, as there is nothing to break the loop.

answered Apr 27 '16 at 14:26

Andy Turner

137,514
11
162
243

Except it will soonreach a number too big to fit in a long. – FredK Apr 27 '16 at 14:27
1

@FredK at which time it will silently overflow and carry on. – Andy Turner Apr 27 '16 at 14:27
Thanks, I'll give this a go – Hiphop03199 Apr 27 '16 at 14:35

score 0 · Answer 4 · edited May 23 '17 at 12:31

0

You have two alternatives:

either use an iterative version of your algorithm, for example something like this
or increase your stack size when running Java, more details

edited May 23 '17 at 12:31

Community

1
1

answered Apr 27 '16 at 14:27

slayful

31
3

Avoiding stack overflow error for Fibonacci sequence

4 Answers4