Последовательность Фибоначчи дает ошибку сегментации на счет 50-го числа в C

Question

Предполагается, что моя программа посчитает x-ю строку последовательности Фибоначчи, если переданный в выполнении x меньше 50, он работает нормально, но с 50 и выше я получаю ошибку сегментации.

Здесьмой код:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
uint64_t fibonnacci ( uint64_t n) {
    if (n < 2)
        return n;
    else {
        uint64_t * val;
        val = malloc ( sizeof ( uint64_t )*2);
        val [0] = fibonnacci (n -1);
        val [1] = fibonnacci (n -2);
        return val [0] + val [1];
    }
}
int main ( int argc , char * argv []) {
    printf ( " % llu \ n " ,fibonnacci ( atoi ( argv [1])));
    return 0;
}

Answer 1

Моя компиляция падает на Fibonacci 39.

Если я добавлю счетчик вызовов в рекурсивную функцию, Fibonacci 38 вызовет рекурсивную функцию 126491971 раз.

Вы не free памяти, и вы не проверяете возвращаемое значение из malloc.Таким образом, в какой-то момент вы можете исчерпать память, в зависимости от реализации.

Когда я использую кодовое предложение @RedaMeskali, я могу запустить Fibonacci 50, хотя запуск занимает не менее одной минуты.

Фибоначчи может быть полезным упражнением для изучения рекурсии, но очень неэффективно.В простом цикле Fibonacci 50 можно вычислить в три раза .

Answer 2

Ошибка сегментации обычно означает, что вы пытаетесь получить доступ к нулевому указателю.

Вычисление последовательности Фибоначчи 50 приводит к миллионам рекурсивных вызовов, и каждый раз, когда вы выделяете 16 байтов для val, но вы никогдаосвободите эту память, когда закончите.В конце концов вы используете всю свою память.malloc не может выделить больше для вас, поэтому он возвращает NULL.Когда вы пытаетесь сохранить что-либо в памяти с адресом NULL, вы получаете ошибку сегментации.

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