Erlang - Rekursi
Rekursi adalah bagian penting dari Erlang. Pertama mari kita lihat bagaimana kita dapat mengimplementasikan rekursi sederhana dengan mengimplementasikan program faktorial.
Contoh
-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]).
Hal-hal berikut perlu diperhatikan tentang program di atas -
Kami pertama kali mendefinisikan fungsi yang disebut fac (N).
Kita dapat mendefinisikan fungsi rekursif dengan memanggil fac (N) secara rekursif.
Output dari program diatas adalah -
Keluaran
24
Pendekatan Praktis untuk Rekursi
Pada bagian ini, kita akan memahami secara rinci berbagai jenis rekursi dan penggunaannya di Erlang.
Rekursi Panjang
Pendekatan rekursi yang lebih praktis dapat dilihat dengan contoh sederhana yang digunakan untuk menentukan panjang daftar. Sebuah daftar dapat memiliki beberapa nilai seperti [1,2,3,4]. Mari gunakan rekursi untuk melihat bagaimana kita bisa mendapatkan panjang daftar.
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]).
Hal-hal berikut perlu diperhatikan tentang program di atas -
Fungsi pertama len([]) digunakan untuk kondisi kasus khusus jika daftar kosong.
Itu [H|T] pola untuk dicocokkan dengan daftar satu atau lebih elemen, sebagai daftar panjang yang akan didefinisikan sebagai [X|[]] dan daftar panjang dua akan didefinisikan sebagai [X|[Y|[]]]. Perhatikan bahwa elemen kedua adalah daftar itu sendiri. Artinya kita hanya perlu menghitung yang pertama dan fungsinya bisa memanggil dirinya sendiri pada elemen kedua. Diberikan setiap nilai dalam daftar dihitung sebagai panjang 1.
Output dari program di atas adalah -
Output
4
Rekursi Ekor
Untuk memahami cara kerja rekursi ekor, mari kita pahami cara kerja kode berikut di bagian sebelumnya.
Syntax
len([]) -> 0;
len([_|T]) -> 1 + len(T).
Jawaban untuk 1 + len (Istirahat) membutuhkan jawaban len (Istirahat) untuk ditemukan. Fungsi len (Istirahat) itu sendiri kemudian membutuhkan hasil dari pemanggilan fungsi lain untuk ditemukan. Penambahan akan ditumpuk sampai yang terakhir ditemukan, dan hanya kemudian hasil akhirnya akan dihitung.
Rekursi ekor bertujuan untuk menghilangkan penumpukan operasi ini dengan menguranginya saat terjadi.
Untuk mencapai ini, kita perlu menyimpan variabel sementara tambahan sebagai parameter dalam fungsi kita. Variabel temporer yang disebutkan di atas kadang-kadang disebut akumulator dan bertindak sebagai tempat untuk menyimpan hasil penghitungan kami saat terjadi untuk membatasi pertumbuhan panggilan kami.
Mari kita lihat contoh rekursi ekor -
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]).
Output dari program diatas adalah -
Output
4
Duplikat
Mari kita lihat contoh rekursi. Kali ini mari kita tulis sebuah fungsi yang menggunakan integer sebagai parameter pertama dan kemudian istilah lain sebagai parameter kedua. Ini kemudian akan membuat daftar sebanyak salinan istilah seperti yang ditentukan oleh integer.
Mari kita lihat bagaimana contoh ini akan terlihat -
-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).
Output dari program di atas adalah -
Keluaran
1,
1,
1,
1,
1,
Daftar Pembalikan
Tidak ada batasan di mana Anda dapat menggunakan rekursi di Erlang. Sekarang mari kita lihat dengan cepat bagaimana kita bisa membalikkan elemen daftar menggunakan rekursi. Program berikut dapat digunakan untuk melakukannya.
Contoh
-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]).
Output dari program di atas adalah -
Keluaran
[4,3,2,1]
Hal-hal berikut perlu diperhatikan tentang program di atas -
Kami kembali menggunakan konsep variabel sementara untuk menyimpan setiap elemen List dalam variabel yang disebut Acc.
Kami kemudian menelepon tail_reverse secara rekursif, tetapi kali ini, kami memastikan bahwa elemen terakhir dimasukkan ke dalam daftar baru terlebih dahulu.
Kami kemudian secara rekursif memanggil tail_reverse untuk setiap elemen dalam daftar.