Erlang - Đệ quy

Đệ quy là một phần quan trọng của Erlang. Trước tiên, hãy xem cách chúng ta có thể thực hiện đệ quy đơn giản bằng cách thực hiện chương trình giai thừa.

Thí dụ

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

Những điều sau đây cần được lưu ý về chương trình trên:

Đầu tiên chúng ta định nghĩa một hàm gọi là fac (N).
Chúng ta có thể định nghĩa hàm đệ quy bằng cách gọi đệ quy fac (N).

Kết quả của chương trình trên là:

Đầu ra

Phương pháp tiếp cận thực tế đối với đệ quy

Trong phần này, chúng ta sẽ hiểu chi tiết về các loại đệ quy khác nhau và cách sử dụng nó trong Erlang.

Đệ quy độ dài

Có thể thấy một cách tiếp cận thực tế hơn đối với đệ quy với một ví dụ đơn giản được sử dụng để xác định độ dài của một danh sách. Một danh sách có thể có nhiều giá trị như [1,2,3,4]. Hãy sử dụng đệ quy để xem làm thế nào chúng ta có thể nhận được độ dài của một danh sách.

Example

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

Những điều sau đây cần được lưu ý về chương trình trên:

Chức năng đầu tiên len([]) được sử dụng cho điều kiện trường hợp đặc biệt nếu danh sách trống.
Các [H|T] mẫu để khớp với danh sách một hoặc nhiều phần tử, vì danh sách có độ dài một phần tử sẽ được xác định là [X|[]] và danh sách độ dài hai sẽ được xác định là [X|[Y|[]]]. Lưu ý rằng phần tử thứ hai là một danh sách. Điều này có nghĩa là chúng ta chỉ cần đếm phần tử đầu tiên và hàm có thể tự gọi phần tử thứ hai. Cho mỗi giá trị trong danh sách được tính là độ dài 1.

Đầu ra của chương trình trên sẽ là:

Output

Đệ quy đuôi

Để hiểu cách hoạt động của đệ quy đuôi, chúng ta hãy hiểu cách hoạt động của đoạn mã sau trong phần trước.

Syntax

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

Câu trả lời cho 1 + len (Rest) cần câu trả lời của len (Rest) được tìm thấy. Khi đó, bản thân hàm len (Rest) cần kết quả của một lệnh gọi hàm khác. Các phần bổ sung sẽ được xếp chồng lên nhau cho đến khi tìm thấy cái cuối cùng và chỉ khi đó kết quả cuối cùng mới được tính toán.

Đệ quy đuôi nhằm mục đích loại bỏ sự xếp chồng của hoạt động này bằng cách giảm chúng khi chúng xảy ra.

Để đạt được điều này, chúng ta sẽ cần phải giữ thêm một biến tạm thời làm tham số trong hàm của chúng ta. Biến tạm thời nói trên đôi khi được gọi là bộ tích lũy và hoạt động như một nơi để lưu trữ các kết quả tính toán của chúng tôi khi chúng xảy ra nhằm hạn chế sự gia tăng các lệnh gọi của chúng tôi.

Hãy xem một ví dụ về đệ quy đuôi -

Example

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

Kết quả của chương trình trên là:

Output

Bản sao

Hãy xem một ví dụ về đệ quy. Lần này, hãy viết một hàm nhận một số nguyên làm tham số đầu tiên và sau đó là bất kỳ số hạng nào khác làm tham số thứ hai. Sau đó, nó sẽ tạo một danh sách bao nhiêu bản sao của thuật ngữ được chỉ định bởi số nguyên.

Hãy xem ví dụ về điều này sẽ như thế nào -

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

Đầu ra của chương trình trên sẽ là:

Đầu ra

1,
1,
1,
1,
1,

Đảo ngược danh sách

Không có giới hạn nào mà bạn có thể sử dụng đệ quy trong Erlang. Bây giờ hãy nhanh chóng xem xét cách chúng ta có thể đảo ngược các phần tử của danh sách bằng cách sử dụng đệ quy. Chương trình sau đây có thể được sử dụng để thực hiện điều này.

Thí dụ

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

Đầu ra của chương trình trên sẽ là:

Đầu ra

[4,3,2,1]

Những điều sau đây cần được lưu ý về chương trình trên:

Một lần nữa chúng ta đang sử dụng khái niệm biến tạm thời để lưu trữ từng phần tử của Danh sách trong một biến có tên là Acc.
Sau đó chúng tôi gọi tail_reverse đệ quy, nhưng lần này, chúng tôi đảm bảo rằng phần tử cuối cùng được đưa vào danh sách mới trước tiên.
Sau đó, chúng tôi gọi đệ quy tail_reverse cho mỗi phần tử trong danh sách.