Fungsi Rekursif: Kata Kunci rec

Kata kunci rec digunakan bersama dengan kata kunci let untuk menentukan fungsi rekursif.

Sintaks

// Recursive function:
let rec function-name parameter-list =
    function-body

// Mutually recursive functions:
let rec function1-name parameter-list =
    function1-body

and function2-name parameter-list =
    function2-body
...

Keterangan

Fungsi rekursif - fungsi yang memanggil dirinya sendiri - diidentifikasi secara eksplisit dalam bahasa pemrogram F# dengan kata kunci rec. Kata kunci rec membuat nama pengikatan let tersedia dalam isinya.

Contoh berikut menunjukkan fungsi rekursif yang melakukan komputasi angka Fibonacci ke-ⁿ menggunakan definisi matematika.

let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

Catatan

Dalam praktiknya, kode seperti sampel sebelumnya tidak ideal karena tidak perlu mengolah ulang nilai yang telah dikomputasi. Hal ini karena ia bukanlah rekursif ekor, yang dijelaskan lebih lanjut dalam artikel ini.

Metode rekursif secara implisit dalam jenis yang ditentukan, yang berarti tidak perlu menambahkan kata kunci rec. Misalnya:

type MyClass() =
    member this.Fib(n) =
        match n with
        | 0 | 1 -> n
        | n -> this.Fib(n-1) + this.Fib(n-2)

Pengikatan let dalam kelas tidak rekursif secara implisit. Semua fungsi ikatan-let memerlukan kata kunci rec.

Rekursi ekor

Untuk beberapa fungsi rekursif, diperlukan untuk merefaktor definisi yang lebih "murni" ke definisi yang rekursif ekor. Ini mencegah komputasi ulang yang tidak diperlukan. Misalnya, generator angka fibonacci sebelumnya dapat ditulis ulang seperti ini:

let fib n =
    let rec loop acc1 acc2 n =
        match n with
        | 0 -> acc1
        | 1 -> acc2
        | _ ->
            loop acc2 (acc1 + acc2) (n - 1)
    loop 0 1 n

Menghasilkan angka fibonacci adalah contoh yang bagus dari algoritma "naif" yang secara matematis murni tetapi tidak efisien dalam praktiknya. Meskipun ini adalah implementasi yang lebih rumit, beberapa aspek membuatnya efisien dalam F# sambil tetap didefinisikan secara rekursif:

• Fungsi dalam rekursif bernama loop, yang merupakan pola F# idiomatik.
• Dua parameter akumulator, yang meneruskan nilai yang diakumulasi ke panggilan rekursif.
• Pemeriksaan pada nilai n agar mengembalikan akumulator tertentu.

Jika contoh ini ditulis secara berulang dengan perulangan, kode akan terlihat mirip dengan dua nilai berbeda yang mengakumulasi angka hingga kondisi tertentu terpenuhi.

Alasan mengapa ini merupakan rekursif ekor adalah karena panggilan rekursif tidak perlu menyimpan nilai apa pun pada tumpukan panggilan. Semua nilai perantara yang terhitung diakumulasikan melalui input ke fungsi dalam. Hal ini juga memungkinkan kompilator F# untuk mengoptimalkan kode agar sama cepatnya dengan saat Anda menulis sesuatu seperti perulangan while.

Adalah umum untuk menulis kode F# yang memproses sesuatu dengan fungsi dalam dan luar secara rekursif, seperti yang ditunjukkan contoh sebelumnya. Fungsi dalam menggunakan rekursi ekor, sementara fungsi luar memiliki antarmuka yang lebih baik untuk pemanggil.

Dimulai dengan F# 8.0, Anda dapat menggunakan TailCall atribut untuk secara eksplisit menyatakan niat Anda untuk menentukan fungsi rekursif ekor ke kompilator. Pengkompilasi kemudian akan memperingatkan Anda jika fungsi Anda melakukan panggilan rekursif non-ekor. Anda dapat menggunakan atribut pada metode dan fungsi tingkat modul.
Misalnya, menggunakannya pada definisi pertama fib :

[<TailCall>]
let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

akan memicu peringatan kompilator tentang dua panggilan rekursif non-ekor.

Fungsi Rekursif Timbal Balik

Terkadang fungsi merupakan rekursif timbal balik, yang berarti bahwa panggilan membentuk lingkaran, di mana satu fungsi memanggil fungsi lain yang pada gilirannya memanggil yang pertama, dengan sejumlah panggilan di antaranya. Anda harus menentukan fungsi tersebut bersama-sama dalam satu ikatan let, menggunakan kata kunci and untuk menautkannya.

Contoh berikut menunjukkan dua fungsi yang melakukan rekursif timbal balik.

let rec Even x = if x = 0 then true else Odd(x - 1)
and Odd x = if x = 0 then false else Even(x - 1)

Nilai rekursif

Anda juga dapat menentukan nilai ikatan-let menjadi rekursif. Hal ini terkadang dilakukan untuk pengelogan. Dengan F# 5 dan fungsi nameof, Anda dapat melakukan ini:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Lihat juga

• Fungsi