Εισαγωγή
Αναδρομή ουράς
Μια συνάρτηση είναι αναδρομική ουράς αν το τελευταίο πράγμα που εκτελεί η συνάρτηση είναι μια κλήση στον εαυτό της.
Κάθε φορά που καλείται μια συνάρτηση, ένα πλαίσιο στοίβας με τις τοπικές μεταβλητές και τα ορίσματά της τοποθετείται στην κορυφή της στοίβας κλήσεων συναρτήσεων.
Όταν μια συνάρτηση επιστρέφει, το πλαίσιο στοίβας αφαιρείται από τη στοίβα.
Οι αναδρομικές συναρτήσεις ουράς επιτρέπουν τη βελτιστοποίηση κλήσης ουράς (ή εξάλειψη κλήσης ουράς).
Είναι μια βελτιστοποίηση που επιτρέπει την επαναχρησιμοποίηση του τελευταίου πλαισίου στοίβας από την επόμενη κλήση συνάρτησης, όταν είναι βέβαιο ότι η προηγούμενη συνάρτηση δεν το χρειάζεται πια.
Αυτό μετριάζει τους προβληματισμούς για υπερχείλιση της στοίβας κλήσεων συναρτήσεων, μια κατάσταση όπου υπάρχουν τόσα πολλά πλαίσια στη στοίβα κλήσεων ώστε να μην έχει απομείνει μνήμη για να δημιουργηθεί άλλο.
Βελτιστοποίηση κλήσης ουράς στην Elm
Κάτω από ορισμένες συνθήκες, ο μεταγλωττιστής της Elm μπορεί να εκτελέσει αυτόματα μια βελτιστοποίηση κλήσης ουράς όταν μεταγλωττίζει σε JavaScript.
Η βελτιστοποίηση μπορεί να συμβεί για μια αναδρομική συνάρτηση όταν η τελευταία πράξη σε έναν κλάδο γίνεται καλώντας την ίδια τη συνάρτηση σε μια απλή εφαρμογή συνάρτησης.
Ας δούμε μερικά παραδείγματα:
factorial : Int -> Int
factorial n =
if n <= 1 then
n
else
n * factorial (n-1)
Η παραπάνω υλοποίηση δεν είναι αναδρομική ουράς, γιατί η τελευταία πράξη στον κλάδο else είναι ένας πολλαπλασιασμός n *.
factorial : Int -> Int
factorial n =
factorialHelper n n
factorialHelper : Int -> Int -> Int
factorialHelper n resultSoFar =
if n <= 1 then
resultSoFar
else
factorialHelper (n-1) (n * resultSoFar)
Η παραπάνω υλοποίηση είναι αναδρομική ουράς και θα βελτιστοποιηθεί, γιατί η τελευταία πράξη στον κλάδο else είναι η factorialHelper που καλεί τον εαυτό της.
Κάτι τέτοιο δεν θα ήταν δυνατό για μια συνάρτηση με υπογραφή τύπου Int -> Int, και στην πράξη η βελτιστοποίηση κλήσης ουράς επιτυγχάνεται συχνά ορίζοντας βοηθητικές συναρτήσεις.
Οδηγίες
Η Piper ψήνει πίτες με πάθος.
Κανείς δεν ξέρει αν ασχολήθηκε με το ψήσιμο πιτών εξαιτίας του ονόματός της, ή αν άλλαξε το όνομά της για να ταιριάζει με το χόμπι της.
Εκ πρώτης όψεως, το δεύτερο δε φαίνεται και πολύ πιθανό, αλλά βλέπεις, η Piper τρέφει απόλυτο πάθος για τις πίτες.
Πάντα πειραματίζεται στην κουζίνα, τροποποιεί τις συνταγές της, βελτιώνει την τέχνη της, προς απόλυτη χαρά των φίλων της.
Το πιο πρόσφατο πάθος της;
Να ψήνει πίτες όσο πιο κυκλικές γίνεται, μέχρι μαθηματικής τελειότητας, με τη βοήθεια του αγαπημένου της αριθμού, το μάντεψες: το π.
Η Piper βρήκε έναν υπέροχο τύπο για να υπολογίζει το π επαναληπτικά, τον μετασχηματισμό σύγκλισης Newton/Euler:
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Βοήθησε την Piper να ψήσει τη μαθηματικά τέλεια πίτα της υπολογίζοντας το π.
1. Παραγοντικό
Ας κάνουμε πρώτα μια προθέρμανση.
Ο τελεστής του παραγοντικού, που συνήθως γράφεται !, ορίζεται ως
0! = 1
n! = 1 * 2 * 3 * ... * n
Όρισε τη συνάρτηση factorial, η οποία θα υπολογίζει το παραγοντικό με αναδρομή ουράς.
factorial 4
-- 24
2. Διπλό Παραγοντικό
Ο τελεστής του διπλού παραγοντικού, που συνήθως γράφεται !!, ορίζεται ως
0!! = 1
n!! = 1 * 3 * 5 * ... * n (for odd n)
n!! = 2 * 4 * 6 * ... * n (for even n)
Όρισε τη συνάρτηση doubleFactorial, η οποία θα υπολογίζει το παραγοντικό με αναδρομή ουράς.
factorial 5
-- 15
factorial 6
-- 48
Όρισε τη συνάρτηση pipersPi, η οποία θα προσεγγίζει το π χρησιμοποιώντας έναν συγκεκριμένο αριθμό όρων από τον τύπο του μετασχηματισμού σύγκλισης Newton/Euler, με αναδρομή ουράς.
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Ας υπολογίσουμε μαζί τον πρώτο όρο.
Για ανώτατο όριο 0 (αντί για άπειρο), παίρνουμε:
π / 2 ≈ Sum for k from 0 to 0 of ( k! ) / ( 2 * k + 1 )!!
π / 2 ≈ ( 0! ) / ( 2 * 0 + 1 )!!
π / 2 ≈ 0! / 0!!
π / 2 ≈ 1 / 1
π / 2 ≈ 1
π ≈ 2
Κάθε επιπλέον όρος θα βελτιώνει την προσέγγιση.
pipersPi 0
-- 2.0
pipersPi 1
-- 2.6666666
Άσκηση εκμάθησης
