Как стать автором
Обновить

Комментарии 14

Пример с Фибоначи очень узок. Редко кому надо проводить рекурсивные математические операции. Для этого есть разнообразные чилодробительные библиотеки, которые работают ещё быстрее.


А если мы перейдем от чисел к строкам или структурам, то потери на работу с этими объектами в памяти изменят ситуацию, и скорость уже не будет в тысячу раз быстрее.


В реальной жизни рекурсию используют для банального обхода дерева или других ациклических структур. И хотя тут тоже можно использовать замыкание, но читабельность может упасть критически.

Писать статьи про программирование на Python и не оформлять код отступами — очень помогает разобраться в примерах.

Писал статьи о питоне человек внятный — в оригинале с отступами все нормально.
Но гуглетранслейт питона не знает.
PS. жаль, что SkillFactory не делится исходниками хабра-бота, можно было бы поправить.

как всегда у всех подобных статей — примеры гипотетические, а то еще и специально подобранные так чтобы разница была больше. это как сравнивать вычисление числа с плавающей точкой на 8ми битной ардуино и на STM32 с FPU ядром. вроде бы и частоты одинаковые, но почему то STM в сотни раз быстрее. вывод — говно ваша ардуина.

я молчу о том что рекурсивные функции и так плохо читаются и понимаются, а вы сделали код который вообще стал 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))
я подразумевал такое использование, не знаю насколько это правильно, я не настоящий программист :)
[i for i in fibonacci(10)]


Добавил: вот так лучше
list(fibonacci(10))

Почему Фибоначчи с замыканиями код производительный, а рекурсивный вычисляет 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, но анализу сложности рекурсивных алгоритмов я учу первокурсников. Причём написать линейный рекурсивный алгоритм для Фибоначчи совсем даже не сложно, он абсолютно такой же как итеративный (потому что хвостовая рекурсия)

Сюда бы отлично подошла ссылка на call/cc — это предельный вариант того, что, похоже, пытался сделать автор (хоть у него и криво получилось).

Зарегистрируйтесь на Хабре , чтобы оставить комментарий