Ошибка переполнения стека возникает при использовании функции рекурсивного фибоначчи

Question

Вот мой код, и он хорошо работает со значениями от 400 до 4000, но раз около 4 мил, я получаю ошибки переполнения стека.

Заранее благодарен!

public class Fib { 
static int c=1,b=2; 
static long sum1=0,sum2=0; 

static long fib(long a){ 
if(a==1){ 
    return 1; 
} 
if(a==2){ 
    return 2; 
} 
else{ 
    return fib(a-1)+fib(a-2); 
} 

    } 


    public static void main(String[] args){ 
sum2= fib(4000000); 
    System.out.println("Sum %f" +sum2); 
} 
    } 

Answer 1

Да - у вас закончилось пространство стека. Это далеко не бесконечно, и вы используете его для каждого рекурсивного вызова. Вы пытаетесь получить стек с 4 миллионами кадров стека - это не сработает.

Предлагаю вам рассмотреть итеративный подход. Даже если у вас было бесконечное количество стека, этот код, вероятно, не завершился до жары смерти Вселенной. (Подумайте о сложности этого кода ...)

Answer 2

Вы можете увеличить размер стека программ Java. Пример:

java -Xss4m YourProgram 

Reference

Тем не менее, я хотел бы также рекомендовать итерационный метод.

Answer 3

Как уже упоминалось выше, Джон Скит, ваш код потребует огромного количества времени для запуска - от 2 до 4 миллионов, что практически не является практическим. Честно говоря, я удивлен, что стек вообще высох, я думаю, что код просто запустится в течение смешного времени.

Вы должны использовать итеративный подход. Удобное определение последовательности ответов на примере фибоначчи:

static long fib(long i){ 
    if (i == 0 || i == 1) return 1; 
    long a = 1; //This is the 0th element 
    long b = 1; //This is the 1st element 
    while(i-- > 1){ //Each iteration, sets a and b to the next element in the fibonacci sequence 
     long temp = b; 
     a += b; 
     b = a; 
     a = temp; 
    } 
    return b; 
}