Σύγχρονη κατανόηση της αναδρομής: ορισμός της λειτουργικότητας και πρόσβαση σε αυτήν από έξω και από αυτήν τη λειτουργικότητα. Πιστεύεται ότι η αναδρομή γεννήθηκε από τους μαθηματικούς: παραγοντικός υπολογισμός, άπειρες σειρές, φράκταλ, συνεχόμενα κλάσματα … Ωστόσο, η αναδρομή μπορεί να βρεθεί παντού. Οι αντικειμενικοί φυσικοί νόμοι «θεωρούν» την αναδρομή ως κύριο αλγόριθμο και μορφή έκφρασης (ύπαρξης) όχι τόσο των αντικειμένων του υλικού κόσμου, αλλά γενικά τον κύριο αλγόριθμο κίνησης.
Άνθρωποι διαφόρων ειδικοτήτων σε διάφορους τομείς της επιστήμης και της τεχνολογίας χρησιμοποιούν τον αναδρομικό αλγόριθμο f (x), όπου "x ~/=f (x)". Μια συνάρτηση που αυτοαποκαλείται είναι μια ισχυρή λύση, αλλά ο σχηματισμός και η κατανόηση αυτής της λύσης είναι, στις περισσότερες περιπτώσεις, πολύ δύσκολο έργο.
Στην αρχαιότητα, η αναδρομή χρησιμοποιήθηκε για την αύξηση του χώρου του παλατιού. Μέσω ενός συστήματος καθρεφτών που κατευθύνονται ο ένας στον άλλο, μπορείτε να δημιουργήσετε εκπληκτικά τρισδιάστατα χωρικά εφέ. Αλλά είναι τόσο εύκολο να καταλάβουμε πώςρυθμίζω αυτούς τους καθρέφτες; Είναι ακόμη πιο δύσκολο να προσδιοριστεί πού βρίσκεται ένα σημείο στο διάστημα, που αντανακλάται μέσα από πολλούς καθρέφτες.
Αναδρομή, αναδρομικοί αλγόριθμοι: νόημα και σύνταξη
Το πρόβλημα, το οποίο διατυπώνεται με την επανάληψη μιας ακολουθίας πράξεων, μπορεί να λυθεί αναδρομικά. Ένας απλός αλγόριθμος (υπολογισμός τετραγωνικής εξίσωσης, σενάριο για συμπλήρωση μιας ιστοσελίδας με πληροφορίες, ανάγνωση αρχείου, αποστολή μηνύματος…) δεν απαιτεί αναδρομή.
Βασικές διαφορές του αλγορίθμου που επιτρέπει μια αναδρομική λύση:
- υπάρχει ένας αλγόριθμος που πρέπει να εκτελεστεί πολλές φορές.
- Ο αλγόριθμος χρειάζεται δεδομένα που αλλάζουν κάθε φορά;
- ο αλγόριθμος δεν χρειάζεται να αλλάζει κάθε φορά.
- υπάρχει μια τελική συνθήκη: ο αλγόριθμος είναι αναδρομικός - όχι άπειρος.
Γενικά, δεν μπορεί να υποστηριχθεί ότι η εφάπαξ εκτέλεση είναι απαραίτητη προϋπόθεση για την απουσία λόγου για αναδρομή. Δεν μπορείτε επίσης να απαιτήσετε μια υποχρεωτική τελική συνθήκη: οι άπειρες αναδρομές έχουν το δικό τους εύρος.
Ο αλγόριθμος είναι αναδρομικός: όταν μια ακολουθία πράξεων εκτελείται επανειλημμένα, σε δεδομένα που αλλάζουν κάθε φορά και δίνουν ένα νέο αποτέλεσμα κάθε φορά.
Τύπος αναδρομής
Η μαθηματική κατανόηση της αναδρομής και το ανάλογό της στον προγραμματισμό διαφέρουν. Τα μαθηματικά, αν και υπάρχουν σημάδια προγραμματισμού, αλλά ο προγραμματισμός είναι μαθηματικά πολύ υψηλότερης τάξης.
Ένας καλογραμμένος αλγόριθμος είναι σαν ένας καθρέφτης της νόησης του συγγραφέα του. Γενικόςο τύπος αναδρομής στον προγραμματισμό είναι "f(x)", όπου το "x ~/=f(x)" έχει τουλάχιστον δύο ερμηνείες. Εδώ "~" είναι η ομοιότητα ή η απουσία του αποτελέσματος και "=" είναι η παρουσία του αποτελέσματος της συνάρτησης.
Πρώτη επιλογή: δυναμική δεδομένων.
- Η συνάρτηση "f(x)" έχει έναν αναδρομικό και αμετάβλητο αλγόριθμο;
- "x" και το αποτέλεσμα "f(x)" έχουν νέες τιμές κάθε φορά, το αποτέλεσμα "f(x)" είναι η νέα παράμετρος "x" αυτής της συνάρτησης.
Δεύτερη επιλογή: δυναμική κώδικα.
- η συνάρτηση "f(x)" έχει αρκετούς αλγόριθμους που βελτιώνουν (αναλύουν) τα δεδομένα.
- ανάλυση δεδομένων - ένα μέρος του κώδικα και η υλοποίηση αναδρομικών αλγορίθμων που εκτελούν την επιθυμητή ενέργεια - το δεύτερο μέρος του κώδικα;
- το αποτέλεσμα της συνάρτησης "f(x)" δεν είναι.
Κανένα αποτέλεσμα δεν είναι φυσιολογικό. Ο προγραμματισμός δεν είναι μαθηματικά, εδώ το αποτέλεσμα δεν χρειάζεται να είναι ρητά παρόν. Μια αναδρομική συνάρτηση μπορεί απλώς να αναλύσει τοποθεσίες και να συμπληρώσει τη βάση δεδομένων ή να δημιουργήσει αντικείμενα σύμφωνα με την εισερχόμενη είσοδο.
Δεδομένα και αναδρομή
Ο προγραμματισμός αναδρομικών αλγορίθμων δεν αφορά τον υπολογισμό ενός παραγοντικού, στον οποίο η συνάρτηση λαμβάνει κάθε φορά μια δεδομένη τιμή που είναι μία μεγαλύτερη ή μικρότερη από μία - η επιλογή υλοποίησης εξαρτάται από την προτίμηση του προγραμματιστή.
Δεν έχει σημασία πόσο το παραγοντικό "8!",αλγόριθμος που ακολουθεί αυστηρά αυτόν τον τύπο.
Η επεξεργασία πληροφοριών είναι «μαθηματικά» εντελώς διαφορετικής σειράς. Οι αναδρομικές συναρτήσεις και οι αλγόριθμοι εδώ λειτουργούν με γράμματα, λέξεις, φράσεις, προτάσεις και παραγράφους. Κάθε επόμενο επίπεδο χρησιμοποιεί το προηγούμενο.
Η ροή δεδομένων εισόδου αναλύεται σε ένα ευρύ φάσμα συνθηκών, αλλά η διαδικασία ανάλυσης είναι γενικά αναδρομική. Δεν έχει νόημα να γράφουμε μοναδικούς αλγόριθμους για όλες τις παραλλαγές της ροής εισόδου. Θα πρέπει να υπάρχει μία λειτουργικότητα. Εδώ, οι αναδρομικοί αλγόριθμοι είναι παραδείγματα για το πώς να σχηματίσετε μια ροή εξόδου που να είναι επαρκής για την είσοδο. Αυτή δεν είναι η έξοδος του αναδρομικού αλγορίθμου, αλλά είναι η επιθυμητή και απαραίτητη λύση.
Αφαίρεση, αναδρομή και OOP
Ο αντικειμενοστρεφής προγραμματισμός (OOP) και η αναδρομή είναι θεμελιωδώς διαφορετικές οντότητες, αλλά αλληλοσυμπληρώνονται τέλεια. Η αφαίρεση δεν έχει καμία σχέση με την αναδρομή, αλλά μέσω του φακού του OOP δημιουργεί τη δυνατότητα υλοποίησης της αναδρομής με βάση τα συμφραζόμενα.
Για παράδειγμα, οι πληροφορίες αναλύονται και τα γράμματα, οι λέξεις, οι φράσεις, οι προτάσεις και οι παράγραφοι επισημαίνονται ξεχωριστά. Προφανώς, ο προγραμματιστής θα φροντίσει για τη δημιουργία παρουσιών αντικειμένων αυτών των πέντε τύπων και θα προσφέρει μια λύση αναδρομικών αλγορίθμων σε κάθε επίπεδο.
Εν τω μεταξύ, αν στο επίπεδο των γραμμάτων «δεν έχει νόημα να ψάχνουμε για νόημα», τότε η σημασιολογία εμφανίζεται στο επίπεδο των λέξεων. Μπορείτε να χωρίσετε τις λέξεις σε ρήματα, ουσιαστικά, επιρρήματα, προθέσεις… Μπορείτε να προχωρήσετε περισσότερο και να ορίσετε περιπτώσεις.
Σε επίπεδο φράσης, η σημασιολογία συμπληρώνεται από σημεία στίξης και λογικήσυνδυασμοί λέξεων. Στο επίπεδο των προτάσεων, βρίσκεται ένα πιο τέλειο επίπεδο σημασιολογίας και μια παράγραφος μπορεί να θεωρηθεί ως μια ολοκληρωμένη σκέψη.
Αντικειμενοστρεφής ανάπτυξη προκαθορίζει την κληρονομικότητα ιδιοτήτων και μεθόδων και προτείνει να ξεκινήσει η ιεραρχία των αντικειμένων με τη δημιουργία ενός εντελώς αφηρημένου προγόνου. Ταυτόχρονα, αναμφίβολα, η ανάλυση κάθε απόγονου θα είναι επαναληπτική και δεν θα διαφέρει πολύ σε τεχνικό επίπεδο σε πολλές θέσεις (γράμματα, λέξεις, φράσεις και προτάσεις). Οι παράγραφοι, όπως και οι πλήρεις σκέψεις, μπορεί να ξεχωρίζουν από αυτήν τη λίστα, αλλά δεν είναι η ουσία.
Είναι σημαντικό το συντριπτικό μέρος του αλγορίθμου να μπορεί να διατυπωθεί σε επίπεδο αφηρημένου προγόνων, βελτιώνοντάς το στο επίπεδο κάθε απογόνου με δεδομένα και μεθόδους που καλούνται από το αφηρημένο επίπεδο. Σε αυτό το πλαίσιο, η αφαίρεση ανοίγει νέους ορίζοντες για αναδρομή.
Ιστορικά χαρακτηριστικά του OOP
Το OOP έχει έρθει στον κόσμο του λογισμικού δύο φορές, αν και ορισμένοι ειδικοί μπορεί να ξεχωρίσουν την εμφάνιση του υπολογιστικού νέφους και των σύγχρονων ιδεών για αντικείμενα και κλάσεις ως νέο γύρο στην ανάπτυξη τεχνολογιών πληροφορικής.
Οι όροι "αντικείμενο" και "αντικείμενο" στο σύγχρονο πλαίσιο του OOP αποδίδονται συνήθως στις δεκαετίες του '50 και του '60 του περασμένου αιώνα, αλλά συνδέονται με το 1965 και την εμφάνιση των Simula, Lisp, Algol, Smalltalk..
Εκείνες τις μέρες, ο προγραμματισμός δεν ήταν ιδιαίτερα αναπτυγμένος και δεν μπορούσε να ανταποκριθεί επαρκώς σε επαναστατικές έννοιες. Ο αγώνας των ιδεών και των μορφών προγραμματισμού (C / C ++ και Pascal - κυρίως) ήταν ακόμα μακριά και οι βάσεις δεδομένων είχαν ακόμη διαμορφωθεί εννοιολογικά.
Στα τέλη της δεκαετίας του '80 και στις αρχές της δεκαετίας του '90, τα αντικείμενα εμφανίστηκαν στο Pascal και όλοι θυμήθηκαν τάξεις σε C / C ++ - αυτό σηματοδότησε έναν νέο γύρο ενδιαφέροντος για το OOP και τότε ήταν που τα εργαλεία, κυρίως οι γλώσσες προγραμματισμού, δεν έγιναν υποστηρίζουν μόνο αντικειμενοστρεφείς ιδέες, αλλά εξελίσσονται ανάλογα.
Φυσικά, εάν οι προηγούμενοι αναδρομικοί αλγόριθμοι ήταν απλώς συναρτήσεις που χρησιμοποιήθηκαν στον γενικό κώδικα του προγράμματος, τώρα η αναδρομή θα μπορούσε να γίνει μέρος των ιδιοτήτων ενός αντικειμένου (κλάσης), το οποίο παρείχε ενδιαφέρουσες ευκαιρίες στο πλαίσιο της κληρονομικότητας.
Χαρακτηριστικό του σύγχρονου OOP
Η ανάπτυξη του OOP που αρχικά δηλώθηκαν αντικείμενα (κλάσεις) ως συλλογές δεδομένων και ιδιοτήτων (μέθοδοι). Στην πραγματικότητα, επρόκειτο για δεδομένα που έχουν σύνταξη και νόημα. Αλλά τότε δεν ήταν δυνατό να παρουσιαστεί το OOP ως εργαλείο για τη διαχείριση πραγματικών αντικειμένων.
Το OOP έχει γίνει ένα εργαλείο για τη διαχείριση αντικειμένων "φύσης υπολογιστή". Ένα σενάριο, ένα κουμπί, ένα στοιχείο μενού, μια γραμμή μενού, μια ετικέτα σε ένα παράθυρο του προγράμματος περιήγησης είναι ένα αντικείμενο. Όχι όμως μια μηχανή, ένα προϊόν διατροφής, μια λέξη ή μια πρόταση. Τα πραγματικά αντικείμενα έχουν παραμείνει εκτός αντικειμενοστρεφούς προγραμματισμού και τα εργαλεία υπολογιστών έχουν αποκτήσει μια νέα ενσάρκωση.
Λόγω των διαφορών στις δημοφιλείς γλώσσες προγραμματισμού, έχουν προκύψει πολλές διάλεκτοι του OOP. Όσον αφορά τη σημασιολογία, είναι πρακτικά ισοδύναμα και η εστίασή τους στην οργανική σφαίρα, και όχι στην εφαρμοσμένη, καθιστά δυνατή την περιγραφή των πραγματικών αντικειμένων πέρα απόαλγόριθμους και να εξασφαλίσουν τη διαπλατφορμική και διαγλωσσική «ύπαρξή» τους.
Στοίβες και μηχανισμοί κλήσης λειτουργιών
Οι μηχανισμοί για την κλήση συναρτήσεων (διαδικασίες, αλγόριθμοι) απαιτούν τη διαβίβαση δεδομένων (παραμέτρων), την επιστροφή ενός αποτελέσματος και την απομνημόνευση της διεύθυνσης του χειριστή που πρέπει να λάβει τον έλεγχο μετά την ολοκλήρωση της συνάρτησης (διαδικασίας).
Συνήθως, η στοίβα χρησιμοποιείται για αυτόν τον σκοπό, αν και οι γλώσσες προγραμματισμού ή ο ίδιος ο προγραμματιστής μπορούν να παρέχουν μια ποικιλία επιλογών για τη μεταφορά του ελέγχου. Ο σύγχρονος προγραμματισμός παραδέχεται ότι το όνομα μιας συνάρτησης μπορεί να είναι όχι μόνο μια παράμετρος: μπορεί να σχηματιστεί κατά την εκτέλεση του αλγορίθμου. Ένας αλγόριθμος μπορεί επίσης να δημιουργηθεί κατά την εκτέλεση ενός άλλου αλγόριθμου.
Η έννοια των αναδρομικών αλγορίθμων, όταν τα ονόματα και τα σώματά τους μπορούν να προσδιοριστούν τη στιγμή του σχηματισμού της εργασίας (επιλέγοντας τον επιθυμητό αλγόριθμο), επεκτείνει την αναδρομικότητα όχι μόνο στο πώς να κάνετε κάτι, αλλά και στο ποιος ακριβώς πρέπει Κάνε το. Η επιλογή ενός αλγορίθμου με το "σημαινόμενο" του όνομα είναι πολλά υποσχόμενη, αλλά δημιουργεί δυσκολίες.
Αναδρομικότητα σε ένα σύνολο συναρτήσεων
Δεν μπορείτε να πείτε ότι ένας αλγόριθμος είναι αναδρομικός όταν καλεί τον εαυτό του και αυτό είναι όλο. Ο προγραμματισμός δεν είναι δόγμα και η έννοια της αναδρομικότητας δεν είναι αποκλειστική απαίτηση για να καλέσετε τον εαυτό σας από το σώμα του δικού σας αλγορίθμου.
Οι πρακτικές εφαρμογές δεν δίνουν πάντα μια καθαρή λύση. Συχνά, τα αρχικά δεδομένα πρέπει να προετοιμαστούν και το αποτέλεσμα της αναδρομικής κλήσης πρέπει να αναλυθεί στο πλαίσιο ολόκληρου του προβλήματος (όλου του αλγορίθμου) στοσυνολικά.
Στην πραγματικότητα, όχι μόνο πριν κληθεί μια αναδρομική συνάρτηση, αλλά και αφού ολοκληρωθεί, μπορεί ή πρέπει να κληθεί ένα άλλο πρόγραμμα. Εάν δεν υπάρχουν ειδικά προβλήματα με την κλήση: η αναδρομική συνάρτηση A() καλεί τη συνάρτηση B(), η οποία κάνει κάτι και καλεί την A(), τότε αμέσως υπάρχει πρόβλημα με την επιστροφή του ελέγχου. Μετά την ολοκλήρωση της επαναλαμβανόμενης κλήσης, η συνάρτηση A() πρέπει να λάβει τον έλεγχο για να καλέσει ξανά τη B(), η οποία θα την καλέσει ξανά. Η επιστροφή του ελέγχου όπως θα έπρεπε στη σειρά στη στοίβα πίσω στο B() είναι η λάθος λύση.
Ο προγραμματιστής δεν περιορίζεται στην επιλογή των παραμέτρων και μπορεί να τις συμπληρώσει με ονόματα συναρτήσεων. Με άλλα λόγια, η ιδανική λύση είναι να περάσει το όνομα της B() στην A() και να αφήσουμε την ίδια την A() να καλέσει την B(). Σε αυτήν την περίπτωση, δεν θα υπάρχουν προβλήματα με την επιστροφή του ελέγχου και η υλοποίηση του αναδρομικού αλγόριθμου θα είναι πιο διαφανής.
Κατανόηση και επίπεδο αναδρομής
Το πρόβλημα με την ανάπτυξη αναδρομικών αλγορίθμων είναι ότι πρέπει να κατανοήσετε τη δυναμική της διαδικασίας. Όταν χρησιμοποιείτε την αναδρομή σε μεθόδους αντικειμένων, ειδικά στο επίπεδο ενός αφηρημένου προγόνου, υπάρχει πρόβλημα κατανόησης του δικού σας αλγορίθμου στο πλαίσιο του χρόνου εκτέλεσής του.
Προς το παρόν, δεν υπάρχουν περιορισμοί στο επίπεδο ένθεσης των συναρτήσεων και στη χωρητικότητα στοίβας στους μηχανισμούς κλήσης, αλλά υπάρχει ένα πρόβλημα κατανόησης: σε ποιο χρονικό σημείο ποιο επίπεδο δεδομένων ή ποια θέση στον γενικό αλγόριθμο που ονομάζεται αναδρομική λειτουργία και σε ποιον αριθμό κλήσεων είναι η ίδια.
Τα υπάρχοντα εργαλεία εντοπισμού σφαλμάτων είναι συχνά ανίσχυραπείτε στον προγραμματιστή τη σωστή λύση.
Loops και recursion
Θεωρείται ότι η κυκλική εκτέλεση είναι ισοδύναμη με την αναδρομή. Πράγματι, σε ορισμένες περιπτώσεις, ο αναδρομικός αλγόριθμος μπορεί να εφαρμοστεί στη σύνταξη δομών υπό όρους και κυκλικές.
Ωστόσο, εάν υπάρχει σαφής κατανόηση ότι μια συγκεκριμένη συνάρτηση πρέπει να υλοποιηθεί μέσω ενός αναδρομικού αλγόριθμου, οποιαδήποτε εξωτερική χρήση ενός βρόχου ή δηλώσεων υπό όρους θα πρέπει να εγκαταλειφθεί.
Το νόημα εδώ είναι ότι μια αναδρομική λύση με τη μορφή συνάρτησης που χρησιμοποιεί τον εαυτό της θα είναι ένας πλήρης, λειτουργικά πλήρης αλγόριθμος. Αυτός ο αλγόριθμος θα απαιτήσει από τον προγραμματιστή να τον δημιουργήσει με προσπάθεια, κατανοώντας τη δυναμική του αλγορίθμου, αλλά θα είναι η τελική λύση που δεν απαιτεί εξωτερικό έλεγχο.
Οποιοσδήποτε συνδυασμός εξωτερικών τελεστών υπό όρους και κυκλικούς δεν θα μας επιτρέψει να αναπαραστήσουμε τον αναδρομικό αλγόριθμο ως πλήρη συνάρτηση.
Recursion Consensus and OOP
Σε όλες σχεδόν τις παραλλαγές ανάπτυξης ενός αναδρομικού αλγορίθμου, προκύπτει ένα σχέδιο για την ανάπτυξη δύο αλγορίθμων. Ο πρώτος αλγόριθμος δημιουργεί μια λίστα μελλοντικών αντικειμένων (στιγμάτων) και ο δεύτερος αλγόριθμος είναι στην πραγματικότητα μια αναδρομική συνάρτηση.
Η καλύτερη λύση θα ήταν να τακτοποιήσετε την αναδρομή ως μια ενιαία ιδιότητα (μέθοδος) που περιέχει στην πραγματικότητα τον αναδρομικό αλγόριθμο και να τοποθετήσετε όλη την προπαρασκευαστική εργασία στον κατασκευαστή αντικειμένων.
Ένας αναδρομικός αλγόριθμος θα είναι η σωστή λύση μόνο όταν λειτουργείμόνο μόνος του, χωρίς εξωτερικό έλεγχο και διαχείριση. Ένας εξωτερικός αλγόριθμος μπορεί να δώσει μόνο ένα σήμα για να λειτουργήσει. Το αποτέλεσμα αυτής της εργασίας θα πρέπει να είναι η αναμενόμενη λύση, χωρίς εξωτερική υποστήριξη.
Η αναδρομή πρέπει να είναι πάντα μια πλήρης αυτόνομη λύση.
Διαισθητική κατανόηση και λειτουργική πληρότητα
Όταν ο αντικειμενοστραφής προγραμματισμός έγινε το de facto πρότυπο, έγινε προφανές ότι για να κωδικοποιήσετε αποτελεσματικά, πρέπει να αλλάξετε τη δική σας σκέψη. Ο προγραμματιστής πρέπει να μετακινηθεί από τη σύνταξη και τη σημασιολογία της γλώσσας στη δυναμική της σημασιολογίας κατά την εκτέλεση του αλγορίθμου.
Χαρακτηριστικό της αναδρομής: μπορεί να εφαρμοστεί σε όλα:
- απόξεση ιστού;
- λειτουργίες αναζήτησης;
- ανάλυση πληροφοριών κειμένου;
- ανάγνωση ή δημιουργία εγγράφων MS Word;
- δειγματοληψία ή ανάλυση ετικετών…
Χαρακτηριστικό του OOP: καθιστά δυνατή την περιγραφή ενός αναδρομικού αλγόριθμου στο επίπεδο ενός αφηρημένου προγόνου, αλλά προβλέπει ότι αναφέρεται σε μοναδικούς απογόνους, καθένας από τους οποίους έχει τη δική του παλέτα δεδομένων και ιδιοτήτων.
Η αναδρομή είναι ιδανική γιατί απαιτεί τη λειτουργική πληρότητα του αλγορίθμου της. Το OOP βελτιώνει την απόδοση ενός αναδρομικού αλγορίθμου δίνοντάς του πρόσβαση σε όλα τα μοναδικά παιδιά.
