fibonacci sequence using recursion with negative numbers python

Question

I'm trying to write a program that finds the fibonacci sequence of any given number using the formula: F_-n = (-1)ⁿ⁺¹F_n

I have written the code for the positive side, which works, but I am getting nonstop recursion when I enter a negative number.

def fib(n):
    if n > -1:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            return fib(n-1) + fib(n-2)
    if n <= -1:
        return ((-1)**(n+1)) + fib(n)


num = eval(input("enter a number: "))
print("The value of the fibonacci series for the number", num, "is: ", fib(num))

Answer 1

For the negative side, your last clause, you have to call fib(-n), the absolute value of n.

if n <= -1:
    return ((-1)**(n+1)) + fib(-n)   # Note the negation; abs(n) would also work.

If you insist on calculating it directly, you need to maintain the relation:

f(n) = f(n-1) + f(n-2)

To solve this for the least number:

f(n-2) = f(n) - f(n-1)

... and then normalize for the current negative value: let j = n-2:

f(j) = f(j+2) - f(j+1)

Can you handle the variations from there?

Answer 2

The if n <= -1: part of your implementation is not correct, if you look at the wikipedia article, it shows the negative generalization as a multiplication, not an addition:

return((-1)**n+1) * f(-n))

I've taken into account the correction from @prune, this should work in python. I've tested it in R and the output matches the sequence given in the Wikipedia article.

Answer 3

The return statement ((-1)**(n+1)) + fib(n) is not correct as per the equation mentioned by you

F(-n) = ((-1)^n+1)*F(n)

The computer can't differentiate between '-' sign and a number, it evaluates a negative number(eg.-3) as a whole literal(number). In the equation, we are finding the value for F(n) but in your return statement, you are finding the solution for F(-n).

For Instance, if you take the n=-3,

F(-3) = ((-1)^(-3+1))*F(-3) =>(-1)*F(-3) //This is according to your return statement, the system can't evaluate F(-3) in RHS.

The correct form will be, F(-3) = ((-1)^(-3+1))*F(-(-3)) =>(-1)*F(3) //So, you have to negate the value for F(-3) in RHS before recursion.

So the corrected statement is,((-1)**(n+1)) + fib(-n)

Note: RHS(Right Hand Side), Negate(Making a number negative by multiplying it with -1)

Answer 4

The following Fibonacci code is using iteration. the argument n is any integer (positive or negative). It produces exactly the same result as F_-n = (-1)ⁿ⁺¹F_n

def fibo(n):
    if n>=0:
       idx = range(n+1)
       x = [0,1]
       for k in idx[2:]:
           x.append(x[k-1] + x[k-2]) 
       return x[n]
    else:
       n=-(n-1)
       idx = range(n+1)
       x = [1,0]
       for k in idx[2:]:
           x.append(x[k-2] - x[k-1]) 
       x.reverse()
    return x[0]

for i in range(-13,14):
   print(i,fibo(i))

It would produce

-13 233
-12 -144
-11 89
-10 -55
-9 34
-8 -21
-7 13
-6 -8
-5 5
-4 -3
-3 2
-2 -1
-1 1
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233