последовательность Фибоначчи с помощью рекурсии с отрицательными числами Python

Question

Я пытаюсь написать программу, которая находит последовательность Фибоначчи любого заданного числа, используя формулу: F _-n = (-1) ^{п + 1} Р _n

Я написал код для положительной стороны, который работает, но я получаю безостановочную рекурсию при вводе отрицательного числа.

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

Для отрицательной стороны, ваш последний пункт, вы должны вызвать выдумку (-n), абсолютное значение п.

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

Если вы настаиваете на его расчета напрямую, вам необходимо поддерживать соотношение:

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

Чтобы решить эту проблему для числа минимум:

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

... и затем нормализовать для текущего отрицательного значения: пусть j = n-2:

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

Можете ли вы отрегулировать варианты оттуда?