Рекурсия является важной частью 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) рекурсивно.
Сначала мы определим функцию с именем fac (N).
Мы можем определить рекурсивную функцию, вызывая fac (N) рекурсивно.
Выход вышеуказанной программы —
Выход
24
Практический подход к рекурсии
В этом разделе мы подробно разберем различные типы рекурсий и их использование в 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 | []], а список длиной два будет определен как [X | [Y | [ ]]] . Обратите внимание, что вторым элементом является сам список. Это означает, что нам нужно только сосчитать первый, и функция может вызвать себя для второго элемента. Учитывая, что каждое значение в списке считается длиной 1.
Первая функция len ([]) используется для условия особого случая, если список пуст.
Шаблон [H | T] для сопоставления со списками одного или нескольких элементов, поскольку список длиной один будет определен как [X | []], а список длиной два будет определен как [X | [Y | [ ]]] . Обратите внимание, что вторым элементом является сам список. Это означает, что нам нужно только сосчитать первый, и функция может вызвать себя для второго элемента. Учитывая, что каждое значение в списке считается длиной 1.
Выход вышеупомянутой программы будет —
Выход
4
Хвост Рекурсия
Чтобы понять, как работает хвостовая рекурсия, давайте разберемся, как работает следующий код в предыдущем разделе.
Синтаксис
len([]) -> 0; len([_|T]) -> 1 + len(T).
Для ответа на 1 + len (Отдых) нужно найти ответ len (Отдых). Затем самой функции 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]).
Выход вышеуказанной программы —
Выход
4
дублировать
Давайте посмотрим на пример рекурсии. На этот раз давайте напишем функцию, которая принимает целое число в качестве первого параметра, а затем любой другой член в качестве второго параметра. Затем он создаст список из столько копий термина, сколько указано целым числом.
Давайте посмотрим, как будет выглядеть пример этого —
-module(helloworld). -export([duplicate/2,start/0]). duplicate(0,_) -> []; duplicate(N,Term) when N > 0 -> io:fwrite("~w,~n",[Term]), [Term|duplicate(N-1,Term)]. start() -> duplicate(5,1).
Выход вышеупомянутой программы будет —
Выход
1, 1, 1, 1, 1,
Перестановка списка
Не существует границ, по которым вы можете использовать рекурсию в Erlang. Давайте теперь быстро посмотрим, как мы можем обратить элементы списка с помощью рекурсии. Следующая программа может быть использована для достижения этой цели.
пример
-module(helloworld). -export([tail_reverse/2,start/0]). tail_reverse(L) -> tail_reverse(L,[]). tail_reverse([],Acc) -> Acc; tail_reverse([H|T],Acc) -> tail_reverse(T, [H|Acc]). start() -> X = [1,2,3,4], Y = tail_reverse(X), io:fwrite("~w",[Y]).
Выход вышеупомянутой программы будет —
Выход
[4,3,2,1]
Следующие вещи должны быть отмечены о вышеупомянутой программе —
Мы снова используем концепцию временных переменных для хранения каждого элемента списка в переменной с именем Acc.
Затем мы вызываем tail_reverse рекурсивно, но на этот раз мы гарантируем, что последний элемент будет помещен в новый список первым.
Затем мы рекурсивно вызываем tail_reverse для каждого элемента в списке.