Comments 12
Это всё хорошо как объяснение техники мемоизации на некотором примере, но эффективная рекурсивная реализация вычисления чисел Фибоначчи не требует ни экспоненциальной рекурсии, ни мемоизации. Алгоритм содержит один хвостовой рекурсивный вызов, не использует память для временных переменных и, соответственно, не требует в ней поиска:
(defun fib1 (n s1 s2)
(cond
((eq n 0) 0)
((eq n 1) 1)
((eq n 2) (+ s1 s2))
(t (fib1 (- n 1) s2 (+ s1 s2)))))
(defun fib (n)
(fib1 n 0 1))Я бы лично не очень порадовался ответу человека, который решил бы написать эффективное вычисление ряда Фибоначчи через мемоизацию. Это своего рода горе от ума.
Спасибо за ваше замечание. Вы абсолютно правы, что существуют более эффективные алгоритмы для вычисления чисел Фибоначчи, такие как хвостовая рекурсия. Вместо экспоненциальной рекурсии и мемоизации, хвостовая рекурсия позволяет оптимизировать использование памяти и сократить количество вызовов функций. Вы правильно отметили, что мемоизация может быть избыточной в данном случае.
Однако, моя цель была продемонстрировать именно технику мемоизации, так как она часто применяется в решении рутинных задач и может быть полезной в других ситуациях, где хвостовая рекурсия не применима или не оптимальна. Важно отметить, что выбор оптимального алгоритма во многом зависит от задачи и контекста, и хвостовая рекурсия, безусловно, является более эффективным и предпочтительным подходом для вычисления чисел Фибоначчи по сравнению с мемоизацией. Но мемоизация тоже имеет свою ценность и может быть полезным инструментом в арсенале разработчика.
Если мне память не изменяет, число Фибоначчи можно вычислить через матрицу и быстрое возведение в степень. Без вычисления всех предыдущих членов.
Вы абсолютно правы, существует алгоритм для вычисления числа Фибоначчи с использованием матриц и быстрого возведения в степень, признаю, что пример с числами Фибоначчи оказался не лучший выбор для демонстрации техники мемоизации. Однако, моя цель была показать саму технику и принцип ее работы, а не фокусироваться на числах Фибоначчи в частности. К сожалению, на момент написания статьи мне не пришел в голову более подходящий пример для демонстрации мемоизации. В любом случае, спасибо за замечание.
За такие рекурсию и мемоизацию я бы попросил охрану завершить собеседование в стиле обижать но не калечить. Почему ряд Фибоначчи не преподают как пример неверного применения рекурсии - не знаю.
Спасибо за ваше мнение. Вы правильно отмечаете, что есть более эффективные подходы к вычислению чисел Фибоначчи, такие как хвостовая рекурсия или итеративные методы. Рекурсия и мемоизация могут быть не самыми оптимальными подходами в этом случае, но они всё же могут быть полезными для демонстрации основных концепций и возможностей в других задачах.
Цель статьи была продемонстрировать технику мемоизации на примере ряда Фибоначчи, хотя я понимаю, что это может быть не лучшим примером. Важно помнить, что хотя мемоизация не является оптимальным решением для вычисления чисел Фибоначчи, она может быть очень полезной в других ситуациях, где экспоненциальная рекурсия является неизбежной, а хвостовая рекурсия или итеративные методы не подходят.
в реальной жизни — числа Фибоначчи являются ярчайшим примером или эталоном "не нужно".
То есть на собеседованиях, действительно, часто спрашивают про этот ряд. Вот только с числами Фибоначчи программист сталкивается крайне редко. И даже тогда, когда сталкивается — то чаще всего в каком-нибудь легаси коде, куда этот ряд кто-то затащил не в силу необходимости, а потому что хотелось, наконец, куда-то его затащить.
Как-то так, имхо.
Спасибо за ваше мнение! Вы правы в том, что числа Фибоначчи могут быть редко применимы в реальных задачах программирования. Однако, причина, по которой числа Фибоначчи часто упоминаются на собеседованиях, заключается в том, что они служат хорошим примером для проверки понимания кандидатом базовых концепций, таких как рекурсия, динамическое программирование и мемоизация. Цель моей статьи была в демонстрации техники мемоизации на примере, который знаком многим программистам. Хотя числа Фибоначчи могут быть не самым распространенным примером в реальной жизни, их использование в данном контексте помогает быстро объяснить и продемонстрировать работу мемоизации.
Вы отвечаете так, будто, статья — это программа в play.store, а комменты пользователей — отзывы, на которые выложивший программу обязан ответить
:)
PS: я вообще о чём. О том, что и проверять знание важных концепций стоит на более реалистичных примерах/задачах. Если ничего кроме фибоначчи для рекурсии в голову не лезет — ну и не нужная значит это концепция.
За многие годы программирования я, по моему, с рекурсией сталкивался ну может быть раза два. И, думаю, ткни в любого программиста — у него будет то же самое.
Я думал будет не культурно не отвечать на комментарии)
В этом замечании, скорее всего, вы правы по всем пунктам. Остается только надеятся, что кому-то, всё-таки, пригодится!
Это дело привычки и используемого языка. В некоторых языках рекурсия является основным или даже единственным инструментом управления вычислительным процессом (из небанальных примеров назову DB2 SQL; хотя не буду утверждать, что мне доводилось коротать время за написанием циклических алгоритмов на SQL). В целом рекурсию частенько доводилось использовать.
Чувствуется, что часть статьи и ответы на комментарии написаны автором с помощью ChatGPT)
Ряд Фибоначчи и Мемоизация с примерами на Swift языке