Recursive function to check if a given number is Fibonacci-CodePudding

I'm new to python and I'm am having problems building a recursive function that checks if a given number is a Fibonacci number.

This is my code.

def isFib(n):
    if n <= 1:
        return n
    else:
        return (n - 1)   (n - 2)
    
    if isFib(n) == 1 or isFib(n) == isFib(n - 1)   isFib(n - 2):
        return True

It should print True in both cases, but instead it print True and False, and I can't find what's wrong

print(all([isFib(i) for i in [1,2,3,5,8,13,21,34,55]]))
print(all([not isFib(2*i) for i in [1,2,3,5,8,13,21,34,55]]))

CodePudding user response：

The first part of your function is an if statement. If True, it returns a value - if False, it also returns a value. So, the second part of your function cannot possible execute, and the function isn't recursive (since you don't call the function again in either return statement).

More generally, what you're doing will never work. The logic seems to be: "a Fibonacci number is the sum of the previous Fibonacci number and the number before that, so I can reverse that logic by computing n - 1 and n - 2 and if they are Fibonacci numbers, then so is n" - or something like that.

But that doesn't work: 5 is a Fibonacci number, but (5-1) is not, so the logic breaks right there. If you were thinking only the sum needed to be a Fibonacci number: 13 is a Fibonacci number, but (13-1) (13-2) = 23 and that's not a Fibonacci number either.

An easy way to solve this would be to just generate a Fibonacci sequence and return True as soon as the number you're checking comes up:

def is_fib(n, seq=None):
    if seq is None:
        seq = [0, 1]
    # n is Fibonacci if the last number in the sequence is
    # or if the last number has not yet past n, then compute the next and try again
    return n == seq[-1] or (seq[-1] < n and is_fib(n, seq   [seq[-2]   seq[-1]]))


print([is_fib(i) for i in [1,2,3,5,8,13,21,34,55]])
print(is_fib(23))