Тема: Рекурсия

Статья

Числа Чёрча: арифметика без чисел

Как из одних только функций получаются натуральные числа, сложение, умножение, степень и коварный предшественник — с полной раскруткой каждой редукции и рабочим кодом на …

#лямбда-исчисление#кодирование Чёрча#функциональное программирование

Статья

Рекурсия, хвостовые вызовы и как не переполнить стек

Почему в ФП повторение делают рекурсией, как устроен стек вызовов, что такое хвостовой вызов и TCO, как превращать рекурсию в хвостовую аккумулятором, и что делать в …

#функциональное программирование#рекурсия#хвостовая рекурсия

Статья

Рекурсия и разделяй-и-властвуй

Как устроена рекурсия на уровне кадров стека, почему она эквивалентна математической индукции, как проектировать алгоритмы разделяй-и-властвуй и считать их …

#алгоритмы#рекурсия#разделяй и властвуй

Статья

Рекурсия без имён: комбинатор неподвижной точки Y

Как написать факториал в языке, где у функций нет имён: приём открытой рекурсии, вывод комбинатора Y с полной раскруткой редукций, его боевой вариант Z для JavaScript и …

#лямбда-исчисление#рекурсия#комбинаторы

Статья

Динамическое программирование: от мемоизации до оптимизаций

Как перебор с экспоненциальной сложностью превращается в полиномиальный алгоритм: перекрывающиеся подзадачи, дисциплина проектирования состояния, классические семейства …

#алгоритмы#динамическое программирование#рекурсия

Статья

Деревья и бинарные деревья поиска

От определения дерева до продакшн-BST: обходы, инвариант порядка, поиск/вставка/удаление, порядковые запросы, вырождение и почему в реальных библиотеках лежит не BST.

#структуры данных#деревья#бинарные деревья поиска