Рекурсивная функция на практике?

Question

[rusikus]

Объясните пожалуйста суть рекурсии и хвостовой рекурсии в Erlang. Только не на примере вычисления факториала, а например на зайцах. То есть, на практическом примере.
Дополню. Если можно привести простой пример (можно ссылку) практической рекурсивной функции которая считает допустим тех же зайцев с комментариями и той же функции с хвостовой рекурсией.

Comments

[Дмитрий]

Как это на зайцах? Почему не на кошках?
Главное понять суть, есть конфетка, обернутая в три фантика, надо повторить действие "развернуть", чтоб её съесть

[Игорь]

Рекурсия, как правило, не очень часто встречается.
Её пытаются избегать.
В интернете масса примеров как создать рекурсию.

Например, при построении древовидного меню, хотя тоже можно избежать рекурсии.

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

Функция вызывает сома себя создавая копии подпрограмм, со своим стеком, они изолированны друг от друга.
-------------------------------------------

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

Может случиться так, что истина не когда не наступит и мы получим бесконечную рекурсию.
Как если бы мы приставили 2 зеркала друг к другу.

[rusikus]

Дмитрий, спасибо, а хвостовая рекурсия?

[Дмитрий]

rusikus, если по простому, есть пакет конфет, и секундомер, задача съесть все конфеты и в конце увидеть время на это затраченное, кончились конфеты, закончился отчёт времени

[Дмитрий]

rusikus, ну или развернуть все конфеты, конфеты все развернуты, цель достигнута

[Дмитрий]

rusikus, хвостовая не может уйти в бесконечность, так как край всегда виден, то есть она на уменьшение работает

[rusikus]

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

[Дмитрий]

rusikus, пока не кончатся)

[Сергей Горностаев]

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

[Сергей Горностаев]

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

[Дмитрий]

Сергей Горностаев, а на кошках?)
У меня походу не получится по простому объяснить

[rusikus]

Сергей Горностаев, вот юзаю сейчас книгу "Изучай Erlang во имя добра" и прям со страниц её сюда пришёл :-) И вот там в принципе всё это и объясняется что типа чтобы память незаконченными вычислениями рекурсивной функции не переполнять, результат предыдущего записывается в переменную и юзается при следующем вычислении - это понятно. Но не въехать именно в эрланговский стиль написания хвостовой рекурсии. Вот допустим на примере javascript, если я правильно понял это будет что то сродни циклу for c объявлением счетчика? Только вместо счетчика результат предыдущего вычисления? Я правильно понимаю или нет?

[Сергей Горностаев]

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

рекурсивная_функция(аргумент) {
    какой-то код
    одна_переменная
    какой-то код
    другая_переменная
    какой-то код
    возврат рекурсивная_функция(некоторое_значение)
}

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

рекурсивная_функция(аргумент) {
    какой-то код
    одна_переменная
    какой-то код
    другая_переменная
    какой-то код
    возвращаемое_значение = рекурсивная_функция(некоторое_значение)
    другой код
    третья_переменная
    другой код
    другой код
    возврат чего-то
}

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

[Сергей Горностаев]

rusikus, да, вы правильно поняли.

Answer 1

[Сергей]

В общем случае рекурсия это когда функция вызывает саму себя.

Возьмем числа фибоначи: f(x)=f(x-1)+f(x-2), f(0) = 1, f(1) = 1

Erlang код:
```
f(0) -> 1;
f(1) -> 1;
f(X) -> f(X-1)+f(X-2).
```
Это общая рекурсия, она не может быть оптимизирована т.к. результат исполнения зависит от результата исполнения той же функции с другими аргументами. Но данный результат зависит от чего-то еще, поэтому рекурсия не может быть оптимизирована (не хвостовая).

Любой цикл:
```
for i=10 to 1:
do_something
```
loop(0) -> ok;
loop(N) ->
do_something,
loop(N-1).
```

В данном случае рекурсия зовется хвостовой, т.к. результат текущего выполнения функции есть полностью результат выполнения функции для следующей итерации. Т.е. в данном случае компилятор\интерпретатор может не заботиться о том. чтобы отслеживать из какой функции была вызвана текущая функция. Он просто запомнил точку входа в данную рекурсию, и теперь знает что результат самого первого вызова будет результатом самого последнего.
Т.е. другими словами вызов loop(3) будет эквивалентен коду:
```
loop(3),
loop(2),
loop(1),
ok.
```
это обычный линейный код, который никак не является рекурсивным в общем смысле этого слова.

Comments

[rusikus]

правильно ли я пониманию, что аккумулятор в хвостовой рекурсии на erlang это эквивалент объявлению цикла в c++ например?
for (<объявление счетчика>; <условие выполнения цикла>; <шаг цикла>) {
<тело цикла>
}

[rusikus]

вместо цикла выше хотел слово счетчик написать :-)

[Сергей]

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