Рекурсия

Рекурсия — это техника, которая позволяет разбить проблему на более мелкие части. Этот метод позволяет нам удалить некоторые локальные побочные эффекты, которые мы выполняем при написании циклических структур, а также делает наш код более выразительным и читабельным. В этом посте мы увидим, почему это очень полезный метод в функциональном программировании и как он может нам помочь.

Функциональные петли

В функции, которую мы написали в предыдущем посте:

Вы могли заметить, что в этом императивном цикле есть побочный эффект . Мы присваиваем результат вычисления накопителю, потому что foreach — это функция, которая возвращает Unit. Или, другими словами, он ничего не возвращает, поэтому у нас нет другого выбора. Таким образом, метод foreach является утверждением. Мы говорим, что оператор — это блок кода, который может быть выполнен, но не сокращен. С другой стороны, мы говорим, что блок кода, который можно уменьшить, является выражением.

Рекурсия головы

Первая техника, которую мы собираемся использовать, называется рекурсия головы. Давайте переведем предыдущую функцию в рекурсивную функцию головы:

Эта функция не имеет побочных эффектов . Внутренне он вычисляет сумму, пока мы не достигнем базового случая, который равен 0. Вот трассировка стека для sumIntsToRecursive(5) :

Можно сказать, что рекурсивные вызовы происходят до вычисления или в начале. Это означает, что после рекурсивного вызова у нас могут быть другие блоки для оценки, или, как в этом случае, мы оцениваем первую сумму после того, как все последующие оценки уменьшены.

Вы также можете видеть, что мы должны сохранять текущее состояние вычислений до тех пор, пока мы не закончим оценку стека, поэтому на последнем шаге мы получим: 5 + 4 + 3 + 2 + 1 а затем мы оценим последнее Случай, чтобы закончить с вычислением всех значений, которые мы имели в промежуточных шагах.

Сохранение этого состояния может быть проблемой, особенно если мы имеем дело с большим количеством цифр. Если мы попытаемся оценить предыдущую функцию, передав в качестве аргумента Integer.MAX_VALUE мы увидим, что функция дает сбой и выдает нам StackOverflowException . Даже если мы достигли нашей первоначальной цели — не иметь побочных эффектов , у нас она есть, если число слишком велико для оценки. Это приведет нас к следующей технике, хвостовой рекурсии:

Хвостовая рекурсия

Единственная разница между рекурсией головы и хвоста состоит в том, что рекурсивные вызовы происходят после вычисления или в хвосте. Давайте переведем предыдущую функцию в хвостовую рекурсивную функцию:

Как вы могли заметить, последний вызов в методе — это хвостовой рекурсивный вызов, нам нужно выполнить вычисления перед его вызовом. Это привело нас к следующей трассировке стека:

Как вы могли заметить, мы должны удерживать только предыдущее промежуточное состояние, но не все предшествующее текущему. Если мы выполним эту функцию с аргументом Integer.MAX_VALUE мы увидим, что она завершается нормально.

В современных языках, таких как Scala, Kotlin и т. Д.… Рекурсивные вызовы Tail преобразуются в императивные циклы во время компиляции для оптимизации кода. В Scala, когда мы пишем хвостовую рекурсивную функцию, мы можем аннотировать рекурсивный метод с помощью @tailrec . Если мы сделаем это, и функция не будет хвостовой рекурсивной, у нас будет ошибка во время компиляции.

Я рекомендую вам попрактиковаться в написании рекурсивных функций, поскольку они являются обычной техникой в ​​функциональном программировании. Число Фибоначчи , калькулятор боулинга или треугольник Паскаля — хорошие упражнения, чтобы привыкнуть к нему.