Fibonacci extension dans C++ segfaulting

Question

J'essaye d'ajouter l'extension aux nombres de Fibonacci pour prendre en compte des index négatifs. L'extension est Fib (-n) = (-n)^(n + 1) * Fib (n) J'ai essayé d'implémenter ceci en C++ mais je suis confronté à un problème et je ne suis pas sûr de savoir comment contourner.

#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; 
} 

Cela me donne un segfault, une idée de pourquoi c'est?

EDIT: J'ai trouvé quel est le problème. J'ai oublié un cas de base et cela a provoqué une récursion infinie, qui à son tour a provoqué une erreur de segmentation.

Answer 1

Je suppose que quand u appeler fib(-2) appelle fib(2)

fib(2) appels fib(1) et fib(0)

fib(1) appels fib(0) et fib(-1)

fib(-1) appels fib(1) et c'est la boucle sans fin

Answer 2

Cela provoquera des répétitions infinies ion. Vous avez besoin de deux cas de terminaison, pas un.

Prenez par exemple fib(1). Cela appellera fib(0) et fib(-1). fib(0) se terminera, mais fib(-1) appellera fib(1), which will then again call fib (-1) `ad infinitum.

Solution: Terminez la récursivité si n==0 ou n==1.

Sidenote: fib(0) est habituellement défini comme 0, pas 1.

Answer 3

Oops I a fait une erreur stupide oublier le n == -1 cas de base. Il devrait être:

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); 
    } 
} 

Maintenant tout fonctionne comme prévu.

Answer 4

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); 
    } 
}