递归函数中的分段错误

Question

我最近第一次阅读了关于memoization的内容(我是一个菜鸟),我想尝试创建一个使用memoization的fibonacci函数.这是我尝试过的,但超过1的任何东西只会给我一个分段错误.任何帮助表示赞赏!

unsigned int fibonacci( unsigned int n )
{
    vector<unsigned int> fibvector;
    if ( n <= 1 )
        return n;
    if ( fibvector.size() >= n )
        return fibvector[n];
    unsigned int add = fibonacci( n-1 ) + fibonacci( n-2 );
    fibvector[n] = add;
    return add;
}

Answer 1

vector<unsigned int> fibvector; 

是一个局部变量.每次调用fibonacci(n)时都会创建一个没有元素的新矢量.您可以通过将其设置为静态来修复它.

static vector<unsigned int> fibvector(MAXELEMENTS); 

MAXELEMENTS用于初始化目的.在这种情况下,您需要使用测试

if(fibvector[n] != 0) return fibvector[n];

编辑:如果您不需要固定数量的元素,可以使用以下内容

unsigned int fibonacci( unsigned int n )
{
    static vector<unsigned int> fibvector;
    unsigned int fib;

    if ( fibvector.size() > n )
        return fibvector[n];
    if(n <=1){
       fib = n;
    }
    else{
       unsigned int v2 = fibonacci( n-2 );
       unsigned int v1 = fibonacci( n-1 );
       fib = v2 + v1;
    }
    fibvector.push_back(fib);
    return fib;
}

这个想法是斐波纳契(n)的递归方法首先计算斐波那契(0),斐波那契(1),斐波那契(2)直到斐波那契(n).这意味着它将按照n的自然顺序进行计算,push_back将准确地遵循此顺序.