Я новичок в python, и у меня возникают проблемы с созданием рекурсивной функции, которая проверяет, является ли заданное число числом Фибоначчи.
Это мой код.
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
Он должен печатать True в обоих случаях, но вместо этого он печатает True и False, и я не могу найти, что не так.
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]]))
Первая часть вашей функции — это оператор if
. Если True
, он возвращает значение, если False
, он также возвращает значение. Таким образом, вторая часть вашей функции не может быть выполнена, и функция не является рекурсивной (поскольку вы не вызываете функцию снова ни в одном операторе return
).
Проверьте свою функцию. Иногда вы возвращаете число, иногда вы возвращаете True
, а иногда вы возвращаете None
.
Первая часть вашей функции — это оператор if
. Если True
, он возвращает значение, если False
, он также возвращает значение. Таким образом, вторая часть вашей функции не может быть выполнена, и функция не является рекурсивной (поскольку вы не вызываете функцию снова ни в одном операторе return
).
В более общем случае то, что вы делаете, никогда не сработает. Логика выглядит так: «Число Фибоначчи — это сумма предыдущего числа Фибоначчи и числа перед ним, поэтому я могу изменить эту логику, вычислив n - 1
и n - 2
, и если они числа Фибоначчи, то и n
» — или что-то в этом роде. как это.
Но это не работает: 5 — число Фибоначчи, а (5-1) — нет, так что логика тут же ломается. Если вы думаете, что числом Фибоначчи должна быть только сумма: 13 — это число Фибоначчи, но (13-1) + (13-2) = 23, а это тоже не число Фибоначчи.
Простой способ решить эту проблему — просто сгенерировать последовательность Фибоначчи и вернуть True
, как только выпадет число, которое вы проверяете:
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))
Подсказка: что возвращает isFib(13)?