Рекурсия — добро или зло?

Рекурсия — добро или зло? Рекурсию больше относят к функциональному программированию, и действительно, это по сути единственный управляющий механизм в фундаментальной декларативной вычислительной модели. Причём рекурсия (и не только хвостовая!) в ней легко представляется в формате императивных вычислений, и за счёт формальной строгости модели позволяет обходиться вообще без стека (в абстрактной декларативной машине с подстановками, добавлением аккумулятора...). Кто проходил трек "Как понять в программировании всё", надеюсь, это хорошо помнит.

Об этом, кстати, говорит и SICP. Абельсон, правда, упоминает "итеративное" программирование (которое понимается обычно совсем в другом смысле: как методика разработки) — оно не требует цикла, и хвостовая рекурсия и есть итеративное программирование. Ну, на моих курсах такие "итеративные" вычисления определяются декларативной моделью (переменные с однократным присваиванием), а императивщина — это когда состояние хранится в переменных, которые можно изменять, и т.д.

=

Технически, конструктивно, различие между рекурсией и "итерацией" заключается в том, сохраняется ли необходимая информация в стеке между вызовами. Если нам нужно выполнить некоторую операцию после завершения рекурсивного вызова, то нужен стек, чтобы помнить, куда возвращаться. Если нет — просто продолжаем вычисления дальше без возврата (по этой причине, итеративные программы могут исполняться бесконечно, а рекурсивные в конце концов исчерпают стек).

Cамое приятное, что даёт нам рекурсия — это некоторое усложнение формы выполнения программы за счёт существенного повышения элегантности и выразительности стиля её кодирования. Смотрим на то, *что* делает код, а не на то, *как* он это делает. Вдобавок у хвостовой рекурсии есть ещё одно преимущество перед циклом: она позволяет "всему" оставаться неизменяемым (ну, кроме стека, но это уже другой логический уровень). На уровне кода это безопасно!

=

Посмотрите на цикл — какие в нём содержатся состояния? Как правило, это состояние, определяющее момент остановки (обычно счётчик), и один или несколько промежуточных итогов, которые представляют собой "результат" цикла. Ну так просто возьмите каждое из этих состояний и сделайте его параметром рекурсивной функции. Выполняете матчинг по состоянию, чтобы определить момент завершения "цикла" — возвращаете промежуточные итоги. А в рекурсивном вызове трансформируйте фрагменты состояния и передавайте их в качестве параметров в следующий вызов.

=

Люди, знакомые с ФП, сразу скажут, что есть более простые способы "пролистать" содержимое списка или коллекции. Это правильно: синтаксис функциональных языков позволяет реализовать этот очень распространённый паттерн более чистым (map, fold/unfold, filter...). Короче говоря, если вы привыкли думать об итерации в терминах циклов, то вы можете без особых проблем научиться распознавать "итерационное" состояние и переносить его в параметры.

P.S. Но если цель вашего цикла — получение кучи побочных эффектов, то я вам не помогу. В полноценных языках вроде Julia это безобразие запрещено на уровне семантики. В СильныхИдеях я рассказывал ребятам, как надо разбираться с циклами по-умному: никаких циклов, если их можно заменить подходящей абстракцией (например, генериками).

P.P.S. Отказ от ответственности: как в Java 8 не поддерживалась tail call optimization, так вроде и до 21-й версии ничего не изменилось :)

И не надо валить на JVM, потому что клож умеет в TCO/TCE;

аналогично и с C#: .NET не поддерживает TCO, а вот F# умеет.

Ну а питончику — чисто инженерному языку, вообще не повезло, ибо сам Гвидо наш Россум заявил:

"I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool."

Именно так, я как раз и учу этому всему как "a nice theoretical approach to fundamental mathematics" :) Становитесь умнее!

=

Резюме такое, что, по этим всем причинам, если в языке TCO не поддерживается (и лямбда-выражения небось требуют дополнительного выделения памяти) — не надо использовать рекурсию вообще.

А если ваша функция напрямую рекурсивна по хвосту, то вы скорее всего сможете написать её с помощью fold, и это будет лучшей реализацией!

public static A fold(F > f, A z, Iterable xs)

Источник: vk.com

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