C ++ Рекурсивная функция Фебоначи

Question

C ++ Рекурсивная функция Фебоначи

Ниже мой код. Я попытался напечатать рекурсивную функцию Фибоначчи [в самом конце], но это дало мне ошибку сегмента. Что не так с моим кодом? Я потратил около 3 часов на это и не мог понять это. Может ли кто-то быть добрым, чтобы помочь мне? Спасибо

int fibonacci (int x) {if (x == 0) {
return 0;
}
else if (x == 1) {
return 1;
}
else {
return (fibonacci(x-1) + fibonacci (x + 2));
}
}

0

c++fibonacci function recursion segment

Решение

Другие решения

В настоящее время рекурсия никогда не заканчивается, потому что:

return (fibonacci(x-1) + fibonacci (x + 2));

должно быть

return (fibonacci(x-1) + fibonacci (x - 2));

Текущий код приводит к тому, что стеку не хватает памяти, потому что вы продолжаете добавлять вызовы функций бесконечно, и в тот момент, когда стеку не хватает памяти, вы получаете сбой. Вы можете увидеть, что происходит, когда вы проследите за ходом выполнения с номером образца:

fibonnaci(2) = fibonacci(1)+fibonacci(4)
= 1 + (fibonacci(3)+fibonacci(6))
= 1 + (((fibonacci(2)+fibonacci(5))+(fibonacci(5)+fibonacci(8)))
= 1 + .......

Как вы можете видеть, это никогда не заканчивается.

1

Источник

Accepted Answer

Скорее всего, вы получаете segfault, потому что ваш стек растет без контроля, и это из-за этой строки:

    return (fibonacci(x-1) + fibonacci (x + 2));

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

Итак, перепишите эту строку так:

    return (fibonacci(x-1) + fibonacci (x - 2));

4