Σε αυτό το άρθρο, θα μάθετε να δημιουργείτε αναδρομικές συναρτήσεις. μια συνάρτηση που καλείται. Επίσης, θα μάθετε για την αναδρομική λειτουργία της ουράς.
Μια συνάρτηση που ονομάζεται γνωστή ως αναδρομική συνάρτηση. Και, αυτή η τεχνική είναι γνωστή ως επανάληψη.
Ένα παράδειγμα φυσικού κόσμου θα ήταν να τοποθετηθούν δύο παράλληλοι καθρέπτες το ένα απέναντι στο άλλο. Οποιοδήποτε αντικείμενο μεταξύ τους θα ανακλάται αναδρομικά.
Πώς λειτουργεί η αναδρομή στον προγραμματισμό;
fun main (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Εδώ, η recurse()συνάρτηση καλείται από το recurse()ίδιο το σώμα της λειτουργίας. Δείτε πώς λειτουργεί αυτό το πρόγραμμα:
Εδώ, η αναδρομική κλήση συνεχίζεται για πάντα προκαλώντας άπειρη αναδρομή.
Για να αποφύγετε την άπειρη αναδρομή, εάν… αλλιώς (ή παρόμοια προσέγγιση) μπορεί να χρησιμοποιηθεί όπου ένα υποκατάστημα κάνει την αναδρομική κλήση και άλλο όχι.
Παράδειγμα: Βρείτε παραγοντικά ενός αριθμού χρησιμοποιώντας το Recursion
fun main(args: Array) ( val number = 4 val result: Long result = factorial(number) println("Factorial of $number = $result") ) fun factorial(n: Int): Long ( return if (n == 1) n.toLong() else n*factorial(n-1) )
Όταν εκτελείτε το πρόγραμμα, η έξοδος θα είναι:
Παράγοντα του 4 = 24
Πώς λειτουργεί αυτό το πρόγραμμα;
Η αναδρομική κλήση της factorial()συνάρτησης μπορεί να εξηγηθεί στο ακόλουθο σχήμα:
Ακολουθούν τα βήματα:
factorial (4) // 1η συνάρτηση. Επιχειρησιακό: 4 4 * factorial (3) // 2η συνάρτηση. Όρισμα: 3 4 * (3 * factorial (2)) // 3η συνάρτηση. Όρισμα: 2 4 * (3 * (2 * factorial (1))) // 4η κλήση λειτουργίας. Όρισμα: 1 4 * (3 * (2 * 1)) 24
Επανάληψη ουράς Kotlin
Η αναδρομή ουράς είναι μια γενική ιδέα παρά το χαρακτηριστικό της γλώσσας Kotlin. Ορισμένες γλώσσες προγραμματισμού, συμπεριλαμβανομένου του Kotlin, το χρησιμοποιούν για τη βελτιστοποίηση αναδρομικών κλήσεων, ενώ άλλες γλώσσες (π.χ. Python) δεν τις υποστηρίζουν.
Τι είναι η ουρά αναδρομής;
Στην κανονική αναδρομή, πραγματοποιείτε πρώτα όλες τις αναδρομικές κλήσεις και υπολογίζετε το αποτέλεσμα από τις τιμές επιστροφής επιτέλους (όπως φαίνεται στο παραπάνω παράδειγμα). Ως εκ τούτου, δεν λαμβάνετε αποτέλεσμα μέχρι να γίνουν όλες οι αναδρομικές κλήσεις.
Στην ουρά αναδρομής, οι υπολογισμοί εκτελούνται πρώτα και μετά εκτελούνται αναδρομικές κλήσεις (η αναδρομική κλήση μεταφέρει το αποτέλεσμα του τρέχοντος βήματος στην επόμενη αναδρομική κλήση). Αυτό καθιστά την αναδρομική κλήση ισοδύναμη με βρόχο και αποφεύγει τον κίνδυνο υπερχείλισης στοίβας.
Κατάσταση για αναδρομή ουράς
Μια αναδρομική συνάρτηση είναι κατάλληλη για αναδρομή ουράς εάν η συνάρτηση καλεί τον εαυτό της είναι η τελευταία λειτουργία που εκτελεί. Για παράδειγμα,
Παράδειγμα 1: Δεν πληροί τις προϋποθέσεις για αναδρομή ουράς, επειδή η συνάρτηση δεν n*factorial(n-1)είναι η τελευταία λειτουργία.
fun factorial (n: Int): Long (if (n == 1) (return n.toLong ()) other (return n * factorial (n - 1)))
Παράδειγμα 2: Επιλέξιμο για αναδρομή ουράς επειδή η λειτουργία κλήσης από μόνη της fibonacci(n-1, a+b, a)είναι η τελευταία λειτουργία.
fun fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b other fibonacci (n-1, a + b, a))
Για να πείτε στον μεταγλωττιστή να εκτελέσει επαναληπτική ουρά στο Kotlin, πρέπει να επισημάνετε τη λειτουργία με tailrecτροποποιητή.
Παράδειγμα: Επανάληψη ουράς
import java.math.BigInteger fun main(args: Array) ( val n = 100 val first = BigInteger("0") val second = BigInteger("1") println(fibonacci(n, first, second)) ) tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger ( return if (n == 0) a else fibonacci(n-1, b, a+b) )
Όταν εκτελείτε το πρόγραμμα, η έξοδος θα είναι:
354224848179261915075
Αυτό το πρόγραμμα υπολογίζει τον 100 ο όρο της σειράς Fibonacci. Δεδομένου ότι η έξοδος μπορεί να είναι ένας πολύ μεγάλος ακέραιος αριθμός, έχουμε εισαγάγει την κλάση BigInteger από την τυπική βιβλιοθήκη Java.
Εδώ, η συνάρτηση fibonacci()επισημαίνεται με tailrecτροποποιητή και η συνάρτηση είναι κατάλληλη για αναδρομική κλήση ουράς. Ως εκ τούτου, ο μεταγλωττιστής βελτιστοποιεί την αναδρομή σε αυτήν την περίπτωση.
Εάν προσπαθείτε να βρείτε το 20000 Θ όρος (ή οποιοδήποτε άλλο μεγάλο ακέραιο) της σειράς Fibonacci χωρίς τη χρήση αναδρομής ουράς, ο compiler θα ρίξει java.lang.StackOverflowErrorεξαίρεση. Ωστόσο, το παραπάνω πρόγραμμα λειτουργεί καλά. Είναι επειδή έχουμε χρησιμοποιήσει αναδρομή ουράς που χρησιμοποιεί αποτελεσματική έκδοση με βάση βρόχο αντί για παραδοσιακή αναδρομή.
Παράδειγμα: Factorial χρησιμοποιώντας ουρά αναδρομής
Το παράδειγμα για τον υπολογισμό των παραγόντων ενός αριθμού στο παραπάνω παράδειγμα (πρώτο παράδειγμα) δεν μπορεί να βελτιστοποιηθεί για αναδρομή ουράς. Εδώ είναι ένα διαφορετικό πρόγραμμα για την εκτέλεση της ίδιας εργασίας.
fun main(args: Array) ( val number = 5 println("Factorial of $number = $(factorial(number))") ) tailrec fun factorial(n: Int, run: Int = 1): Long ( return if (n == 1) run.toLong() else factorial(n-1, run*n) )
Όταν εκτελείτε το πρόγραμμα, η έξοδος θα είναι:
Παράγοντα 5 = 120
Ο μεταγλωττιστής μπορεί να βελτιστοποιήσει την αναδρομή σε αυτό το πρόγραμμα, καθώς η αναδρομική συνάρτηση είναι κατάλληλη για αναδρομή ουράς και έχουμε χρησιμοποιήσει tailrecτροποποιητή που λέει στον μεταγλωττιστή να βελτιστοποιήσει την αναδρομή.
