Вчера помогала другой блогерше с заданием по функциональному программированию и столкнулась с вопросом - а как объяснить не математику, что такое рекурсия? Тем, кто знаком с такими математическими терминами как реккурентные функции и индукция, рекурсия по идее будет интуитивно понятна и так.
Попробую рассказать про рекурсию максимально просто (для более интеллектуальных и подробных объяснений ищите статьи и видео в Интернете, и всё должно проясниться) для тех, кто ещё не разобрался.
Наверно те, кто уже сталкивался с рекурсией, примерно понимает, что это функция, которая вызывает саму себя. Но как это может работать - непонятно?
Давайте возьмём для примера функцию «сумма элементов списка» (или массива).
sum(lst) - можно ее определить итеративно, пройдясь циклом через все элементы списка. (for x in list: result += x)
Но можно воспользоваться и рекурсивным определением. Оно будет выглядеть примерно так:
1) Если список пуст, то сумма равна 0. - Это граничное условие, оно должно быть не рекурсивным, потому что в этой точке цикл выполнения функции закончится, и рекурсия остановится.
2) Если список не пуст, то сумма равна первому его элементу + сумме оставшейся части списка.
На питоне это будет выглядеть примерно так:
Давайте представим, как будет выполняться такая функция со списком [1,2,3]
1) Первый вызов rec_sum([1,2,3]) - вернёт 1 + rec_sum([2,3]))
2) Второй вызов вернёт 2 + rec_sum([3]).
3) Третий 3 + rec_sum([]) - здесь рекурсия заканчивается, с пустым списоком функция вернёт ноль.
То есть, выполнение разложится на этапы так:
rec_sum( [1, 2, 3]) = 1 + rec_sum([2,3]) = 1 + 2 + rec_sum([3]) = 1 + 2 + 3 + rec_sum([]) = 1 + 2 +3 + 0 = 6
После того, как функция разложится на такую цепочку рекурсивных вызовов и достигнет дна рекурсии, каждый вызов функции начнет возвращать значения - начиная с самого нового, самого последнего вызова (то есть с пустым списком):
rec_sum([]) возвращает 0
rec_sum([3]) возвращает 3 + то, что вернула rec_sum([]) = 3 + 0 = 3
rec_sum([2,3]) возвращает 2 + то, что вернула rec_sum([3]) = 2 + 3 = 5
rec_sum([1,2,3]) возвращает 1 + то, что вернулось на предыдущем шаге, то есть 1 + 5 = 6
Чтобы понять, почему это работает именно так, советую изучить, как устроен стек вызовов функций (и обычных, не рекурсивных в том числе) - то есть, что реально происходит в памяти компьютера, когда вы вызываете функцию, и в каком порядке что там выполянется. Это не сложно, с хорошей картинкой и объяснением всё будет понятно.
Напоследок добавлю print в нашу функцию, чтобы наглядно показать, что происходит, когда мы её вызываем на каждом этапе:
В общем, всё как я и описала.
P.S: Пример выше исключительно для демонстрации рекурсии. С точки зрения продуктовой разработки, рекурсия со слайсами списка в питоне - очень неэффективное и ресурсозатратное решение. Используйте циклы 🙂
P.P.S: А вот в функциональных языках программирования есть оптимизации на уровне компиляторов для эффективного выполнения хвостовой рекурсии. Вот только кто использует этот ваш Haskell в проде?
Подписывайтесь на мой телеграм-канал Программирование для гуманитариев. Там можно почитать больше публикаций и задать свой вопрос автору блога о карьере в IT
