Ряд фибоначчи рекурсия python

Мемоизация, рекурсия и цикл for в Python

В этой статье мы подробно разберем, как создать последовательность Фибоначчи. Решение данной задачи мы покажем с использованием трех разных методов. Рассмотрим мемоизацию, рекурсию и цикл for в Python.

Как вы, вероятно, знаете, последовательность Фибоначчи образуется следующим образом. Мы складываем первое и второе число, 0 и 1, чтобы получить третье число в последовательности (0 + 1 = 1). Затем мы складываем второе и третье число, чтобы получить 4-е число в последовательности (1 + 1 = 2). И так проделываем для каждого последующего числа Фибоначчи.

Код, который мы будем рассматривать, вы можете писать в Jupyter, Colab или любой IDE или текстовом редакторе, который вам удобен.

Вычисление n-го члена последовательности Фибоначчи с помощью цикла for

Напишем базовую программу, используя цикл for . Логика последовательности проста, мы уже обсудили ее выше.

Временная сложность решения с помощью цикла for — O(n), а пространственная сложность – O(1) или константа. Правда, на самом деле все несколько сложнее.

«Если ваше число меньше, чем 94, и вы используете 64-битное число, тогда алгоритм ведет себя, как имеющий линейную сложность. Но для N > 94 он начинает вести себя, как алгоритм с квадратичной сложностью», — из ответа Майкла Векслера на сайте Quora.

def fib_for(n): n1 = 0 n2 = 1 if n 
Запустим этот код с помощью модуля Python %timeit . Это позволит замерить время выполнения, избежав ряда распространенных ловушек.

Для того, чтобы высчитать 10-е число Фибоначчи, потребовалось по 675 наносекунд на каждую итерацию цикла.

Вычисление n-го члена последовательности Фибоначчи с помощью рекурсии
Теперь давайте реализуем последовательность Фибоначчи с помощью рекурсии. Рекурсивные функции вызывают себя повторно, пока не достигнут базового случая. Таким образом, рекурсия создает древовидную структуру.
Если мы возьмем первые 5 чисел Фибоначчи, то в результате рекурсии получится вот такое дерево.

Пространственная сложность в данном случае — O(n), а временная сложность — O(2 n ). Так происходит, потому что у корневого узла есть 2 дочерних узла (fib(4) и fib(3)) и 4 внука. И, как видите, у каждого узла есть 2 дочерних элемента. Кроме того, вы могли заметить, что правое поддерево меньше, чем левое. Так что, на самом деле время выполнения составляет примерно O(1,6 n ).
Базовый случай: Fibonacci(2) = Fib(1) + Fib(0) = 1 + 0 = 1
Вычисление n-го члена последовательности Фибоначчи при помощи рекурсии определенно быстрее, чем с помощью цикла for.

Вычисление n-го члена последовательности Фибоначчи с использованием мемоизации
Мемоизация – это метод, который может значительно улучшить производительность рекурсивной функции за счет уменьшения вычислительных затрат. Он сохраняет результаты дорогостоящих вызовов функций в массиве или словаре и при вызове с такими же входными данными возвращает кэшированные результаты.
Давайте ещё раз посмотрим на приведенное выше дерево. Легко заметить, что некоторые входные данные пересчитываются при каждом обращении к ним.
def Fib_memoisation(n, memo): if n 
Временная сложность — O(n * log10n).

Что лучше: рекурсия, цикл for или мемоизация?
Нельзя сказать, что какая-то из этих техник однозначно лучше других. Вам просто нужно знать, в каких случаях какая из них будет наиболее подходящей и эффективной. Это, конечно же, зависит от ваших требований.
Итерация с помощью цикла for будет быстрее, чем рекурсия, потому что рекурсия должна иметь дело с фреймом рекурсивного стека вызовов. Однако, если рекурсия написана на языке, который оптимизирует «хвостовой» вызов, это устраняет излишние расходы, и тогда рекурсия сравнима с циклом for .
Наконец, мемоизация лучше, когда нужно иметь дело только с некоторыми более мелкими подзадачами, а не решать их все.
Таким образом, каждый из разобранных нами в этой статье методов по-своему хорош. Стоит помнить о существовании и особенностях каждого из них и выбирать наиболее оптимальный под вашу задачу.
Источник
Рекурсивный метод нахождения чисел Фибоначчи
Программа принимает на вход число членов последовательности Фибоначчи и при помощи рекурсии вычисляет все числа, входящие в эту последовательность.
Решение задачи

  
Принимаем на вход число членов последовательности и записываем его в отдельную переменную.
  
Это число передается в качестве аргумента в рекурсивную функцию, которая будет вычислять n -й член последовательности.
  
В качестве базового условия принимаем то обстоятельство, что число членов последовательности Фибоначчи не может быть меньше единицы либо равно ей. При наступление этого условия рекурсия останавливается.
  
В противном случае функция вызывается вновь следующим образом: в качестве аргумента нашей рекурсивной функции передается введенное число, уменьшенное на единицу, и к этому прибавляется эта же функция с аргументом, уменьшенным уже на 2.
  
Каждый вызов функции возвращает одно число, которое мы потом выводим на экран.

Исходный код
Ниже дан исходный код, который осуществляет вывод всех членов последовательности Фибоначчи заданного размера. Результаты работы программы также даны ниже.
Объяснение работы программы

  
Пользователь вводит число и оно записывается в переменную n .
  
Передаем число n в качестве аргумента в рекурсивную функцию, которая вычисляет n-ый член последовательности.
  
Так как первый член последовательности Фибоначчи по определению не может быть меньше 1, в качестве базового условия принимаем n 
  
В противном случае функция вызывается вновь следующим образом: fibonacci(n-1) + fibonacci(n-2) .
  
Результаты выводятся на экран при помощи цикла for .

Результаты работы программы
Пример 1: Введите число членов последовательности:5 Последовательность Фибоначчи: 0 1 1 2 3 Пример 2: Введите число членов последовательности:7 Последовательность Фибоначчи: 0 1 1 2 3 5 8
 
Примечания переводчика
 
Данный пример приведен только с целью подробного ознакомления с алгоритмами рекурсии. Как вы можете заметить, данный код крайне неэффективен и не экономичен с вычислительной точки зрения, поскольку для вычисления n-го члена последовательности нам необходимо вычислять все предыдущие. И так мы делаем ровно n раз. Когда числа n являются большими, данный код абсолютно не применим. И, разумеется, для решения этой задачи есть другие, более эффективные, алгоритмы.
 
Источник
 
Числа Фибоначчи на Python
 
 
Статьи
 
Введение
 
В статье разберём 3 способа получения ряда Фибоначчи на Python. Первые два способа будут с использованием циклов, а третий – рекурсивный.
 
Числа Фибоначчи – бесконечная последовательность чисел, каждое из которых является суммой двух предыдущих и так до бесконечности.
 
 
Числа Фибоначчи циклом while
 
Для начала создадим переменную, в которую будет вводиться длина ряда:
 
n = int(input('Введите длину ряда: '))
 
Далее создадим две переменные (f1 и f2), которые будут равняться начальным единицам и выведем их:
 
Создадим переменную i, которая будет равняться двум:
 
Добавим цикл, который не закончится, пока переменная i будет меньше переменной n:
 
Числа Фибоначчи на Python:
 
n = int(input('Введите длину ряда: ')) f1 = f2 = 1 print(f1, f2, end=' ') i = 2 while i < n: f1, f2 = f2, f1 + f2 # f1 приравнивается к f2, f2 приравнивается к f1 + f2 print(f2, end=' ') # Выводится f2 i += 1 print()
 
Числа Фибоначчи циклом for
 
Создадим переменную, в которую будет вводиться длина ряда:
 
n = int(input('Введите длину ряда: '))
 
Далее создадим две переменные (f1 и f2), которые будут равняться начальным единицам и выведем их:
 
Добавим цикл, который начинается с 2, и заканчивается на n:
 
for i in range(2, n): f1, f2 = f2, f1 + f2 # f1 приравнивается к f2, f2 приравнивается к f1 + f2 print(f2, end=' ') # Выводится f2
 
Числа Фибоначчи на Python:
 
n = int(input('Введите длину ряда: ')) f1 = f2 = 1 print(f1, f2, end=' ') for i in range(2, n): f1, f2 = f2, f1 + f2 print(f2, end=' ')
 
Числа Фибоначчи рекурсией
 
Для начала создадим рекурсивную функцию, назовём её fibonacci и добавим ей параметр n:
 
Добавим условие, что если n = 1, или n = 2, то возвращается единица, так как первый и второй элементы ряда Фибоначчи равны единице. Если же условие не срабатывает, то элементы складываются:
 
def fibonacci(n): if n == 1 or n == 2: # Если n = 1, или n = 2, вернуть в вызывающую ветку единицу, так как первый и второй элементы ряда Фибоначчи равны единице. return 1 return fibonacci(n - 1) + fibonacci(n - 2)
 
Числа Фибоначчи на Python:
 
def fibonacci(n): if n == 1 or n == 2: return 1 return fibonacci(n - 1) + fibonacci(n - 2) n = int(input()) print(fibonacci(n))
 
Заключение
 
В данной статье мы научились вычислять n-ное число ряда Фибоначчи на Python. Надеюсь Вам понравилась статья, удачи! 🙂
 
Источник
 
Читайте также:  Python str replace regexp