Εισαγωγή στην Αναδρομή στην Python

Θέλετε να μάθετε τα πάντα για την αναδρομή στον προγραμματισμό; Αυτό το σεμινάριο για την αναδρομή στην Python θα σας βοηθήσει να ξεκινήσετε.

Το Recursion είναι μια εξαιρετικά χρήσιμη τεχνική επίλυσης προβλημάτων που μπορείτε να προσθέσετε στην εργαλειοθήκη του προγραμματιστή σας. Αν και αρχικά είναι συχνά δύσκολο να τυλίξετε το κεφάλι σας γύρω, η αναδρομή μπορεί να σας βοηθήσει να βρείτε πιο κομψές λύσεις σε περίπλοκα προβλήματα.

Σε αυτό το σεμινάριο, θα ακολουθήσουμε μια προσέγγιση με πρώτο κώδικα για την εκμάθηση αναδρομής χρησιμοποιώντας Python. Ειδικότερα, θα καλύψουμε:

• Τα βασικά της αναδρομής
• Αναδρομικές συναρτήσεις και πώς λειτουργούν
• Εφαρμογή αναδρομικών συναρτήσεων σε Python
• Διαφορές μεταξύ επαναληπτικών και επαναληπτικών προσεγγίσεων στην επίλυση προβλημάτων

Ας αρχίσουμε!

Τι είναι η αναδρομή;

Η αναδρομή είναι μια τεχνική προγραμματισμού όπου μια συνάρτηση καλεί τον εαυτό της επανειλημμένα για να λύσει ένα πρόβλημα.

Στον πυρήνα της, η αναδρομή είναι μια προσέγγιση επίλυσης προβλημάτων που περιλαμβάνει τη διάσπαση ενός σύνθετου προβλήματος σε μικρότερα, πανομοιότυπα υποπροβλήματα. Ουσιαστικά, σας επιτρέπει να λύσετε ένα πρόβλημα όσον αφορά τις απλούστερες εκδόσεις του.

Λοιπόν, πώς υλοποιούμε την αναδρομή στον κώδικα; Για να γίνει αυτό, ας καταλάβουμε πώς λειτουργούν οι αναδρομικές συναρτήσεις.

Κατανόηση των αναδρομικών συναρτήσεων

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

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

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

• Βασική περίπτωση: Η βασική περίπτωση είναι μια συνθήκη (ή συνθήκες) που καθορίζουν πότε πρέπει να σταματήσει η αναδρομή. Όταν πληρούται η βασική περίπτωση, η συνάρτηση επιστρέφει ένα αποτέλεσμα χωρίς να πραγματοποιεί περαιτέρω αναδρομικές κλήσεις. Μια θήκη βάσης είναι απαραίτητη για την αποφυγή άπειρης αναδρομής.
• Αναδρομική περίπτωση: Η αναδρομική περίπτωση ορίζει πώς να αναλύσετε το πρόβλημα σε μικρότερα υποπροβλήματα. Σε αυτό το τμήμα της συνάρτησης, η συνάρτηση καλεί τον εαυτό της με τροποποιημένες εισόδους. Κάθε αναδρομική κλήση είναι, επομένως, ένα βήμα προς την επίτευξη της βασικής περίπτωσης.

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

Πώς λειτουργεί το Recursion Under the Hood

Όταν καλείται μια συνάρτηση, μια εγγραφή του πλαισίου εκτέλεσής της τοποθετείται στη στοίβα κλήσεων. Αυτή η εγγραφή περιλαμβάνει πληροφορίες σχετικά με τα ορίσματα της συνάρτησης, τις τοπικές μεταβλητές και τη θέση που θα επιστρέψει μόλις ολοκληρωθεί η εκτέλεση της συνάρτησης.

Στην περίπτωση των αναδρομικών συναρτήσεων, όταν μια συνάρτηση καλεί τον εαυτό της, μια νέα εγγραφή προωθείται στη στοίβα κλήσεων, αναστέλλοντας ουσιαστικά την εκτέλεση της τρέχουσας συνάρτησης. Η στοίβα επιτρέπει στην Python να παρακολουθεί όλες τις εκκρεμείς κλήσεις συναρτήσεων, συμπεριλαμβανομένων εκείνων από αναδρομικές κλήσεις.

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

Υλοποίηση αναδρομής στην Python

Σε αυτήν την ενότητα, θα εξερευνήσουμε τρία απλά παραδείγματα αναδρομής:

Υπολογισμός του παραγοντικού ενός αριθμού

Υπολογισμός αριθμών Fibonacci

Υλοποίηση δυαδικής αναζήτησης με χρήση αναδρομής.

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

#1. Παραγοντικός υπολογισμός με χρήση αναδρομής

Πρόβλημα: Υπολογίστε το παραγοντικό ενός μη αρνητικού ακέραιου αριθμού n, που συμβολίζεται ως n!. Μαθηματικά, το παραγοντικό ενός αριθμού n είναι το γινόμενο όλων των θετικών ακεραίων από το 1 έως το n.

Ο παραγοντικός υπολογισμός προσφέρεται για αναδρομή, όπως φαίνεται:

Ακολουθεί η αναδρομική συνάρτηση για τον υπολογισμό του παραγοντικού ενός δεδομένου αριθμού n:

def factorial(n):
	# Base case
    if n == 0 or n == 1:
        return 1
	# Recursive case: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Ας υπολογίσουμε το 5! χρησιμοποιώντας τη συνάρτηση factorial():

factorial_5 = factorial(5)
print(factorial(5))
# Output: 120

Ας δούμε τώρα πώς λειτουργεί η συνάρτηση:

• Έχουμε μια βασική περίπτωση που ελέγχει αν το n είναι ίσο με 0 ή 1. Εάν πληρούται η συνθήκη, οι συναρτήσεις επιστρέφουν 1. Θυμηθείτε ότι 0! είναι 1, και έτσι είναι 1!.
• Αν το n είναι μεγαλύτερο από 1, υπολογίζουμε το n! πολλαπλασιάζοντας το n με το παραγοντικό του n-1. Αυτό εκφράζεται ως n * παραγοντικό(n – 1).
• Η συνάρτηση συνεχίζει να κάνει αναδρομικές κλήσεις με φθίνουσες τιμές n μέχρι να φτάσει στη βασική περίπτωση.

#2. Αριθμοί Fibonacci με αναδρομή

Πρόβλημα: Βρείτε τον όρο στον n-ο δείκτη στο Ακολουθία Fibonacci. Η ακολουθία Fibonacci ορίζεται ως εξής: F(0) = 0, F(1) = 1 και F(n) = F(n-1) + F(n-2) για n >= 2.

def fibonacciSeq(n):
	# Base cases
    if n == 0:
        return 0
    elif n == 1:
        return 1
	# Recursion: F(n) = F(n-1) + F(n-2)
    else:
        return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)

Ας εκτελέσουμε τη συνάρτηση:

fib_5 = fibonacciSeq(5)
print(fib_5)
# Output: 5

Δείτε πώς λειτουργεί η λειτουργία:

• Ας ξεκινήσουμε συζητώντας τις βασικές περιπτώσεις. Αν το n είναι 0, επιστρέφει 0. Και αν το n είναι 1, επιστρέφει 1. Ανάκληση F(0) = 0 και F(1) = 1.
• Στην αναδρομική περίπτωση, εάν το n είναι μεγαλύτερο από 1, η συνάρτηση υπολογίζει το F(n) προσθέτοντας τους όρους F(n-1) και F(n-2). Αυτό εκφράζεται ως fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
• Η συνάρτηση συνεχίζει να κάνει αναδρομικές κλήσεις με φθίνουσες τιμές n μέχρι να φτάσει στις βασικές περιπτώσεις.

#3. Αναδρομική Υλοποίηση Δυαδικής Αναζήτησης

Πρόβλημα: Εφαρμόστε έναν αλγόριθμο δυαδικής αναζήτησης χρησιμοποιώντας αναδρομή για να βρείτε τη θέση ενός στοιχείου στόχου σε μια ταξινομημένη λίστα.

Ακολουθεί η αναδρομική υλοποίηση της δυαδικής αναζήτησης:

def binarySearch(arr, target, low, high):
	# Base case: target not found
    if low > high:
        return -1

    mid = (low + high) // 2

	# Base case: target found
    if arr[mid] == target:
        return mid
	# Recursive case: search left or right half of the array
    elif arr[mid] > target:
        return binarySearch(arr, target, low, mid - 1)
    else:
        return binarySearch(arr, target, mid + 1, high)

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

Ακολουθεί ένα δείγμα εκτέλεσης της συνάρτησης:

arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96]
target = 37
idx = binarySearch(arr, target, 0, len(arr)-1)
print(idx)
# Output: 4

Ας αναλύσουμε τι κάνει η συνάρτηση:

• Στην αναδρομική υλοποίηση δυαδικής αναζήτησης, έχουμε δύο βασικές περιπτώσεις. Πρώτον, εάν το χαμηλό γίνει μεγαλύτερο από το υψηλό, σημαίνει ότι το στοιχείο στόχος δεν βρίσκεται στη λίστα. Έτσι, επιστρέφουμε -1 για να υποδείξουμε ότι ο στόχος δεν βρέθηκε.
• Η άλλη βασική περίπτωση ελέγχει εάν το στοιχείο στο μεσαίο δείκτη στο μέσο του τρέχοντος διαστήματος αναζήτησης είναι ίσο με τον στόχο. Εάν ταιριάζουν, επιστρέφουμε τον δείκτη στο μέσο, ​​υποδεικνύοντας ότι βρήκαμε τον στόχο.
• Στην αναδρομική περίπτωση, εάν το μεσαίο στοιχείο είναι μεγαλύτερο από τον στόχο, αναζητούμε αναδρομικά το αριστερό μισό του πίνακα καλώντας το binarySearch(arr, target, low, mid – 1). Εάν το μεσαίο στοιχείο είναι μικρότερο από τον στόχο, αναζητούμε το δεξί μισό καλώντας το binarySearch(arr, target, mid + 1, high).

Αναδρομική έναντι Επαναληπτικής Προσέγγισης

Η επαναληπτική προσέγγιση – χρησιμοποιώντας βρόχους – είναι μια άλλη κοινή προσέγγιση για την επίλυση προβλημάτων. Λοιπόν, σε τι διαφέρει από την αναδρομή; Ας ανακαλύψουμε.

Αρχικά, συγκρίνουμε αναδρομικές και επαναληπτικές λύσεις σε ένα κοινό πρόβλημα: τον υπολογισμό του παραγοντικού ενός αριθμού.

Ακολουθεί η αναδρομική υλοποίηση του παραγοντικού υπολογισμού:

def factorialRec(n):
	# Base case
    if n == 0 or n == 1:
        return 1
	# Recursive case: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Επειδή γνωρίζουμε ότι το παραγοντικό ενός μη αρνητικού αριθμού είναι το γινόμενο όλων των αριθμών από το 1 έως το n, μπορούμε επίσης να γράψουμε μια επαναληπτική υλοποίηση χρησιμοποιώντας βρόχους.

def factorialIter(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

Και οι δύο αυτές υλοποιήσεις δίνουν τα ίδια αποτελέσματα.

factorial_5 = factorialRec(5)
print(factorial_5)
# Output: 120

factorial_5 = factorialIter(5)
print(factorial_0)
# Output: 120

Προτιμάται όμως η επαναληπτική προσέγγιση έναντι της αναδρομής; Όταν υπάρχει βαθιά αναδρομή—με πάρα πολλές κλήσεις συναρτήσεων—μπορεί να αντιμετωπίσετε σφάλματα λόγω υπέρβασης του βάθους αναδρομής. Ο βρόχος είναι μια καλύτερη επιλογή για προβλήματα των οποίων η αναδρομική υλοποίηση απαιτεί πάρα πολλές κλήσεις συναρτήσεων για να φτάσει στη βασική περίπτωση.

Ας συνοψίσουμε τις διαφορές μεταξύ επαναληπτικών και αναδρομικών υλοποιήσεων:

FeatureRecursive ApproachIterative ApproachStructureΧρησιμοποιεί αναδρομικές κλήσεις συναρτήσεων και βασίζεται στη στοίβα κλήσεων.Χρησιμοποιεί βρόχους για επανάληψη χωρίς πρόσθετες κλήσεις συναρτήσεων.Βασικές περιπτώσεις Απαιτεί ρητές βασικές περιπτώσεις για να σταματήσει η αναδρομή. Συνήθως χρησιμοποιεί συνθήκες βρόχου για τον τερματισμό. Η απόδοση μπορεί να είναι λιγότερο αποδοτική ως προς τη μνήμη λόγω της κλήσης . Η βαθιά αναδρομή μπορεί μερικές φορές να οδηγήσει σε σφάλματα υπερχείλισης στοίβας. Γενικά πιο αποδοτική στη μνήμη και λιγότερο επιρρεπής σε σφάλματα υπερχείλισης στοίβας. Ο εντοπισμός σφαλμάτων μπορεί να είναι δύσκολος στον εντοπισμό σφαλμάτων λόγω πολλαπλών κλήσεων συναρτήσεων και ένθετων πλαισίων εκτέλεσης. Συνήθως είναι πιο εύκολος ο εντοπισμός σφαλμάτων λόγω μιας απλής γραμμικής ροής εκτέλεσης .Επαναληπτική vs Αναδρομική προσέγγιση

συμπέρασμα

Σε αυτό το άρθρο, ξεκινήσαμε μαθαίνοντας τι είναι η αναδρομή και πώς να ορίσουμε αναδρομικές συναρτήσεις με περιπτώσεις βάσης και σχέσεις επανάληψης.

Στη συνέχεια γράψαμε κάποιο κώδικα Python—αναδρομικές υλοποιήσεις κοινών προβλημάτων προγραμματισμού. Τέλος, μάθαμε τις διαφορές μεταξύ επαναληπτικών και επαναληπτικών προσεγγίσεων και τα πλεονεκτήματα και τα μειονεκτήματα καθεμιάς από αυτές τις προσεγγίσεις.

Στη συνέχεια, ελέγξτε αυτήν τη λίστα ερωτήσεων συνέντευξης Python.