Erlang - 递归

递归是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) 来定义递归函数。

上面程序的输出是 −

输出

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] 模式与一个或多个元素的列表进行匹配， 长度为 1 的列表将定义为 [X|[]]，长度为 2 的列表将定义为 [X|[Y|[]]]。请注意，第二个元素本身就是一个列表。 这意味着我们只需要计算第一个元素，函数就可以在第二个元素上调用自身。 给定列表中每个值的长度均为 1。

上述程序的输出将是 −

输出

4

尾递归

要了解尾递归的工作原理，让我们了解上一节中的以下代码的工作原理。

语法

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]).

上面程序的输出是 −

输出

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 。