Fungsi Rekursif: Kata Kunci rec

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

Sintaksis

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

Komentar

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

Contoh berikut menunjukkan fungsi rekursif yang menghitung angka Fibonacci ke-n menggunakan definisi matematika.

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

Nota

Dalam praktiknya, kode seperti sampel sebelumnya tidak ideal karena tidak perlu mengkomputasi ulang nilai yang telah dihitung. Ini karena tidak rekursif ekor, yang dijelaskan lebih lanjut dalam artikel ini.

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

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

let namun, pengikatan dalam kelas tidak secara implisit rekursif. Semua letfungsi terikat memerlukan rec kata kunci.

Rekursi ekor

Untuk beberapa fungsi rekursif, perlu untuk merefaktor definisi yang lebih "murni" ke definisi yang rekursif ekor. Ini mencegah rekomputasi yang tidak perlu. Misalnya, generator nomor 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 praktik. 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 akumulasi ke panggilan rekursif.
• Pemeriksaan nilai n untuk mengembalikan akumulator tertentu.

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

Alasan mengapa ini ekor-rekursif adalah karena panggilan rekursif tidak perlu menyimpan nilai apa pun pada tumpukan panggilan. Semua nilai perantara yang dihitung diakumulasikan melalui input ke fungsi dalam. Ini juga memungkinkan pengkompilasi F# untuk mengoptimalkan kode agar sama cepatnya seolah-olah Anda telah menulis sesuatu seperti perulangan while .

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

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 Bersama

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

Contoh berikut menunjukkan dua fungsi yang saling rekursif.

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 letnilai -bound menjadi rekursif. Ini kadang-kadang dilakukan untuk pengelogan. Dengan F# 5 dan fungsinya nameof , Anda dapat melakukan ini:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Lihat juga

• Fungsi