почему эта запомненная факторная функция возвращает неправильный ответ!

Question

Я запомнил факториальную функцию в C следующим образом:

int fact(int n)
{
int temp;
int lookup_table[n];
if(lookup_table[n])
    return lookup_table[n]; 
else{
    if(n == 0 || n == 1)
        return 1;
    else
        temp = n * fact(n-1);
        lookup_table[n] = temp;
        return temp;
    }
}

Но тогда, когда я введу n = 5, он выдаст
-1! = 134514064
Может кто-нибудь объяснить, что происходит?

Answer 1

Ваш массив lookup_table объявлен локально; это отличается в каждом вызове; ничего не запоминается.

Answer 2

хорошо, сразу же, если (lookup_table [n]) будет на один элемент больше длины lookup_table []. В C массивы имеют индексирование на основе 0.

Тогда есть проблема, что вы объявляете таблицу поиска как автоматическую (стековую) переменную в рекурсивной функции, которая должна ее заполнять. Она должна быть объявлена ​​вне функции в глобальной области / области модуля.

Answer 3

Этот int lookup_table[n]; объявляет массив из n int с именем lookup_table.поскольку допустимый индекс для этого массива - 0..n-1, lookup_table [n] находится вне массива и будет вызывать неопределенное поведение.Полагаю, вы хотели написать: int somevariable = lookup_table[n]; и использовать эту переменную для сравнения или вообще удалить эту строку.

В любом случае, обязательно проверяйте границы при доступе к этому массиву.

Answer 4

Заменить

int lookup_table[n];

с

static int lookup_table[13];

Это сделает тот же массив доступным в рекурсивных вызовах функций и даст вам достаточно места для хранения всех факторных значений, которые может поддерживать диапазон int.

Было бы неплохо проверить, что входное значение равно 12 или меньше, чтобы вы не столкнулись с неопределенным поведением.

Answer 5

int lookup_table[n] должен быть помечен как статический (на самом деле это не может, вам нужна константа, но она не должна быть слишком большой, так как факториалы растут очень быстро), но это не совсем то, почему вы ошибаетесь ответ. Вместо этого lookup_table инициализируется для неопределенного мусора вместо 0.

Однако, нет никаких оснований инициализировать его нулем, когда вы делаете его статическим; это будет сделано автоматически.

О, и как уже отмечали другие, у вас есть ошибка за пределами границ, потому что вам нужно обменять int lookup_table[n] на использование константы вместо n.