Αυτό το σε βάθος σεμινάριο για την Αναδρομή στη Java εξηγεί τι είναι η Αναδρομή με παραδείγματα, τύπους και συναφείς έννοιες. Καλύπτει επίσης την Αναδρομή έναντι της Επανάληψης:
Από τα προηγούμενα σεμινάριά μας στη Java, έχουμε δει την επαναληπτική προσέγγιση κατά την οποία δηλώνουμε έναν βρόχο και στη συνέχεια διατρέχουμε μια δομή δεδομένων με επαναληπτικό τρόπο, παίρνοντας ένα στοιχείο κάθε φορά.
Είδαμε επίσης τη ροή υπό συνθήκη, όπου και πάλι κρατάμε μια μεταβλητή βρόχου και επαναλαμβάνουμε ένα κομμάτι κώδικα μέχρι η μεταβλητή βρόχου να ικανοποιήσει τη συνθήκη. Όταν πρόκειται για κλήσεις συναρτήσεων, εξερευνήσαμε την επαναληπτική προσέγγιση και για κλήσεις συναρτήσεων.
Σε αυτό το σεμινάριο, θα συζητήσουμε μια διαφορετική προσέγγιση στον προγραμματισμό, δηλαδή την αναδρομική προσέγγιση.
Τι είναι η αναδρομή στη Java;
Η αναδρομή είναι μια διαδικασία με την οποία μια συνάρτηση ή μια μέθοδος καλεί τον εαυτό της ξανά και ξανά. Αυτή η συνάρτηση που καλείται ξανά και ξανά είτε άμεσα είτε έμμεσα ονομάζεται "αναδρομική συνάρτηση".
Θα δούμε διάφορα παραδείγματα για να κατανοήσουμε την αναδρομή. Ας δούμε τώρα τη σύνταξη της αναδρομής.
Σύνταξη αναδρομής
Κάθε μέθοδος που υλοποιεί την Αναδρομή έχει δύο βασικά μέρη:
- Κλήση μεθόδου που μπορεί να καλεί τον εαυτό της, δηλαδή αναδρομική
- Μια προϋπόθεση που θα σταματήσει την αναδρομή.
Σημειώστε ότι μια προϋπόθεση είναι απαραίτητη για κάθε αναδρομική μέθοδο, καθώς, αν δεν διακόψουμε την αναδρομή, τότε αυτή θα συνεχίσει να εκτελείται άπειρες φορές και θα οδηγήσει σε υπερχείλιση στοίβας.
Η γενική σύνταξη της αναδρομής έχει ως εξής:
methodName (T parameters...) { if (precondition == true) //προϋπόθεση ή βασική συνθήκη { return result; } return methodName (T parameters...); //αναδρομική κλήση } Σημειώστε ότι η προϋπόθεση ονομάζεται επίσης βασική συνθήκη. Θα συζητήσουμε περισσότερα για τη βασική συνθήκη στην επόμενη ενότητα.
Κατανόηση της αναδρομής στη Java
Σε αυτή την ενότητα, θα προσπαθήσουμε να κατανοήσουμε τη διαδικασία της αναδρομής και να δούμε πώς πραγματοποιείται. Θα μάθουμε για τη βασική συνθήκη, την υπερχείλιση στοίβας και θα δούμε πώς μπορεί να λυθεί ένα συγκεκριμένο πρόβλημα με αναδρομή και άλλες τέτοιες λεπτομέρειες.
Αναδρομή Βασική συνθήκη
Κατά τη συγγραφή του αναδρομικού προγράμματος, θα πρέπει πρώτα να δώσουμε τη λύση για τη βασική περίπτωση. Στη συνέχεια εκφράζουμε το μεγαλύτερο πρόβλημα σε όρους μικρότερων προβλημάτων.
Ως παράδειγμα, μπορούμε να πάρουμε ένα κλασικό πρόβλημα υπολογισμού του παραγοντικού ενός αριθμού. Δεδομένου ενός αριθμού n, πρέπει να βρούμε ένα παραγοντικό του n που συμβολίζεται με n!
Τώρα ας υλοποιήσουμε το πρόγραμμα για τον υπολογισμό του n παραγοντικού (n!) χρησιμοποιώντας αναδρομή.
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Έξοδος
Σε αυτό το πρόγραμμα, μπορούμε να δούμε ότι η συνθήκη (n<=1) είναι η βασική συνθήκη και όταν επιτευχθεί αυτή η συνθήκη, η συνάρτηση επιστρέφει 1. Το else μέρος της συνάρτησης είναι η αναδρομική κλήση. Αλλά κάθε φορά που καλείται η αναδρομική μέθοδος, το n μειώνεται κατά 1.
Έτσι μπορούμε να συμπεράνουμε ότι τελικά η τιμή του n θα γίνει 1 ή μικρότερη από 1 και σε αυτό το σημείο, η μέθοδος θα επιστρέψει την τιμή 1. Αυτή η βασική συνθήκη θα επιτευχθεί και η συνάρτηση θα σταματήσει. Σημειώστε ότι η τιμή του n μπορεί να είναι οτιδήποτε, αρκεί να ικανοποιεί τη βασική συνθήκη.
Επίλυση προβλημάτων με χρήση αναδρομής
Η βασική ιδέα πίσω από τη χρήση της αναδρομής είναι η έκφραση του μεγαλύτερου προβλήματος σε όρους μικρότερων προβλημάτων. Επίσης, πρέπει να προσθέσουμε μία ή περισσότερες βασικές συνθήκες ώστε να μπορέσουμε να βγούμε από την αναδρομή.
Αυτό είχε ήδη αποδειχθεί στο παραπάνω παραγοντικό παράδειγμα. Σε αυτό το πρόγραμμα, εκφράσαμε το παραγοντικό n (n!) σε όρους μικρότερων τιμών και είχαμε μια βασική συνθήκη (n <=1) έτσι ώστε όταν το n φτάσει στο 1, να μπορούμε να εγκαταλείψουμε την αναδρομική μέθοδο.
Σφάλμα υπερχείλισης στοίβας στην αναδρομή
Γνωρίζουμε ότι όταν καλείται οποιαδήποτε μέθοδος ή συνάρτηση, η κατάσταση της συνάρτησης αποθηκεύεται στη στοίβα και ανακτάται όταν η συνάρτηση επιστρέφει. Η στοίβα χρησιμοποιείται και για την αναδρομική μέθοδο.
Αλλά στην περίπτωση της αναδρομής, μπορεί να προκύψει πρόβλημα αν δεν ορίσουμε τη βασική συνθήκη ή αν η βασική συνθήκη δεν επιτευχθεί ή δεν εκτελεστεί με κάποιο τρόπο. Αν συμβεί αυτή η κατάσταση, τότε μπορεί να προκύψει υπερχείλιση στοίβας.
Ας εξετάσουμε το παρακάτω παράδειγμα παραγοντικού συμβολισμού.
Εδώ έχουμε δώσει μια λανθασμένη βασική συνθήκη, n==100.
public class Main { static int fact(int n) { if (n == 100) // βασική συνθήκη που οδηγεί σε υπερχείλιση στοίβας return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Έτσι, όταν n> 100 η μέθοδος θα επιστρέψει 1 αλλά η αναδρομή δεν θα σταματήσει. Η τιμή του n θα συνεχίσει να μειώνεται επ' αόριστον, καθώς δεν υπάρχει άλλη συνθήκη για να τη σταματήσει. Αυτό θα συνεχιστεί μέχρι να υπερχειλίσει η στοίβα.
Μια άλλη περίπτωση θα είναι όταν η τιμή του n <100. Και σε αυτή την περίπτωση, η μέθοδος δεν θα εκτελέσει ποτέ τη βασική συνθήκη και θα οδηγήσει σε υπερχείλιση στοίβας.
Παραδείγματα αναδρομής στη Java
Σε αυτή την ενότητα, θα υλοποιήσουμε τα ακόλουθα παραδείγματα χρησιμοποιώντας αναδρομή.
#1) Σειρά Fibonacci χρησιμοποιώντας αναδρομή
Η σειρά Fibonacci δίνεται από,
1,1,2,3,5,8,13,21,34,55,…
Η παραπάνω ακολουθία δείχνει ότι το τρέχον στοιχείο είναι το άθροισμα των δύο προηγούμενων στοιχείων. Επίσης, το πρώτο στοιχείο στη σειρά Fibonacci είναι το 1.
Έτσι, γενικά, αν το n είναι ο τρέχων αριθμός, τότε δίνεται από το άθροισμα των (n-1) και (n-2). Καθώς το τρέχον στοιχείο εκφράζεται με βάση τα προηγούμενα στοιχεία, μπορούμε να εκφράσουμε αυτό το πρόβλημα χρησιμοποιώντας αναδρομή.
Το πρόγραμμα για την εφαρμογή της σειράς Fibonacci δίνεται παρακάτω:
public class Main { //μέθοδος υπολογισμού της σειράς fibonacci static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String[] args) { int number = 10; //εκτυπώνουμε τους 10 πρώτους αριθμούς της σειράς fibonacci System.out.println ("Σειρά Fibonacci: Πρώτοι 10 αριθμοί:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " "),} } } Έξοδος
#2) Ελέγξτε αν ένας αριθμός είναι παλίνδρομο χρησιμοποιώντας αναδρομή
Ένα παλίνδρομο είναι μια ακολουθία που είναι ίση όταν τη διαβάζουμε από αριστερά προς τα δεξιά ή από δεξιά προς τα αριστερά.
Δεδομένου του αριθμού 121, βλέπουμε ότι όταν τον διαβάζουμε από αριστερά προς τα δεξιά και από δεξιά προς τα αριστερά, είναι ίσος. Επομένως, ο αριθμός 121 είναι παλίνδρομο.
Ας πάρουμε έναν άλλο αριθμό, τον 1242. Όταν τον διαβάζουμε από αριστερά προς τα δεξιά είναι 1242 και όταν τον διαβάζουμε από δεξιά προς τα αριστερά διαβάζεται ως 2421. Επομένως, δεν πρόκειται για παλίνδρομο.
Υλοποιούμε το πρόγραμμα παλίνδρομο αντιστρέφοντας τα ψηφία των αριθμών και συγκρίνουμε αναδρομικά τον δεδομένο αριθμό με την αντίστροφη αναπαράστασή του.
Το παρακάτω πρόγραμμα υλοποιεί το πρόγραμμα για τον έλεγχο του παλίνδρομου.
import java.io.*; import java.util.*; public class Main { // έλεγχος αν ο αριθμός περιέχει μόνο ένα ψηφίο public static int oneDigit(int num) { if ((num>= 0) && (num <10)) return 1; else return 0; } //λειτουργία χρησιμότητας παλίνδρομου public static int isPalindrome_util (int num, int revNum) throws Exception { // βασική συνθήκη- return if num=0 if (num == 0) { return revNum; } else { //callutility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Ελέγξτε αν το πρώτο ψηφίο του num και του revNum είναι ίσο if (num % 10 == revNum % 10) { // αν ναι, το revNum θα κινηθεί με το num return revNum / 10; } else { // exit throw new Exception(); } } } //μέθοδος για να ελέγξετε αν ένας δεδομένος αριθμός είναι παλίνδρομος χρησιμοποιώντας την utility function palindrome public static int isPalindrome(int num) throwsException { if (num <0) num = (-num), int revNum = (num), return isPalindrome_util(num, revNum), } public static void main(String args[]) { int n = 1242, try { isPalindrome(n), System.out.println("Ναι, ο συγκεκριμένος αριθμός " + n + " είναι παλίνδρομο."), } catch (Exception e) { System.out.println("Όχι, ο συγκεκριμένος αριθμός " + n + " δεν είναι παλίνδρομο."), } n = 1221, try { isPalindrome(n),System.out.println("Ναι, ο συγκεκριμένος αριθμός " + n + " είναι παλίνδρομο."); } catch (Exception e) { System.out.println("Όχι, ο συγκεκριμένος αριθμός " + n + " δεν είναι παλίνδρομο."); } } } Έξοδος
#3) Αντίστροφη αναδρομή συμβολοσειράς Java
Δεδομένου ενός αλφαριθμητικού "Hello" πρέπει να το αντιστρέψουμε έτσι ώστε το προκύπτον αλφαριθμητικό να είναι "olleH".
Ξεκινώντας από τον τελευταίο χαρακτήρα της συμβολοσειράς εκτυπώνουμε αναδρομικά κάθε χαρακτήρα μέχρι να εξαντληθούν όλοι οι χαρακτήρες της συμβολοσειράς.
Το παρακάτω πρόγραμμα χρησιμοποιεί την αναδρομή για να αντιστρέψει μια δεδομένη συμβολοσειρά.
class String_Reverse { //αναδρομική μέθοδος για την αντιστροφή μιας δεδομένης συμβολοσειράς void reverseString(String str) { //βασική συνθήκη- επιστρέφει αν η συμβολοσειρά είναι null ή με 1 ή λιγότερο χαρακτήρα if ((str==null)} } } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Η δεδομένη συμβολοσειρά: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Η αντιστραμμένη συμβολοσειρά: "); obj.reverseString(inputstr); } } Έξοδος
#4) Δυαδική αναζήτηση Java Αναδρομή
Ο αλγόριθμος δυαδικής αναζήτησης είναι ένας διάσημος αλγόριθμος αναζήτησης. Σε αυτόν τον αλγόριθμο, δεδομένου ενός ταξινομημένου πίνακα n στοιχείων, αναζητούμε τον πίνακα αυτό για το δεδομένο στοιχείο-κλειδί. Στην αρχή, χωρίζουμε τον πίνακα σε δύο μισά βρίσκοντας το μεσαίο στοιχείο του πίνακα.
Στη συνέχεια, ανάλογα με το αν το κλειδί είναι μεσαίο περιορίζουμε την αναζήτησή μας στο πρώτο ή στο δεύτερο μισό του πίνακα. Με αυτόν τον τρόπο επαναλαμβάνεται η ίδια διαδικασία μέχρι να βρεθεί η θέση των στοιχείων κλειδιών.
Θα υλοποιήσουμε αυτόν τον αλγόριθμο χρησιμοποιώντας αναδρομή εδώ.
import java.util.*; class Binary_Search { // αναδρομική δυαδική αναζήτηση int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { // υπολογίζουμε το μέσο του πίνακα int mid = left + (right - left) / 2; // αν το κλειδί είναι στο μέσο, επιστρέφουμε το μέσο if (numArray[mid] == key) return mid; // αν κλειδί key) return binarySearch(numArray, left, mid - 1, key); // Αλλιώς αναδρομική αναζήτηση στοδεξιά υποσυστοιχία return binarySearch(numArray, mid + 1, right, key); } // δεν υπάρχουν στοιχεία στον πίνακα, επιστρέφουμε -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //δηλώνουμε και εκτυπώνουμε τον πίνακα int numArray[] = { 4,6,12,16,22}; System.out.println("Ο συγκεκριμένος πίνακας : " + Arrays.toString(numArray)); int len = numArray.length; //μήκος του πίνακαint key = 16; //κλειδί προς αναζήτηση int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Element " + key + " not present"); else System.out.println("Element " + key + " found at index " + result); } } Έξοδος
#5) Εύρεση ελάχιστης τιμής σε συστοιχία χρησιμοποιώντας αναδρομή
Χρησιμοποιώντας την αναδρομή μπορούμε επίσης να βρούμε την ελάχιστη τιμή στον πίνακα.
Το πρόγραμμα Java για την εύρεση της ελάχιστης τιμής στον πίνακα δίνεται παρακάτω.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //επιστρέφει το πρώτο στοιχείο αν είναι μόνο ένα στοιχείο ή το ελάχιστο των στοιχείων του πίνακα return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Δεδομένος πίνακας : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Ελάχιστο στοιχείο του πίνακα: " + getMin(numArray, 0, n) + "\n"); } } Έξοδος
Αυτά είναι μερικά από τα παραδείγματα αναδρομής. Εκτός από αυτά τα παραδείγματα, πολλά άλλα προβλήματα στο λογισμικό μπορούν να υλοποιηθούν με τη χρήση αναδρομικών τεχνικών.
Τύποι αναδρομής
Η αναδρομή διακρίνεται σε δύο τύπους ανάλογα με το πότε γίνεται η κλήση της αναδρομικής μεθόδου.
Είναι:
#1) Αναδρομή ουράς
Όταν η κλήση της αναδρομικής μεθόδου είναι η τελευταία εντολή που εκτελείται μέσα στην αναδρομική μέθοδο, ονομάζεται "Αναδρομή ουράς".
Στην αναδρομή ουράς, η δήλωση αναδρομικής κλήσης εκτελείται συνήθως μαζί με τη δήλωση επιστροφής της μεθόδου.
Η γενική σύνταξη για την αναδρομή ουράς δίνεται παρακάτω:
methodName ( T parameters...){ { if (base_condition == true) { return result; } return methodName (T parameters ...) //tail recursion } #2) Αναδρομή κεφαλής
Αναδρομή κεφαλής είναι κάθε αναδρομική προσέγγιση που δεν είναι αναδρομή ουράς. Έτσι, ακόμη και η γενική αναδρομή είναι αναδρομή κεφαλής.
Η σύνταξη της αναδρομής κεφαλής έχει ως εξής:
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...); } return result; } Αναδρομή Vs Επαναλήψεις στην Java
| Αναδρομή | Επανάληψη |
|---|---|
| Η αναδρομή είναι μια διαδικασία κατά την οποία μια μέθοδος καλεί τον εαυτό της επανειλημμένα μέχρι να ικανοποιηθεί μια βασική συνθήκη. | Η επανάληψη είναι μια διαδικασία με την οποία ένα κομμάτι κώδικα εκτελείται επανειλημμένα για έναν πεπερασμένο αριθμό φορών ή μέχρι να ικανοποιηθεί μια συνθήκη. |
| Είναι η εφαρμογή για λειτουργίες. | Ισχύει για βρόχους. |
| Λειτουργεί καλά για μικρότερο μέγεθος κώδικα. | Λειτουργεί καλά για μεγαλύτερο μέγεθος κώδικα. |
| Χρησιμοποιεί περισσότερη μνήμη καθώς κάθε αναδρομική κλήση μεταφέρεται στη στοίβα | Χρησιμοποιείται συγκριτικά λιγότερη μνήμη. |
| Δύσκολη αποσφαλμάτωση και συντήρηση | Ευκολότερη αποσφαλμάτωση και συντήρηση |
| Οδηγεί σε υπερχείλιση στοίβας εάν η βασική συνθήκη δεν έχει καθοριστεί ή δεν έχει επιτευχθεί. | Μπορεί να εκτελείται απεριόριστα, αλλά τελικά θα σταματήσει την εκτέλεση με τυχόν σφάλματα μνήμης. |
| Η χρονική πολυπλοκότητα είναι πολύ υψηλή. | Η χρονική πολυπλοκότητα είναι σχετικά χαμηλή. |
Συχνές ερωτήσεις
Q #1) Πώς λειτουργεί η Αναδρομή στη Java;
Απαντήστε: Στην αναδρομή, η αναδρομική συνάρτηση καλεί τον εαυτό της επανειλημμένα μέχρι να ικανοποιηθεί μια βασική συνθήκη. Η μνήμη για την καλούμενη συνάρτηση ωθείται στη στοίβα στην κορυφή της μνήμης της καλούσας συνάρτησης. Για κάθε κλήση συνάρτησης, δημιουργείται ξεχωριστό αντίγραφο των τοπικών μεταβλητών.
Q #2) Γιατί χρησιμοποιείται η Αναδρομή;
Απαντήστε: Η αναδρομή χρησιμοποιείται για την επίλυση εκείνων των προβλημάτων που μπορούν να αναλυθούν σε μικρότερα και ολόκληρο το πρόβλημα μπορεί να εκφραστεί σε όρους ενός μικρότερου προβλήματος.
Η αναδρομή χρησιμοποιείται επίσης για τα προβλήματα που είναι πολύ πολύπλοκα για να επιλυθούν με επαναληπτική προσέγγιση. Εκτός από τα προβλήματα για τα οποία η χρονική πολυπλοκότητα δεν αποτελεί πρόβλημα, χρησιμοποιήστε την αναδρομή.
Q #3) Ποια είναι τα οφέλη της Αναδρομής;
Απαντήστε:
Τα οφέλη της Αναδρομής περιλαμβάνουν:
- Η αναδρομή μειώνει την περιττή κλήση της συνάρτησης.
- Η αναδρομή μας επιτρέπει να επιλύουμε προβλήματα εύκολα σε σύγκριση με την επαναληπτική προσέγγιση.
Q #4) Ποιο από τα δύο είναι καλύτερο - Αναδρομή ή Επανάληψη;
Απαντήστε: Η αναδρομή πραγματοποιεί επαναλαμβανόμενες κλήσεις μέχρι να επιτευχθεί η βασική συνάρτηση. Έτσι υπάρχει επιβάρυνση μνήμης, καθώς μια μνήμη για κάθε κλήση συνάρτησης ωθείται στη στοίβα.
Η επανάληψη από την άλλη πλευρά δεν έχει μεγάλη επιβάρυνση μνήμης. Η εκτέλεση με αναδρομή είναι πιο αργή από την επαναληπτική προσέγγιση. Η αναδρομή μειώνει το μέγεθος του κώδικα, ενώ η επαναληπτική προσέγγιση καθιστά τον κώδικα μεγάλο.
Q #5) Ποια είναι τα πλεονεκτήματα της αναδρομής έναντι της επανάληψης;
Απαντήστε:
- Η αναδρομή καθιστά τον κώδικα σαφέστερο και συντομότερο.
- Η αναδρομή είναι καλύτερη από την επαναληπτική προσέγγιση για προβλήματα όπως ο Πύργος του Ανόι, οι διαβάσεις δέντρων, κ.λπ.
- Καθώς σε κάθε κλήση συνάρτησης η μνήμη μεταφέρεται στη στοίβα, η Αναδρομή χρησιμοποιεί περισσότερη μνήμη.
- Η απόδοση της αναδρομής είναι πιο αργή από την επαναληπτική προσέγγιση.
Συμπέρασμα
Η αναδρομή είναι μια πολύ σημαντική έννοια στο λογισμικό, ανεξάρτητα από τη γλώσσα προγραμματισμού. Η αναδρομή χρησιμοποιείται κυρίως για την επίλυση προβλημάτων δομής δεδομένων, όπως οι πύργοι του Ανόι, οι διελεύσεις δέντρων, οι συνδεδεμένες λίστες κ.λπ. Αν και απαιτεί περισσότερη μνήμη, η αναδρομή κάνει τον κώδικα απλούστερο και σαφέστερο.
Έχουμε εξερευνήσει τα πάντα για την Αναδρομή σε αυτό το σεμινάριο. Έχουμε επίσης υλοποιήσει πολυάριθμα παραδείγματα προγραμματισμού για την καλύτερη κατανόηση της έννοιας.