Fibonacci extension in c++ segfaulting [closed]

Closed. This question is not reproducible or was caused by typos. It is not currently accepting answers.

---

This question was caused by a typo or a problem that can no longer be reproduced. While similar questions may be on-topic here, this one was resolved in a way less likely to help future readers.

Closed 8 years ago.

Improve this 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);
  开发者_如何学Python  }
}


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.

---

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

---

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.

---

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.

---

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