Η πίτα της Piper

Αναδρομή

Μια συνάρτηση είναι αναδρομική όταν καλεί τον εαυτό της.

Μια βασική διαφορά ανάμεσα σε μια κλήση συνάρτησης και έναν βρόχο είναι ότι η κλήση μιας συνάρτησης ωθεί στη στοίβα τη διεύθυνση επιστροφής. Αυτό σημαίνει ότι μια αναδρομική συνάρτηση απαιτεί συνήθως περισσότερο χώρο στη στοίβα από έναν ισοδύναμο βρόχο.

Κατά συνέπεια, μια συνάρτηση που συνεχίζει να καλεί τον εαυτό της μπορεί τελικά να εξαντλήσει όλο τον χώρο της στοίβας. Αυτό ονομάζεται υπερχείλιση στοίβας.

Γι' αυτό κάθε αναδρομική συνάρτηση πρέπει να έχει τουλάχιστον μία βασική περίπτωση, δηλαδή μια κατάσταση όπου η συνάρτηση επιστρέφει χωρίς να καλέσει τον εαυτό της. Κάθε αναδρομική κλήση πρέπει τελικά να φτάνει σε μια βασική περίπτωση.

Για παράδειγμα, η συνάρτηση παραγοντικού n! = n * (n - 1) * ... * 1 μπορεί να οριστεί αναδρομικά με το 1 ως βασική περίπτωση:

factorial:
    ; the argument `n` is passed on `rdi`
    ; the factorial will be returned on `rax`

    cmp rdi, 1
    jle .base_case     ; base case -> if rdi <= 1, return 1

    push rdi           ; save n
    dec rdi            ; rdi = n - 1
    call factorial     ; recursive call, rax = (n - 1)!
    pop rdi            ; restore n
    imul rax, rdi      ; rax = n * (n - 1)! = n!
    ret
.base_case:
    mov rax, 1
    ret

Πρόσεξε ότι η factorial πρέπει να κάνει push rdi πριν την αναδρομή και pop rdi μετά. Αυτό συμβαίνει επειδή χρειάζεται ακόμα το n όταν επιστρέψει η αναδρομική κλήση, για να υπολογίσει το n * (n-1)!.

Πρόσεξε επίσης ότι η χρήση ενός καταχωρητή που διατηρείται από τον καλούμενο δεν θα έλυνε αυτό το πρόβλημα.

Αν και μια αναδρομική συνάρτηση είναι δυνάμει καλών του εαυτού της, είναι και η ίδια καλούμενη κάποιας άλλης συνάρτησης. Αυτό σημαίνει ότι η συνάρτηση πρέπει επίσης να διατηρεί τους καταχωρητές που διατηρεί ο καλούμενος πριν τους χρησιμοποιήσει, και να επαναφέρει την τιμή τους αφού χρησιμοποιηθούν. Αυτό γίνεται συνήθως με μια ακολουθία push/pop, όπως έχουμε δει σε μια προηγούμενη έννοια.

Εφόσον κάθε πλαίσιο μιας αναδρομικής συνάρτησης, με εξαίρεση τη βασική περίπτωση, είναι και καλών που πρέπει να διατηρήσει τις δικές του τοπικές μεταβλητές, αυτή η ακολουθία push/pop πρέπει να επαναλαμβάνεται για κάθε πλαίσιο. Ακόμα και η αποθήκευση της μεταβλητής απευθείας στη στοίβα, χωρίς τη χρήση καταχωρητών, θα κόστιζε και πάλι τα ίδια 8 bytes ανά πλαίσιο.

Αυτό σημαίνει ότι κάθε αναδρομική κλήση προσθέτει 8 bytes στη στοίβα για τη διεύθυνση επιστροφής που ωθεί το call, συν 8 bytes για κάθε τοπική μεταβλητή που πρέπει να αποθηκεύσει. Η συνάρτηση θα συνεχίζει να προσθέτει αυτά τα bytes στη στοίβα σε κάθε πλαίσιο, μέχρι να φτάσει στη βασική περίπτωση. Μόνο τότε αρχίζει να ξετυλίγεται με αντίστροφη σειρά, με κάθε αναδρομική κλήση να χρησιμοποιεί όσα pop χρειάζεται και έπειτα ένα ret.

Για παράδειγμα, αν η factorial καλούνταν με όρισμα 10, θα καλούσε τον εαυτό της εννέα φορές πριν φτάσει στη βασική περίπτωση του 1. Σε εκείνο το σημείο, θα είχαν χρησιμοποιηθεί 144 bytes για την αποθήκευση του n (8 bytes) και της διεύθυνσης επιστροφής (8 bytes) για κάθε προηγούμενο πλαίσιο.

Ουριαία Κλήση

Σε ορισμένες περιπτώσεις, μια συνάρτηση δεν εκτελεί άλλη εργασία αφού καλέσει μια άλλη και πριν επιστρέψει.

Σκέψου, για παράδειγμα:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    call times_three
    ret

Η συνάρτηση triple_of_square:

• πολλαπλασιάζει το όρισμα που της περνιέται (στο rdi) με τον εαυτό του, παίρνοντας το τετράγωνό του;
• στη συνέχεια καλεί τη times_three, η οποία επιστρέφει το τριπλάσιο του ορίσματος που της περνιέται.

Ως αποτέλεσμα, η triple_of_square επιστρέφει 3*x², όπου x είναι το όρισμά της, περασμένο στο rdi.

Πρόσεξε ότι δεν εκτελείται καμία εργασία στη triple_of_square αφού καλέσει τη times_three, η συνάρτηση απλώς επιστρέφει. Σε μια τέτοια περίπτωση, αντί να χρησιμοποιήσει call, μια συνάρτηση μπορεί να χρησιμοποιήσει jmp και να μεταφέρει την εκτέλεση στην καλούμενη συνάρτηση:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    jmp times_three

Αυτό ονομάζεται ουριαία κλήση.

Το κύριο πλεονέκτημα μιας ουριαίας κλήσης είναι ότι αποφεύγει το επιπλέον κόστος του call. Ένα call ωθεί μια διεύθυνση επιστροφής στη στοίβα, και για να επιστρέψει ο έλεγχος σε εκείνο το σημείο χρειάζεται ένα αντίστοιχο ret.

Μια ουριαία κλήση τα παραλείπει και τα δύο: δεν υπάρχει διεύθυνση επιστροφής για ώθηση, ούτε επιπλέον ret για ταίριασμα, μόνο το δικό της ret της καλούμενης συνάρτησης.

Ουριαία Αναδρομή

Μια ουριαία κλήση είναι ιδιαίτερα χρήσιμη για αναδρομικές συναρτήσεις που μπορεί να καλέσουν τον εαυτό τους πολλές φορές πριν επιστρέψουν.

Ωστόσο, δεν μπορεί να μετατραπεί άμεσα κάθε αναδρομική κλήση σε ουριαία κλήση. Εφόσον ένα jmp μεταφέρει τον έλεγχο στην καλούμενη συνάρτηση, ο καλών δεν μπορεί να εκτελέσει άλλη εργασία μετά την ουριαία κλήση.

Για παράδειγμα, η προηγούμενη συνάρτηση factorial δεν είναι ουριαία αναδρομική. Μετά την αναδρομική κλήση, χρειάζεται ακόμα να πολλαπλασιάσει το αποτέλεσμα με το τρέχον n, χρησιμοποιώντας το imul rax, rdi.

Σε τέτοιες περιπτώσεις, είναι μερικές φορές δυνατό να χρησιμοποιηθεί ένας συσσωρευτής που θα συλλέγει τα μερικά αποτελέσματα και θα επιστραφεί στο τέλος. Για παράδειγμα, μπορούμε να ορίσουμε μια factorial_helper που κάνει το μεγαλύτερο μέρος της δουλειάς, και στη συνέχεια η factorial αρχικοποιεί έναν συσσωρευτή και μεταφέρει τον έλεγχο στη factorial_helper:

factorial_helper:
    ; the argument `n` is passed on `rdi`
    ; `rax` is used as an accumulator and will be returned at the end

    cmp rdi, 1
    jle .base_case

    imul rax, rdi        ; we accumulate the partial result on `rax`
    dec rdi              ; rdi = n - 1
    jmp factorial_helper ; tail call to accumulate (n - 1)!
.base_case:
    ret                  ; returns the factorial already accumulated on `rax`

factorial:
    mov rax, 1           ; initial value for the accumulator
    jmp factorial_helper ; tail call

Εφόσον δεν εκτελείται άλλη εργασία μετά την αναδρομική κλήση, δεν χρειάζεται πια να αποθηκεύουμε το rdi. Δεν υπάρχει call ή push rdi, οπότε κάθε αναδρομική επανάληψη προσθέτει 0 bytes στη στοίβα: δεν χρησιμοποιείται επιπλέον χώρος στη στοίβα. Αυτή η εκδοχή μπορεί να χειριστεί οσοδήποτε μεγάλο n χωρίς να υπερχειλίσει τη στοίβα. Είναι ταυτόχρονα πιο αποδοτική και πιο ασφαλής.

Σε ορισμένες περιπτώσεις, με αναδιάταξη της σειράς των συναρτήσεων, μπορεί να αποφευχθεί ακόμα και το jmp προς τη βοηθητική συνάρτηση. Για παράδειγμα, οι factorial και triple_of_square μπορούν να ξαναγραφτούν ως εξής:

factorial:
    mov rax, 1
factorial_helper:
    cmp rdi, 1
    jle .base_case

    imul rax, rdi
    dec rdi
    jmp factorial_helper
.base_case:
    ret

triple_of_square:
    imul rdi, rdi
times_three:
    imul rax, rdi, 3
    ret

Στο παραπάνω απόσπασμα, η εκτέλεση της factorial περνά απευθείας στη factorial_helper. Το ίδιο συμβαίνει με τη triple_of_square και τη times_three. Και στις δύο περιπτώσεις, η εκτέλεση συνεχίζει διαδοχικά και φαίνεται πως η ουριαία συνάρτηση είναι απλώς μια τοπική ετικέτα μέσα στην "κύρια" συνάρτηση.

Στην πραγματικότητα, δεν υπάρχει ουσιαστική διαφορά ανάμεσα σε μια τοπική ετικέτα και μια συνάρτηση. Η assembly x86-64 δεν δίνει ειδική μεταχείριση σε κανένα από αυτά, είναι απλώς διευθύνσεις σε ένα τμήμα με εκτελέσιμο κώδικα, όπως το section .text.

Έτσι, μια ουριαία αναδρομική συνάρτηση μπορεί να θεωρηθεί ουσιαστικά το ίδιο με έναν βρόχο όπου η αναδρομική κλήση πηδά πίσω στην αρχή, και η βασική περίπτωση είναι η συνθήκη που τερματίζει τον βρόχο.