<|user|>
Что такое рекурсия? Как она работает? Зачем она нужна?</s>
<|assistant|>
Рекурсия (в программировании) - это вызов функцией самой себя. Например, на JavaScript:
```js
function recursion() {
  recursion();
}
recursion();
```
Тут первый вызов функции recursion на 4й строке запустит рекурсивную функцию, безусловно запускающую саму себя. Это повлечёт падение программы из-за исчерпания стека, поэтому важно продумывать условия остановки рекурсии. Рекурсии без условия остановки успользуются в атаках приводящих к отказу в обслуживании (fork бомбы, DoS).
Рекурсия используется для перебора разных путей выполнения программы или рекуррентных вычислений. Так, например, рекурсией можно обойти бинарное дерево, найти все перестановки цифр в числе или рассчитать факториал, например:
```js
function factorial(n) {
  if (n == 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}
var f4 = factorial(4);
console.log(f4);
```
Вызов этого кода приведёт к выводу в консоль JavaScript результата взятия факториала от 4, то есть 24.
Рассмотрим как он работает. Рекуррентная формула для факториала - это F(n) = N * F(n - 1); F(1) = 1. Код функции написан по этой формуле.
Сначала происходит вызов функции factorial с аргументом 4. Так как 4 не равно 1, то будет выполнена вторая ветка условного выражения if. Вторая ветвь условного выражения возвратит результат умножения аргумента на факториал числа на 1 меньшего чем аргумент - число 4 будет запомнено в програмном стеке, пока происходит вычисление factorial(3). Так будет происходить пока аргумент не уменьшится до единицы, тогда функция перестанет вызывать себя вернув единицу. Тогда, наконец, сможет вычислиться сначала factorial(2) = 2 * factorial(1) = 2 * 1 = 2, следом factorial(3) = 3 * factorial(2) = 3 * 2 = 6, следом factorial(4) = 4 * factorial(3) = 4 * 6 = 24. Результат будет записан в переменную f4, которая будет выведена в консоль.
У рекрсии есть недостатки, так вызовы функций могут исчерпать стек и привести к падению программы, так и то, что рекурсии обычно медленее простых циклов, но не всегда получится просто переписать рекрсию в цикл. Например, вычисление факториала можно было написать в виде цикла:
```js
function factorial(n) {
  var result = 1;
  for (var i = 1; i <= n; i++) {
     result *= i;
  }
  return result;
}
```</s>
<|user|>
А можешь привести простой пример, когда рекурсию трудно/громоздко/некрасиво переписать в виде цикла?</s>
<|assistant|>
Конечно. Вот простой пример. Представьте, что у вас есть иерархия узлов (например, дерево директорий в файловой системе), каждый из которых хранит некоторое значение (например, число файлов) и вам нужно посчитать, скажем, сумму всех этих значений (общее число файлов в директории, включая все её поддиректории). С помощью рекурсии эта задача решается буквально в одну строку. (Аналогично будут выглядеть и другие процедуры, требующие обхода дерева, например поиск узла с каким-то свойством, обновление состояний узлов и т. п.)
```python
def recursive_sum(node):
    return node.value + sum(recursive_sum(child) for child in node.children)
```
Если ту же задачу решать без рекурсии, то может потребоваться явным образом отслеживать, какие узлы обработаны, куда двигаться дальше (вверх или вниз, а если вниз, то к какому конкретно потомку) и т. п. Если порядок обхода неважен, можно это сделать, например, с использованием динамически обновляемого списка узлов для дальнейшего посещения.
```python
def non_recursive_sum(node):
    result = 0
    todo = [node]
    while todo:
        current_noode = todo.pop()
        result += current_noode.value
        todo.extend(current_noode.children)
    return result
```
Согласитесь, что первую реализацию читать гораздо проще. Она не только короче, в ней нет лишних промежуточных объектов вроде списка `todo` и «сумматора» `result`. Она читается буквально как естественный язык: «Рекурсивная сумма узла возвращает значение узла плюс сумму рекурсивных сумм по всем его потомкам». Вторую реализацию уже так просто не опишешь: нужно говорить о временном списке, из которого на каждом шаге цикла извлекается и обрабатывается текущий узел, и в который добавляются его потомки; также придётся сказать об инициализации списка и условии завершения цикла. В общем, много технических деталей, не относящихся к делу и отвлекающих внимание.</s>
