Εισαγωγή
Η αναδρομή είναι μια ισχυρή έννοια στον προγραμματισμό, όπου μια συνάρτηση καλεί τον εαυτό της.
Μπορεί να σου φανεί λίγο δύσκολη στην αρχή, αλλά μόλις καταλάβεις τα βασικά, γίνεται ένα πολύτιμο εργαλείο για την επίλυση σύνθετων προβλημάτων.
Σε αυτόν τον οδηγό θα εξερευνήσουμε την αναδρομή στη JavaScript με εύκολα κατανοητά παραδείγματα.
Τι είναι η αναδρομή;
Η αναδρομή συμβαίνει όταν μια συνάρτηση καλεί τον εαυτό της, είτε άμεσα είτε έμμεσα.
Μοιάζει με έναν βρόχο, αλλά περιλαμβάνει τη διάσπαση ενός προβλήματος σε μικρότερα και πιο εύκολα διαχειρίσιμα υποπροβλήματα.
Παράδειγμα 1: Αντίστροφη μέτρηση
Ας ξεκινήσουμε με ένα απλό παράδειγμα: μια συνάρτηση αντίστροφης μέτρησης.
function countdown(num) {
// Base case
if (num <= 0) {
console.log('Blastoff!');
return;
}
// Recursive case
console.log(num);
countdown(num - 1);
}
// Call the function
countdown(5);
Σε αυτό το παράδειγμα:
-
Βασική περίπτωση: Όταν το
num γίνει μικρότερο ή ίσο με 0, η συνάρτηση τυπώνει "Blastoff!" και σταματά να καλεί τον εαυτό της.
-
Αναδρομική περίπτωση: Η συνάρτηση τυπώνει το τρέχον
num και καλεί τον εαυτό της με num - 1.
Παράδειγμα 2: Παραγοντικό
Τώρα, ας δούμε ένα κλασικό παράδειγμα αναδρομής: τον υπολογισμό του παραγοντικού ενός αριθμού.
function factorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Test the function
console.log(factorial(5)); // Output: 120
Σε αυτό το παράδειγμα:
-
Βασική περίπτωση: Όταν το
n είναι 0 ή 1, η συνάρτηση επιστρέφει 1.
-
Αναδρομική περίπτωση: Η συνάρτηση πολλαπλασιάζει το
n με το παραγοντικό του n - 1.
Βασικές έννοιες
Βασική περίπτωση
Κάθε αναδρομική συνάρτηση πρέπει να έχει τουλάχιστον μία βασική περίπτωση, μια συνθήκη όπου η συνάρτηση σταματά να καλεί τον εαυτό της.
Χωρίς βασική περίπτωση, η αναδρομή θα συνεχιζόταν επ' άπειρον, οδηγώντας σε υπερχείλιση της στοίβας.
Αναδρομική περίπτωση
Η αναδρομική περίπτωση ορίζει πώς η συνάρτηση καλεί τον εαυτό της με μια μικρότερη ή απλούστερη εκδοχή του προβλήματος.
Πλεονεκτήματα και μειονεκτήματα της αναδρομής
Πλεονεκτήματα:
- Κομψή λύση για ορισμένα προβλήματα.
- Προσομοιώνει την έννοια της μαθηματικής επαγωγής.
Μειονεκτήματα:
- Μπορεί να είναι λιγότερο αποδοτική από τις επαναληπτικές λύσεις.
- Μπορεί να οδηγήσει σε υπερχείλιση της στοίβας σε βαθιά αναδρομή.
Συμπέρασμα
Η αναδρομή είναι μια πολύτιμη τεχνική που μπορεί να απλοποιήσει σύνθετα προβλήματα, σπάζοντάς τα σε μικρότερα και πιο εύκολα διαχειρίσιμα υποπροβλήματα.
Η κατανόηση των βασικών περιπτώσεων και των αναδρομικών περιπτώσεων είναι καθοριστική για την υλοποίηση αποτελεσματικών αναδρομικών λύσεων στη JavaScript.
Μάθε περισσότερα:
Οδηγίες
Έχεις ένα κατάστημα πίτσας και προσφέρεις τρία είδη πίτσας:
- Margherita: 7 $
- Caprese: 9 $
- Formaggio: 10 $
Αν οι πελάτες το θέλουν, μπορούν να προσθέσουν απεριόριστο αριθμό επιπλέον επιλογών: είτε "ExtraSauce" για 1 $ είτε "ExtraToppings" για 2 $.
Η αποστολή σου είναι να γράψεις κώδικα που βοηθά τον πελάτη να υπολογίσει το κόστος του.
Υπολόγισε την τιμή μιας πίτσας
Με το όνομα της πίτσας ως πρώτο όρισμα και έναν απεριόριστο αριθμό πρόσθετων επιλογών, υπολόγισε την τιμή της πίτσας σε δολάρια.
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
Υπολόγισε τη συνολική τιμή μιας παραγγελίας
Η συνάρτησή σου καλείται με μια λίστα από PizzaOrder και πρέπει να επιστρέψει τη συνολική τιμή της παραγγελίας σε δολάρια.
Κάθε PizzaOrder έχει μια ιδιότητα pizza, το όνομα της πίτσας, και μια ιδιότητα extras, τη λίστα με τις επιπλέον επιλογές.
const margherita = new PizzaOrder('Margherita');
const caprese = new PizzaOrder('Caprese', 'ExtraToppings');
orderPrice([margherita, caprese]);
// => 18
Θα διαπιστώσεις ότι δεν μπορείς να το γράψεις αυτό με αναδρομή, καθώς ένα τεστ με τεράστιο αριθμό παραγγελιών θα πετάξει Maximum call stack size exceeded.
Μην ανησυχείς, αυτό γίνεται επίτηδες· δοκίμασε να υλοποιήσεις αυτή τη συνάρτηση χρησιμοποιώντας έναν προστακτικό βρόχο!
Έχεις πολλές επιλογές, όπως, ενδεικτικά, τη χρήση της reduce ή ενός βρόχου for.
Όταν ο διερμηνευτής της JavaScript εκτελεί τον κώδικα JavaScript, παρακολουθεί σε ποιες συναρτήσεις έχει εισέλθει (έχει αρχίσει να καλεί) πάνω σε μια δομή δεδομένων που ονομάζεται "στοίβα".
Όταν η συνάρτηση επιστρέφει (τελειώνει), αφαιρείται από τη στοίβα.
Ωστόσο, αυτή η στοίβα έχει περιορισμένο μέγεθος.
Το πιο συνηθισμένο λάθος είναι μια αναδρομική συνάρτηση που δεν τελειώνει ποτέ.
Κάθε κλήση τοποθετείται στη στοίβα, αλλά πριν επιστρέψει, μια άλλη κλήση τοποθετείται στη στοίβα.
function kaboom() {
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
Το ίχνος στοίβας αυτού του σφάλματος δείχνει την ίδια γραμμή ξανά και ξανά, κάτι που βγάζει νόημα, επειδή η συνάρτηση καλεί τον εαυτό της.
Αν και στις περισσότερες περιπτώσεις δεν έχει πραγματική πρακτική εφαρμογή, μπορείς να ανακαλύψεις πόσο ψηλά μπορεί να φτάσει αυτή η στοίβα.
let calls = 0;
function kaboom() {
calls +=1 ;
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
console.log(calls)
// => a number, generally higher than 10.000
Υπάρχουν μόνο δύο βιώσιμες λύσεις για ένα σφάλμα στοίβας κλήσεων που προκαλείται από μια αναδρομική συνάρτηση που εκτελείται σύγχρονα:
- φρόντισε οι συναρτήσεις να επιστρέφουν πριν φτάσει το όριο της στοίβας, συνήθως προσθέτοντας ή διορθώνοντας μια βασική περίπτωση.
- ξαναγράψε την αναδρομική συνάρτηση ως προστακτικό βρόχο, ο οποίος θα εκτελεί το σώμα του βρόχου χωρίς να χρειάζεται να εισέλθει σε συνάρτηση, άρα χωρίς να αυξάνει τη στοίβα.
Άσκηση εκμάθησης
