Αναδρομή σε

Σχετικά με την έννοια Αναδρομή

Η ικανότητα ενός πράγματος να ορίζεται με βάση τον εαυτό του ονομάζεται αναδρομή. Στην F#, η αναδρομή συναντάται πιο συχνά στις αναδρομικές συναρτήσεις, οι οποίες είναι συναρτήσεις που καλούν τον εαυτό τους.

Μια αναδρομική συνάρτηση χρειάζεται να έχει τουλάχιστον μία βασική περίπτωση και τουλάχιστον μία αναδρομική περίπτωση. Μια βασική περίπτωση επιστρέφει μια τιμή χωρίς να καλέσει ξανά τη συνάρτηση. Μια αναδρομική περίπτωση καλεί ξανά τη συνάρτηση, τροποποιώντας την είσοδο ώστε κάποια στιγμή να ταιριάξει με τη βασική περίπτωση.

Οι αναδρομικές συναρτήσεις ορίζονται όπως οι συνηθισμένες συναρτήσεις, αλλά με τον τροποποιητή rec. Χωρίς αυτόν τον τροποποιητή, μια συνάρτηση δεν θα μπορεί να καλέσει τον εαυτό της και οποιαδήποτε προσπάθεια να το κάνει θα έχει ως αποτέλεσμα ένα σφάλμα μεταγλώττισης. Η αναδρομή, επομένως, πρέπει να ενεργοποιηθεί ρητά.

let rec factorial x =
    // Base case
    if x = 1 then
        1
    // Recursive case
    else
        x * factorial (x - 1)

Οι λίστες συχνά επεξεργάζονται αναδρομικά. Για παράδειγμα, να πώς μπορείς να χρησιμοποιήσεις την αναδρομή για να υπολογίσεις το μήκος μιας λίστας:

let rec length list =
    match list with
    | [] -> 0
    | x::xs -> 1 + length xs

length [1; 2; 3]
// => 3

Πολλές από τις ενσωματωμένες συναρτήσεις ορίζονται αναδρομικά.

Ένα πιθανό πρόβλημα με τις αναδρομικές συναρτήσεις είναι ότι κάθε (αναδρομική) κλήση συνάρτησης προκαλεί δεσμεύσεις μνήμης στη στοίβα, προκαλώντας την αύξησή της. Καθώς η στοίβα έχει περιορισμένη ποσότητα μνήμης, συναρτήσεις που χρησιμοποιούν πολλές αναδρομικές κλήσεις μπορεί να έχουν ως αποτέλεσμα να πεταχτεί μια StackOverflowException. Πόσες αναδρομικές κλήσεις θα προκαλέσουν αυτή τη συμπεριφορά εξαρτάται από πολλούς παράγοντες, όπως η διαθέσιμη μνήμη στη στοίβα και πόσα δεδομένα καταλαμβάνει κάθε κλήση συνάρτησης στη στοίβα.

Ο καλύτερος τρόπος για να αποτρέψεις τις αναδρομικές συναρτήσεις από το να υπερχειλίσουν τη στοίβα είναι να τις γράψεις ως συναρτήσεις με αναδρομή ουράς. Όταν μια συνάρτηση έχει αναδρομή ουράς, ο μεταγλωττιστής μπορεί να βελτιστοποιήσει την έξοδό της έτσι ώστε να μην υπάρχουν επιπλέον δεσμεύσεις μνήμης στη στοίβα για κάθε αναδρομική κλήση συνάρτησης. Ο μοναδικός κανόνας για τις συναρτήσεις με αναδρομή ουράς είναι ότι το αποτέλεσμα μιας αναδρομικής κλήσης συνάρτησης πρέπει να επιστρέφεται απευθείας από τη συνάρτηση, δεν πρέπει να υπάρχει επιπλέον κώδικας που να επεξεργάζεται το αποτέλεσμα της αναδρομικής κλήσης. Ο πιο συνηθισμένος τρόπος για να γίνει αυτό είναι η δημιουργία μιας βοηθητικής συνάρτησης που δέχεται ένα επιπλέον όρισμα συσσωρευτή, το οποίο ενημερώνεται σε κάθε αναδρομική κλήση και επιστρέφεται όταν ολοκληρωθεί η αναδρομή. Αυτή η σελίδα μπαίνει σε μεγάλη λεπτομέρεια για το πώς ο μεταγλωττιστής επεξεργάζεται τις συναρτήσεις με αναδρομή ουράς.

Ακολουθεί μια έκδοση με αναδρομή ουράς της συνάρτησης μήκους λίστας:

let rec lengthRecursive acc list =
    match list with
    | [] -> acc
    | x::xs -> lengthRecursive (acc + 1) xs

let length list = lengthRecursive 0 list

Είναι αρκετά συνηθισμένο να ορίζεται η αναδρομική βοηθητική συνάρτηση ως εμφωλευμένη συνάρτηση, κάτι που κρύβει την αναδρομική φύση της συνάρτησης από όποιον την καλεί:

let length list =
    let rec lengthRecursive acc remainder =
        match remainder with
        | [] -> acc
        | x::xs -> lengthRecursive (acc + 1) xs

    lengthRecursive 0 list

Η F# υποστηρίζει αναδρομικούς τύπους μέσω τύπων διακριτών ενώσεων. Ένας αναδρομικός τύπος διακριτής ένωσης έχει μία ή περισσότερες από τις περιπτώσεις του να αναφέρονται στον ίδιο τον τύπο διακριτής ένωσης στα δεδομένα τους. Όπως οι αναδρομικές συναρτήσεις, έτσι και οι αναδρομικοί τύποι πρέπει να έχουν μια βασική περίπτωση. Σε αντίθεση με τις αναδρομικές συναρτήσεις, οι αναδρομικοί τύποι δεν χρησιμοποιούν τη λέξη-κλειδί rec.

type RussianDoll =
    | Doll                 // Base case
    | Layer of RussianDoll // Recursive case

Ακολουθεί μια συνάρτηση (χωρίς αναδρομή ουράς) για να δουλέψεις με τον παραπάνω αναδρομικό τύπο:

let layers doll =
    match doll with
    | Doll -> 0 // Base case
    | Layer innerDoll -> 1 + layers innerDoll // Recursive case

layers (Layer Doll)
// => 1