Unetway

Erlang - Рекурсия

Рекурсия - важная часть Эрланг. Сначала давайте посмотрим, как мы можем реализовать простую рекурсию, реализуя факториальную программу.

-module(helloworld). 
-export([fac/1,start/0]). 

fac(N) when N == 0 -> 1; 
fac(N) when N > 0 -> N*fac(N-1). 

start() -> 
   X = fac(4), 
   io:fwrite("~w",[X]).

Необходимо отметить следующее:

  • Сначала мы определяем функцию, называемую fac (N)
  • Мы можем определить рекурсивную функцию, вызвав рекурсивно функцию fac (N)

Практический подход к рекурсии

В этом разделе мы подробно рассмотрим различные типы рекурсий и его использование в Erlang.

Длина рекурсии

Более практичный подход к рекурсии можно увидеть с помощью простого примера, который используется для определения длины списка. Список может иметь несколько значений, например [1,2,3,4]. Давайте используем рекурсию, чтобы узнать, как мы можем получить длину списка.

-module(helloworld). 
-export([len/1,start/0]). 

len([]) -> 0; 
len([_|T]) -> 1 + len(T). 

start() -> 
   X = [1,2,3,4], 
   Y = len(X), 
   io:fwrite("~w",[Y]).

Необходимо отметить следующее:

  • Первая функция len ([]) используется для специального условия случая, если список пуст.
  • [H | T] , шаблон для сопоставления списков одного или более элементов, в виде списка длины один будет определяться как [Х | []] и список длины два будет определяться как [X | [Y | [ ]]] . Обратите внимание, что второй элемент - это сам список. Это означает, что нам нужно только считать первый, и функция может называть себя вторым элементом. Учитывая, что каждое значение в списке считается длиной 1.

Хвостовая рекурсия

Чтобы понять, как работает хвостовая рекурсия, давайте разобраться, как работает следующий код в предыдущем разделе.

len([]) -> 0; 
len([_|T]) -> 1 + len(T).

Ответ на 1 + len (Rest) требует ответа len (Rest), который нужно найти. Сама функция len (Rest) требовала результата другого вызова функции. Добавления будут складываться до тех пор, пока не будет найден последний, и только тогда будет рассчитан конечный результат.

Рекурсия хвоста направлена ​​на то, чтобы устранить эту сложность операций, уменьшив их по мере их возникновения.

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

-module(helloworld).
-export([tail_len/1,tail_len/2,start/0]). 

tail_len(L) -> tail_len(L,0). 
tail_len([], Acc) -> Acc; 
tail_len([_|T], Acc) -> tail_len(T,Acc+1). 

start() -> 
   X = [1,2,3,4], 
   Y = tail_len(X), 
   io:fwrite("~w",[Y]).