c - 带缓存的递归斐波那契计算 - 找不到错误

Question

我写了一个简单的函数来计算斐波那契数，但它进入了无限循环并崩溃了。我似乎无法在这里找到问题所在。

#include <stdio.h>

int fib(int number, int *cache);

int main(int argc, char *argv[])
{
    int cache[20] = {0};
    int result = fib (3, cache);
    printf("%d ", result);
}

int fib(int number, int *cache)
{
    if (number == 0) return 0;
    if (number == 1) return 1;

    if (cache[number] != 0) return cache[number];

    int result = fib(number - 1, cache) + (number - 2, cache);
    cache[number] = result;
    return result;
}

Answer 1

此行包含错误

int result = fib(number - 1, cache) + (number - 2, cache);

fib不见了。它应该是

int result = fib(number - 1, cache) + fib(number - 2, cache);

Answer 2

除了@MOHAMED 的回答，您只需初始化cache[0]，其他元素可以包含任意垃圾（访问它们确实是未定义的行为）。按预期工作;-)