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

Я новичок в 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
Скраппинг поиска Apple App Store с помощью Python
Скраппинг поиска Apple App Store с помощью Python
📌Примечание: В этой статье я покажу вам, как скрапировать поиск Apple App Store и получить точно такой же результат, как на Apple iMac, потому что...
Редкие достижения на Github ✨
Редкие достижения на Github ✨
Редкая коллекция доступна в профиле на GitHub ✨
Мутабельность и переработка объектов в Python
Мутабельность и переработка объектов в Python
Объекты являются основной конструкцией любого языка ООП, и каждый язык определяет свой собственный синтаксис для их создания, обновления и...
Другой маршрут в Flask Python
Другой маршрут в Flask Python
Flask - это фреймворк, который поддерживает веб-приложения. В этой статье я покажу, как мы можем использовать @app .route в flask, чтобы иметь другую...
14 Задание: Типы данных и структуры данных Python для DevOps
14 Задание: Типы данных и структуры данных Python для DevOps
Проверить тип данных используемой переменной, мы можем просто написать: your_variable=100
Python PyPDF2 - запись метаданных PDF
Python PyPDF2 - запись метаданных PDF
Python скрипт, который будет записывать метаданные в PDF файл, для этого мы будем использовать PDF ридер из библиотеки PyPDF2 . PyPDF2 - это...
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))

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