Stack overflow Фибоначчи

Question

стоит задача вычислить n число Фибоначчи. Вроде все работает, но на числах больше 1000(на глаз :) программа прерывается из-за Stack overflow. Кто может подсказать причину данного проишествия? Мне не хватает вместительности переменной? Или же есть какой-то иной путь решения задачи(точнее записи промежуточных значений)

#include <iostream>
#include <math.h>

using namespace std;
long fibo(int n)
{
    if (n<=2)
    {
        return 1;
    }
    else
    {
        return fibo(n - 1) + fibo(n - 2);
    }
}

int main()
{
    int n;
    cin >> n ;
    cout << fibo(n);    
}

Answer 1

Вы вызываете метод fibo рекурсией. Если посмотрите в стек вызовов то увидите что каждый вызов этого метода создаёт ещё несколько рекурсий этого же метода вот здесь

return fibo(n - 1) + fibo(n - 2);

Неплохая статья для примера возможного решения. https://habr.com/ru/post/261159/ Я бы использовал цикл внутри метода.

Answer 2

Код ниже, он будет работать с небольшими числами, если пишет "stack overflow" то это скорее памяти не хватает для записи числа.

int fibonacci_number(int pos)
{
    if (pos < 2)
        return pos;
    return fibonacci_number(pos - 1) + fibonacci_number(pos - 2);
}

Что б выделить больше памяти, следует писать так:

long long fibonacci_number_fast(long long pos, long long a = 0, long long b = 1)
{
    if (pos == 0)
        return a;
    return fibonacci_number_fast(pos - 1, b, a + b);
}

Вторая функция будет очень быстро обрабатывать большие числа.

БЛОГ НА HUSL

Stack overflow Фибоначчи

Ответы (2 шт):