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

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

Ссылка

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

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