Fibonacci extension in c++ segfaulting

Question

I'm trying to add the extension to the Fibonacci numbers to take into account negative indexes. The extension is Fib(-n) = (-n)^(n+1) * Fib(n) I have attempted to implement this in c++ but I'm running into a problem and I'm not sure how to get around it.

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

This gives me a segfault, any idea why this is?

EDIT: I figured out what the problem is. Forgot a base case and this caused an infinite recursion, which in turn caused a segfault.

Answer 1

I guess that when u call fib(-2) it calls fib(2)

fib(2) calls fib(1) and fib(0)

fib(1) calls fib(0) and fib(-1)

fib(-1) calls fib(1) and this is never-ending loop

Answer 2

This will cause infinite recursion. You need two terminating cases, not one.

Take for example fib(1). This will call fib(0) and fib(-1). fib(0) will terminate, but fib(-1) will call fib(1), which will then again callfib(-1)` ad infinitum.

Solution: Terminate the recursion if n==0 or n==1.

Sidenote: fib(0) is usually defined as 0, not 1.

Answer 3

Oops I made a stupid mistake forgetting the n== -1 base case. It should be:

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

Now everything works as expected.

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