Комментарии 14
Пример с Фибоначи очень узок. Редко кому надо проводить рекурсивные математические операции. Для этого есть разнообразные чилодробительные библиотеки, которые работают ещё быстрее.
А если мы перейдем от чисел к строкам или структурам, то потери на работу с этими объектами в памяти изменят ситуацию, и скорость уже не будет в тысячу раз быстрее.
В реальной жизни рекурсию используют для банального обхода дерева или других ациклических структур. И хотя тут тоже можно использовать замыкание, но читабельность может упасть критически.
я молчу о том что рекурсивные функции и так плохо читаются и понимаются, а вы сделали код который вообще стал 3 раза вложенным сам в себя и читебельность упала еще ниже.
давайте реальные примеры. постройте дерево диска например, разберите DOM дерево с сайта. короче что то что на практике нужно. если вы проводили эти тесты — то значит для каких то целей? цель была написать статью? или вы делали какой то проект и рекурсия проиграла? так покажите код проекта, объясните почему в вашем примере оно выгоднее по памяти, времени и т.п. а то как в примере с деревом диска — да плевать с какой скоростью рекурсия идёт, ваш диск будет бутылочным горлышком и сканирование займёт 20 минут, и к которым добавится 0,2 секунды что скушает рекурсия… по вашему же примеру будет 20 минут и 0,0002 секунды… выигрыш очевиден!!!
Статью с таким же успехом можно было бы назвать «Избегайте рекурсии и замыкания в Python: вспомните о генераторах»
def fibonacci(n):
fib1, fib2 = 0, 1
for _ in range(n):
fib1, fib2 = fib2, fib1 + fib2
yield fib1
Но, думаю, всем понятно, что есть смысл использовать все инструменты которые даёт язык, всё зависит от конечной задачи, а не результата какого-то скрупулёзно выбранного синтетичного теста. И каждый из подходов будет иметь преимущества и недостатки в разных ситуациях.
Чтобы получить схожий результат, нужно вызывать композицию его с next(), как-то так:
def fibonacci():
fib1, fib2 = 0, 1
while True:
fib1, fib2 = fib2, fib1 + fib2
yield fib1
f = fibonacci()
for _ in range(10):
print(next(f))
Почему Фибоначчи с замыканиями код производительный, а рекурсивный вычисляет n-2 число по сути два раза? Без мемоизации там же в дичайшее дерево разворачивается все с плачевной производительностью… И тут не проблема рекурсивных вызовов, а проблема их использования именно в таком исполнении.
Вот еще вариант на классах.
class Fib:
def __init__(self):
self._x1 = 0
self._x2 = 1
def __call__(self):
x3 = self._x1 + self._x2
self._x1, self._x2 = self._x2, x3
return x3
А если __call__
переименовать в __next__
то будет вообще хорошо. Без генераторов это исследование выглядит неполным.
Может автор исходной статьи и понимает в Питоне, но точно слаб в рекурсии.
А вы точно программист?
В статье последовательно используются практики, которых следует избегать: числа Фибоначчи – это классический пример задачи, которую не надо решать рекурсией (разве что у вас в языке других механизмов нет вообще), модификация "лямбдой" переменной во внешней функции…
И, раз уж зашла речь о рекурсивной реализации итеративных алгоритмов – хотелось бы увидеть упоминание хвостовой рекурсии.
Просто оставлю это здесь (наивная рекурсия на python для Фибоначчи, накатал на скорую руку, извиняйте если что, файл fibonacci.py):
#!/bin/env python3
import timeit
def _fib(i):
if i == 0:
return (0, 1)
if i == 1:
return (1, 1)
i_fib = _fib(i - 1)
return (i_fib[1], i_fib[0] + i_fib[1])
def fib(i):
return _fib(i)[1]
python -m timeit 'import fibonacci; fibonacci.fib(20)'
100000 loops, best of 3: 2.54 usec per loop
Понятно, что может характеристики машины не те, но что-то сомневаюсь, что время будет сильно варьироваться.
Интуитивно понятно: причина в том, что все временные значения для каждого уровня рекурсии хранятся в памяти отдельно, тогда как замыкание каждый раз обновляет одни и те же переменные.
Автору нельзя доверять своей интуиции. В алгоритме "с замыканиями" у него очевидно линейная сложность, хотя при чём тут замыкания, это обычный итеративный алгоритм. А в рекурсивном сложность пропорциональна числу Фибоначчи, т.е. экспоненциальная, О(φ^n). Непонятно чего автор кандидат, надеюсь не compsci, но анализу сложности рекурсивных алгоритмов я учу первокурсников. Причём написать линейный рекурсивный алгоритм для Фибоначчи совсем даже не сложно, он абсолютно такой же как итеративный (потому что хвостовая рекурсия)
Избегайте рекурсии в Python: вспомните о замыкании