Рекурсивная функция для проверки, является ли заданное число Фибоначчи

Я новичок в 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]]))

Подсказка: что возвращает isFib(13)?

user253751 18.11.2022 22:01

Первая часть вашей функции — это оператор if. Если True, он возвращает значение, если False, он также возвращает значение. Таким образом, вторая часть вашей функции не может быть выполнена, и функция не является рекурсивной (поскольку вы не вызываете функцию снова ни в одном операторе return).

Grismar 18.11.2022 22:03

Проверьте свою функцию. Иногда вы возвращаете число, иногда вы возвращаете True, а иногда вы возвращаете None.

Woodford 18.11.2022 22:11
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
1
3
88
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Первая часть вашей функции — это оператор 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))

Другие вопросы по теме