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

Что такое рекурсия, как она работает и какое отношение имеет к неизменяемости?

Рекурсия - это функция, которая вызывает себя до тех пор, пока не будет выполнено условие выхода. Это способ разбить большую проблему на более мелкие, которые, когда все решены, также решат большую проблему. Чтобы представить это в реальной жизни: сушка волос может быть формой рекурсии. Высуши волосы минутку. Проверьте, сухие ли мои волосы. Если он высох, остановись. Или суши волосы одну минуту.

Как рекурсия работает в стеке

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

Стек - это место в памяти, где хранятся временные переменные, созданные вызовами функций. Стек представляет собой структуру данных «последний пришел - первый ушел» (LIFO), что означает, что последний добавленный элемент будет первым удаленным элементом. Каждый раз, когда функция вызывается в первый раз, она создает блок в стеке, куда помещаются все ее аргументы, любые локальные переменные, которые она создает (и многое другое). После выхода из функции все элементы в стеке выталкиваются (последний вставленный элемент будет вытянут первым (LIFO)), и блок будет удален. Чтобы визуализировать это:

def fctn = { 
      val a = "a"     
      val b = "b"  
     }

С учетом вышеуказанной функции происходит следующее:

По fctn звонку:

  1. Создайте блок стека для fctn
  2. Переменная push - a = "a"
  3. Переменная push - b = "b"

При выходе fctn:

  1. Поп-переменная (b)
  2. Поп-переменная (a)
  3. Стереть fctn блок

Пришло время познакомиться с классической рекурсивной функцией из книги: факториалом.

def factorial(n: Int): Int = {     
    if(n <= 1) 1 // exit condition     
    else n * factorial(n - 1) // recursive call to itself  
  }

Мы видим, что эта функция состоит из двух частей:

  • условие выхода (также известный как базовый случай)
  • рекурсивный вызов, который будет вызываться до тех пор, пока не будет выполнено условие выхода

Теперь давайте посмотрим, как на самом деле работает факториал при вызове. Вы видите рекурсивные вызовы, которые идут «вниз» (в стек) и возвращают значения, которые идут «вверх» (из стека) после оценки вызывающей функции (немного упрощено, но, по сути, это работает). Как я упоминал ранее, здесь мы хорошо видим, как решение меньшей проблемы (факториал (1)) приводит к решению большой проблемы (факториал (4)).

Из объяснения выше легко заметить, насколько важно условие выхода, когда дело доходит до рекурсии. Если бы не условие выхода выше, мы бы продолжали вызывать факториальную функцию бесконечно.

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

Рекурсия головы - это рекурсия, которая вызывает себя с обновленным аргументом до тех пор, пока не будет выполнено условие выхода. Отличный пример - наша факториальная функция. Как вы понимаете, размер стека ограничен, и поэтому, если мы вызовем factorial(1234), код выдаст исключение StackOverflowException - в стеке больше не осталось места для еще одного вызова. Этого мы должны избегать, поэтому альтернативой будет хвостовая рекурсия.

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

Хвостовая рекурсия (если все сделано правильно) - это способ избежать исключений из-за переполнения стека. Хвостовая рекурсивная функция - это функция, в которой самым последним вызовом является обращение к самой себе. Существует аккумулятор, который позволяет передавать вычисленное значение следующему рекурсивному вызову по мере продвижения. В Scala они могут быть аннотированы с помощью @tailrec.

Итак, давайте перепишем наш факториал:

@tailrec  
def factorial(n: Int, accumulator: Int): Int =
    if(n <= 1) accumulator // exit condition     
    else factorial(n - 1, n * accumulator) // recursive call 
  }

Пара отличий от головной рекурсивной версии:

  • Scala позволит вам аннотировать этот код как хвостовую рекурсию.
  • есть аккумулятор
  • не будет «пирамиды» вызовов в стек, как в случае рекурсии головы, потому что мы накапливаем вычисленное значение по мере продвижения и немедленно передаем его следующему рекурсивному вызову.

Звонки будут выглядеть так…

... что немного напоминает цикл while ...

PLOT TWIST! В Scala хвостовые рекурсивные функции фактически оптимизированы так, чтобы они выполняли циклы while под капотом.

Что .. Так помогает ли рекурсия придерживаться неизменности или нет?

Поскольку каждый головной рекурсивный вызов помещается в стек и затем оценивается при выходе из функции, на самом деле не происходит никаких изменений переменных, только вызовы функций. Однако это может вызвать переполнение стека, например если мы получаем факториал большого числа, лучше написать хвостовые рекурсивные функции. Как я уже упоминал ранее, в Scala они фактически автоматически оптимизируются для превращения в циклы while под капотом, поэтому * технически * хвостовая рекурсия на самом деле не является полностью неизменяемым решением.

Итак, все сводится к тому, что вы выберете лично - рекурсия или цикл. Я довольно уверен во внутренней работе Scala над оптимизацией, поэтому я выбираю хвостовые рекурсивные решения. Помимо части уверенности в Scala, они мне кажутся более интересными, в целом более совместимыми с остальной кодовой базой, выглядят более краткими, и мне также не нужно беспокоиться об ошибках, которые я мог бы внести, заставляя свои собственные циклы работать (например, отключение). на-1 или около того).

Реальная жизнь

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

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

Оказывается, мне никто не сказал:

  • в большинстве случаев вы на самом деле используете методы преобразования / агрегации, такие как map, flatMap, foldLeft, foldRight, reduce, filter и т. д., вместо того, чтобы выявлять рекурсию - посмотрите на эту линейную реализацию нашей факториальной функции с использованием foldLeft (который, кстати, реализован как tail рекурсия под капотом):

def factorial(i: Int) = (1 to i).toList.foldLeft(1)(_ * _)

…or reduce:

def factorial(i: Int) = (1 to i).toList.reduce(_ * _)

  • На самом деле, вам понадобится рекурсия для очень нестандартных задач - на работе мне действительно пришлось написать ряд рекурсивных функций для вложенного Json, содержащего рекурсивную структуру данных - не было готового готового решения, такого как foldLeft на список выше.

Я хотел бы подчеркнуть важность написания тестов для ваших рекурсивных функций после их реализации - независимо от того, насколько надежным кажется решение. Я всегда проверяю счастливый путь, средний путь, но также и путь «этого никогда не случится». С большой мощностью приходит большая ответственность, и ничто так не заставляет вас спать по ночам так крепко, как хорошо протестированный (особенно рекурсивный) код в продакшене.

Резюме

Подводя итог, я хотел бы выделить два практических правила написания рекурсивных функций:

  • напишите условие выхода, прежде чем писать что-либо еще (здесь: if n <= 1)
  • убедитесь, что вы приближаетесь к условию выхода в своих рекурсивных вызовах (здесь: передача n - 1 рекурсивному вызову - с каждым шагом, приближающимся к1)

Но помните - как однажды сказала одна мудрая женщина:

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

Я был там, и многие программисты тоже. Поначалу сложно получить правильную рекурсию. Но я обещаю, что если вы решите рекурсивно решать 30 проблем, вы начнете замечать появление нового образа мышления.

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

Ссылки:
Функциональное программирование на Scala: упрощенное от А. Александра
Поваренная книга Scala от А. Александера