rusikus
@rusikus

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

Объясните пожалуйста суть рекурсии и хвостовой рекурсии в Erlang. Только не на примере вычисления факториала, а например на зайцах. То есть, на практическом примере.
Дополню. Если можно привести простой пример (можно ссылку) практической рекурсивной функции которая считает допустим тех же зайцев с комментариями и той же функции с хвостовой рекурсией.
  • Вопрос задан
  • 334 просмотра
Решения вопроса 1
begemot_sun
@begemot_sun
Программист в душе.
В общем случае рекурсия это когда функция вызывает саму себя.

Возьмем числа фибоначи: 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.
```
это обычный линейный код, который никак не является рекурсивным в общем смысле этого слова.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы