Комментарии 8
Думаю если вы показали способ поиска чисел Фибоначи при помощи рекурсивного процесса, то стоит так же показать и способ с итеративным процессом. Потому что в JS (из коробки) поиск с помощью рекурсивного процесса не эффективен :(
Если кому-то захочется подробнее ознакомиться с рекурсией, то на hexlet есть статья где про рекурсию написано подробнее
https://ru.hexlet.io/blog/posts/recursive
передадим в функцию
Math.floorдлину массива, поделим результат на 2
Всё-таки сначала делим длину пополам, а потом округляем. Иначе смысла нет.
А вообще, зачем pivot брать именно из середины? Есть в этом какая-то сермяга или так повелось просто?
Смотрите, элементы не упорядочены, поэтому первый в массиве ничем не хуже среднего. Но при этом избавляемся от вычислений середины и в цикле убираем одно сравнение - текущего с pivot.
Не то, чтобы большая оптимизация, но зачем бесполезную работу делать, статью ведь могут и дети читать, научатся плохому...
Пример с числами Фибоначчи в разделе "рекурсия" как мне кажется следует подавать только под соусом "как не надо делать" а лучше подать этот пример в разделе "оптимизация" с последующим объяснением "как надо делать и почему".
Потому что программист со школы/универа должен понимать что fibonachi(50) в вашей реализации создаст кучу (~2млрд) вызовов и повешает комп (мой ноут справился за 170сек на JS и за 52сек на сях).
Уместнее ряда Фибоначчи тут бы смотрелся факториал или разложение на множители, но тоже с оговорками.
Факториал вообще случай, когда вместо функции можно просто брать готовые значения из массива фиксированной длины. Числа Фибоначчи тоже, хоть и массив значительно больше, по сегодняшним меркам - мелочь. Зачем это вообще пересчитывать, ещё и рекурсивно?
Массив фиксированной длины для бесконечных последовательностей? К тому же Вы забываете что это учебная задача)
Поэтому я и говорю что это отличный пример для оптимизации.
1. решить задачу рекурсией.
2. решить итеративно на 3х переменных
3. уйти в длинную арифметику.
4. развернуть часть цикла в п2 чтобы сократить количество перестановок
5. предварительно посчитанная таблица значений
6. таблица контрольных точек значений от которых идём алгоритмом из п4.
Если длинная арифметика ещё слишком рано на этом этапе обучения - формулируем задачу как "найти последние 9 цифр числа Фибоначчи с номером 1..2^32". Готовая таблица значений для этой задачи если что займёт 16Gb. памяти.
При этом нет однозначного ответа на вопрос "какой алгоритм быстрее?". Быстрее пишется рекурсия, по соотношению затраты/профит - итеративный, быстрее без ограничений памяти - таблица. Это так же некорректно как считать быстрой быструю сортировку Хоара из этой статьи.
Забыл упомянуть формулу Бине - на ней можно показать опасность округления и длинную нецелочисленную арифметику.
Конечно с оговорками и в другой формулировке все верно, но Вы пытаетесь исправить изначально провальную тут идею рекурсии, заменив её на задачу оптимизации.
Возможно смысл учебы не в этом. Учебная задача на рекурсию для чисел Фибоначчи научит тому, что её бесполезно решать таким образом. Учебная задача на факториал научит переполнению и ограничениям применения стандартных числовых типов данных.
И главный вывод - который должен сделать ученик - что рекурсию использовать не надо :)
Вы пытаетесь исправить изначально провальную тут идею рекурсии
Я просто описал как меня учили и как я учил. На чем вы предлагаете учить рекурсию? У меня сходу разве что ханойская башня всплывает из простого.
И главный вывод - который должен сделать ученик - что рекурсию использовать не надо
Есть еще пара выводов следом за главным) Если стоит тз "использовать рекурсию" - предупреди заказчика что тз некорректно, потом выжми из алгоритма что можно (в примере с Фибоначчи - кэшируй значения). Если есть уверенность что это место не станет узким - используй простое решение. Рекурсия пишется проще всего.
Алгоритмы для веб-разработчиков простыми словами (часть 3)