Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

1 <p><strong>В этой статье разбираемся, какой бывает рекурсия, как с ее помощью можно решать задачи и что такое рекурсивные функции.</strong></p>

2 <h2>Содержание</h2>

3 <ul><li><a>Рекурсия vs рекурсивный или итеративный процесс: в чем разница</a></li>

4 <li><a>Методы решения задач с помощью рекурсии</a></li>

5 <li><a>В чем отличие рекурсивного процесса от итеративного</a></li>

6 <li><a>Что такое рекурсивные функции и в чем особенность их применения</a></li>

7 <li><a>Что такое хвостовая рекурсия</a></li>

8 </ul><h2>Рекурсия vs рекурсивный или итеративный процесс: в чем разница</h2>

9 <p>Рекурсия - это функция, которая вызывает саму себя, но с другими значениями параметров.</p>

10 <p>На самом деле понятия рекурсии и процесса никак не связаны. Рекурсия - просто абстрактная концепция, которую можно наблюдать в природе, в математике и в других областях. Такая же абстрактная, как, например, музыкальная гармония.</p>

11 <p>Теперь давайте поговорим о компьютерах. Для выполнения задач им нужны инструкции. Когда компьютер выполняет набор инструкций - это процесс. Ваш работающий сейчас браузер - тоже процесс. Простой цикл, выводящий на экран десять раз число "42" - также процесс.</p>

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

13 <blockquote><h3>Читайте также:</h3>

14 <p>Что такое<a>callback-функция</a>в JavaScript?</p>

15 </blockquote><h2>Методы решения задач с помощью рекурсии</h2>

16 <p>Есть два метода решения задач с использованием рекурсии: рекурсивный процесс и итеративный процесс. Рекурсия в них не отличается: в каждом из подходов функция вызывает саму себя, рекурсивно. Отличаются способы использования идеи рекурсии.</p>

17 <p>Давайте продолжим аналогию с музыкальной гармонией и подумаем про фортепиано. При написании музыки используем эту концепцию - "гармонию звуков". Можно придумать разные способы: рассчитывать частоты звуков - ноты - математическими формулами или рассчитывать правильные расстояния между клавишами.</p>

18 <p>В детстве я научился находить правильные расстояния между клавишами на фортепиано, и получал гармоничные комбинации звуков, но понятия не имел, что это за ноты. А профессиональный музыкант знает теорию и подбирает гармонию другими методами. В любом случае, гармония есть гармония, эта концепция не меняется, меняются лишь способы ее использования.</p>

19 <h2>В чем отличие рекурсивного процесса от итеративного</h2>

20 <p>Рекурсивный процесс на каждом шаге рекурсии говорит "я это запомню и потом посчитаю". "Потом" наступает в самом конце.</p>

21 <ul><li>Если рекурсивный процесс считает факториал 6, то ему нужно запомнить 5 чисел, чтобы посчитать их в самом конце, когда уже никуда не деться и рекурсивно двигаться вниз больше нельзя</li>

22 <li>Когда мы находимся в очередном вызове функции, то где-то снаружи этого вызова в памяти хранятся эти запомненные числа</li>

23 </ul><p>На этой картинке видно, как растет использование памяти: процессу нужно запоминать все больше и больше чисел</p>

24 <p>Рекурсивный процесс - это процесс с отложенным вычислением.</p>

25 <p>Итеративный процесс постоянно говорит "<em>я сейчас посчитаю все что можно и продолжу</em>" на каждом шаге рекурсии. Ему не нужно ничего запоминать вне вызова, он всегда все считает в первый возможный момент. Каждый шаг рекурсии может существовать в изоляции от прошлых, потому что вся информация передается последовательно.</p>

26 <ul><li>Когда итеративный процесс считает факториал 6, то ему не нужно запоминать числа. Нужно лишь считать и передавать результат дальше, в новый вызов</li>

27 <li>Когда мы находимся в очередном вызове функции, снаружи этого вызова в памяти ничего не нужно запоминать</li>

28 </ul><p>А на этой картинке видно, что использование памяти не растет.</p>

29 <p>Подытожим в шуточной форме. Рекурсивный процесс - это чувак, который все дела откладывает на вечер пятницы. В течение недели у него мало работы, а в пятницу завал. Но ему так нравится.</p>

30 <p>Итеративный процесс - это чувак, который все делает при первой возможности. У него работа равномерно распределена по неделе, а пятница - просто обычный день, но последний.</p>

31 <h2>Что такое рекурсивные функции и в чем особенность их применения</h2>

32 <p>Рекурсивные функции - это те функции, которые используют итеративный процесс. Для каждого рекурсивного вызова в стек вызовов записывается вся информация, связанная с этим вызовом, вроде параметров функции и ее локальных переменных, адреса возврата в точку вызова.</p>

33 <p>Для рекурсивной функции выделяется дополнительная область памяти - лексический контекст функции, область видимости -, которая обслуживает рекурсивный вызов. Так как это стек вызовов, то контексты предыдущих рекурсивных вызовов также продолжают занимать память.</p>

34 <p>Достижение большой глубины рекурсии, или же, недостижение терминального условия выхода из рекурсии, приводит к переполнению стека, так как он ограничен в размерах, и аварийному завершению всей программы.</p>

35 <blockquote><h3>Читайте также:</h3>

36 <p>Как<a>проверить качество кода</a>: функциональное и нефункциональное тестирование</p>

37 </blockquote><p>В контексте каждого рекурсивного вызова такой функции хранится вся необходимая информация для его успешного выполнения. Он самодостаточен и никак не зависит от предыдущих контекстов. Помните, что этот чувак ничего не откладывает на потом, на вечер пятницы?</p>

38 <p>В наших практиках на Хекслете мы реализовывали такое поведение благодаря использованию аккумулятора acc, который передается в качестве аргумента из одного вызова в другой и накапливает в себе результат вычисления необходимого значения.</p>

39 <p>Получается, что, грубо говоря, на каком бы по уровню вложенности рекурсивном вызове мы не находились, все предыдущие уже не имеют значения и являются "бесполезной обузой", нагружающей память. Это распространяется в том числе и на самый последний рекурсивный вызов, где срабатывает терминальное условие. Он готов вернуть готовое вычисленное значение из функции сразу, ему не нужны для этого предыдущие контексты в стеке.</p>

40 <h2>Что такое хвостовая рекурсия</h2>

41 <p>Как использовать преимущества итеративного процесса и одновременно избавиться от недостатка рекурсивных функций, то есть от неумолимого роста использования памяти? Можно избавить процесс от заполнения стека "ненужными" контекстами предыдущих вызовов и обеспечить прямой возврат из функции при достижении терминального условия.</p>

42 <p>Для этого служит так называемая оптимизация хвостовой рекурсии (Tail call optimization). Итеративный процесс, который мы рассмотрели, как раз можно отнести к хвостовой рекурсии. Благодаря оптимизации состояния стека, она придает итеративному процессу вид "плоской" итерации. Так исключается его переполнение из-за большой глубины рекурсии.</p>

43 <p>Хвостовая рекурсия и ее оптимизация широко используется при написании программ на функциональных языках программирования.</p>