Με απλά λόγια, η αναδρομή είναι ένας τρόπος επίλυσης του προβλήματος με τη λειτουργία μιας κλήσης, η λέξη « αναδρομική 'Προέρχεται από το λατινικό ρήμα' επανέρχομαι ', Που σημαίνει να επαναλάβω κάτι. Αυτό κάνει η αναδρομική λειτουργία, επαναλαμβάνει το ίδιο πράγμα ξανά και ξανά, δηλαδή θυμάται τον εαυτό του. Σε αυτό το άρθρο, θα μάθουμε για την αναδρομή στο python. Ακολουθούν τα θέματα που καλύπτονται σε αυτό το ιστολόγιο:
- Τι είναι η αναδρομή στο Python;
- Κατάσταση τερματισμού
- Όριο αναδρομής της Python
- Ισιώνοντας λίστες με επανάληψη
- Πλεονεκτήματα της αναδρομής
- Μειονεκτήματα της αναδρομής
Τι είναι η αναδρομή στο Python;
Η επανάληψη είναι η διαδικασία προσδιορισμού κάτι από μόνο του. Γνωρίζουμε ότι στην Python, οποιαδήποτε συνάρτηση μπορεί να καλέσει οποιαδήποτε άλλη συνάρτηση, μια συνάρτηση μπορεί επίσης να καλείται. Αυτοί οι τύποι συναρτήσεων που αποκαλούνται έως ότου δεν πληρούται η συγκεκριμένη συνθήκη ονομάζονται αναδρομικές συναρτήσεις.
ας πάρουμε μερικά παραδείγματα για να δούμε πώς λειτουργεί, Εάν σας δοθεί ένας θετικός ακέραιος n το παραγοντικό θα ήταν.
- ν! = n * (n-1) * (n-2) και ούτω καθεξής.
- 2! = 2 * (2-1)
- ένας! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Η αντικατάσταση των παραπάνω τιμών θα έχει ως αποτέλεσμα την ακόλουθη παράσταση
- 4! = 4 * 3 * 2 * 1
Πρέπει να ορίσουμε μια συνάρτηση, ας πούμε fact (n) που παίρνει θετικό ακέραιο ή 0 ως παράμετρο και επιστρέφει το nth factorial, πώς μπορούμε να το κάνουμε χρησιμοποιώντας αναδρομή;
Ας δούμε, για να το κάνουμε χρησιμοποιώντας αναδρομή πρέπει να εξετάσουμε την ακόλουθη εξίσωση
ν! = n. (n-1). (n-2) & hellip3.2.1
πώς να χρησιμοποιήσετε την ειδοποίηση στο javascript
ν! = ν. (n-1)! # μπορούμε να ξαναγράψουμε την παραπάνω δήλωση όπως σε αυτήν τη γραμμή
Τώρα εδώ αν περάσουμε το 2 ως παράμετρο θα πάρουμε:
2! = 2.1! = 2
Ομοίως, αν περάσουμε το 1 θα πάρουμε:
ένας! = 1.0! = 1
Αλλά αν περάσουμε το 0, σπάει
0! = 0. (- 1)! και εδώ δεν καθορίζεται το παραγοντικό για -1, οπότε αυτό λειτουργεί μόνο για τιμές> 0
Πρέπει λοιπόν να γράψουμε δύο περιπτώσεις
1. ν! = ν. (n-1)! αν n> = 1
2. 1 εάν n = 0
Αυτή είναι μια ολοκληρωμένη λύση για όλους τους θετικούς ακέραιους και 0.
Κατάσταση τερματισμού
Μια αναδρομική συνάρτηση πρέπει να πληροί μια σημαντική προϋπόθεση για τερματισμό. Προχωρώντας σε μια κατάσταση όπου το πρόβλημα μπορεί να λυθεί χωρίς περαιτέρω αναδρομή, μια αναδρομική συνάρτηση θα τερματιστεί, ελαχιστοποιώντας το πρόβλημα στα μικρότερα δευτερεύοντα βήματα. Μια αναδρομή μπορεί να καταλήξει σε έναν άπειρο βρόχο εάν η συνθήκη τερματισμού δεν ικανοποιείται στις κλήσεις.
Παράγοντες συνθήκες:
- παραγοντικός του n = n * (n-1) εφ 'όσον το n είναι μεγαλύτερο από 1.
- 1 αν n = 0
Θα μετατρέψουμε τις παραπάνω παραγοντικές συνθήκες σε κώδικα python:
def fact (n): if n == 1: return n else: return n * fact (n-1)
Ας πάρουμε ένα παράδειγμα, ας πούμε ότι θέλουμε να βρούμε παραγοντικά του 4:
fact (4) # αυτό θα επιστρέψει το 4 * fact (3) και ούτω καθεξής έως το n == 1.
Παραγωγή: 24
Χρησιμοποιείται τόσο συχνά ως παράδειγμα για αναδρομή λόγω της απλότητας και της σαφήνειας. Επίλυση μικρότερων περιπτώσεων ενός προβλήματος σε κάθε βήμα που ονομάζεται αναδρομή στην επιστήμη των υπολογιστών.
Όριο αναδρομής της Python
Σε ορισμένες γλώσσες, μπορείτε να δημιουργήσετε έναν άπειρο αναδρομικό βρόχο, αλλά, στην Python, υπάρχει ένα όριο αναδρομής. Για να ελέγξετε το όριο εκτελέστε την ακόλουθη συνάρτηση από την ενότητα sys. το οποίο θα δώσει το όριο του σετ αναδρομής για το python.
πηγαίνετε στη λειτουργία στο python
εισαγωγή sys sys.getrecursionlimit ()
Παραγωγή: 1000
Μπορείτε επίσης να αλλάξετε το όριο χρησιμοποιώντας το functionsetrecursionlimit της λειτουργικής μονάδας sys () σύμφωνα με την απαίτησή σας, τώρα ας δημιουργήσουμε μια συνάρτηση που καλείται αναδρομικά μέχρι να υπερβεί το όριο και να ελέγξει τι συμβαίνει:
def recursive (): recursive () if __name__ == '__main__': αναδρομικό ()
Εάν εκτελέσετε τον παραπάνω κώδικα, θα λάβετε μια εξαίρεση χρόνου εκτέλεσης: RuntimeError: υπέρβαση του μέγιστου βάθους αναδρομής. Η Python σας εμποδίζει να δημιουργήσετε μια συνάρτηση που καταλήγει σε έναν ατέρμονα επαναλαμβανόμενο βρόχο.
Ισιώνοντας λίστες με επανάληψη
Άλλα πράγματα που μπορείτε να κάνετε χρησιμοποιώντας αναδρομή εκτός από τα παραγοντικά, ας υποθέσουμε ότι θέλετε να δημιουργήσετε ένα από μια λίστα που είναι ένθετη, μπορεί να γίνει χρησιμοποιώντας τον παρακάτω κώδικα:
def flatten (a_list, flat_list = none): if flat_list is none: flat_list = [] for item in a_list: if isinstance (item, list): flatten (item, flat_list) other: flat_list.append (item) επιστροφή flat_list εάν __name__ == '__main__': ένθετο = [1,2,3, [4,5], 6] x = επίπεδη (ένθετη) εκτύπωση (x)
Παραγωγή: [1,2,3,4,5,6]
Η εκτέλεση του παραπάνω κώδικα θα οδηγήσει σε μία λίστα αντί για ακέραια λίστα που περιέχει ακέραια λίστα που χρησιμοποιήσαμε ως εισαγωγή. Μπορείτε επίσης να κάνετε το ίδιο πράγμα χρησιμοποιώντας άλλους τρόπους επίσης, η Python έχει κάτι που ονομάζεται itertools.chain () μπορείτε να ελέγξετε τον κωδικό που χρησιμοποιείται για τη δημιουργία μιας αλυσίδας λειτουργίας () είναι μια διαφορετική προσέγγιση για να κάνετε το ίδιο πράγμα όπως κάναμε.
Πλεονεκτήματα της αναδρομής
Ο κωδικός είναι καθαρός και κομψός σε μια αναδρομική λειτουργία.
Μια σύνθετη εργασία μπορεί να χωριστεί σε απλούστερα δευτερεύοντα προβλήματα χρησιμοποιώντας την αναδρομή.
Η δημιουργία ακολουθίας είναι ευκολότερη με την αναδρομή παρά με τη χρήση μιας ένθετης επανάληψης
Μειονεκτήματα της αναδρομής
Ακολουθώντας τη λογική πίσω από την αναδρομική λειτουργία μπορεί μερικές φορές να είναι δύσκολη.
Οι αναδρομικές κλήσεις είναι ακριβές (αναποτελεσματικές) καθώς καταλαμβάνουν πολλή μνήμη και χρόνο.
Οι αναδρομικές συναρτήσεις είναι δύσκολο να εντοπιστούν.
Σε αυτό το άρθρο είδαμε τι είναι η αναδρομή και πώς μπορούμε να αναπτύξουμε αναδρομικές συναρτήσεις από τη δήλωση προβλήματος, πώς μαθηματικά μπορεί να οριστεί μια δήλωση προβλήματος. Λύσαμε ένα πρόβλημα του παραγοντικού και ανακαλύψαμε τις προϋποθέσεις που απαιτούνται για να βρούμε παραγοντικά από τα οποία μπορέσαμε να μετατρέψουμε αυτές τις συνθήκες σε κώδικα python δίνοντάς σας την κατανόηση του τρόπου λειτουργίας της αναδρομής. Νομίζω ότι είναι τακτοποιημένο ότι η Python έχει ένα ενσωματωμένο όριο αναδρομής για να αποτρέψει τους προγραμματιστές από τη δημιουργία κακώς κατασκευασμένων αναδρομικών λειτουργιών. Ένα σημαντικό πράγμα που πρέπει να παρατηρήσετε είναι ότι η αναδρομή είναι δύσκολο να εντοπιστεί σφαλμάτων καθώς η λειτουργία συνεχίζει να καλείται.