c++ - c ++ segfaulting中的斐波那契扩展

Question

我正在尝试将扩展添加到斐波那契数字以考虑负指数。扩展名是 Fib(-n) = (-n)^(n+1) * Fib(n) 我试图在 c++ 中实现它，但我遇到了一个问题，我不知道如何解决它。

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


int fib(int n) {
    if ( n < 0 ){ 
        return ( pow(-1,-n+1 ) * fib(-n) );
    }else if (n == 0){
        return 1;
    }else{
        return fib(n-1) + fib(n-2);
    }
}


int main(void){
    std::cout << "fib("<< -2<<") = " << fib(-2) << std::endl;
    return 0;
}

这给了我一个段错误，知道为什么会这样吗？

编辑：我想出了问题所在。忘记了基本情况，这会导致无限递归，进而导致段错误。

Answer 1

我想当你打电话给fib(-2)它的时候fib(2)

fib(2)通话fib(1)和fib(0)

fib(1)通话fib(0)和fib(-1)

fib(-1)电话fib(1)，这是永无止境的循环

Answer 2

According to your extension, shouldn't this be:
int fib(int n) { 
    if ( n < 0 ){  
        return ( pow(-1,n+1 ) * fib(n) ); // <<<
    }else if (n == 0){ 
        return 1; 
    }else{ 
        return fib(n-1) + fib(n-2); 
    } 
} 

Answer 3

这将导致无限递归。您需要两个终止案例，而不是一个。

举个例子fib(1)。这将调用fib(0)and fib(-1)。fib(0)将终止，但会无限fib(-1)调用fib(-1)`。fib(1), which will then again call

n==0解决方案：如果或终止递归n==1。

旁注：fib(0)通常定义为 0，而不是 1。

Answer 4

糟糕，我犯了一个愚蠢的错误，忘记了 n== -1 基本情况。它应该是：

int fib(int n) {
    if( n == -1){
        return 1;
    }else if ( n < 0 ){ 
        return ( pow(-1,-n+1 ) * fib(-n) );
    }else if (n == 0){
        return 1;
    }else{
        return fib(n-1) + fib(n-2);
    }
}

现在一切都按预期工作。