recursion java tutorial with examples
Αυτό το σε βάθος εκπαιδευτικό πρόγραμμα για την αναδρομή στην Java εξηγεί τι είναι η αναδρομή με παραδείγματα, τύπους και συναφείς έννοιες. Καλύπτει επίσης το Recursion Vs Iteration:
Από τα προηγούμενα σεμινάρια μας στην Java, έχουμε δει την επαναληπτική προσέγγιση στην οποία δηλώνουμε έναν βρόχο και στη συνέχεια διασχίζουμε μια δομή δεδομένων με επαναληπτικό τρόπο λαμβάνοντας ένα στοιχείο κάθε φορά.
Έχουμε επίσης δει τη ροή υπό όρους όπου και πάλι διατηρούμε μια μεταβλητή βρόχου και επαναλαμβάνουμε ένα κομμάτι κώδικα έως ότου η μεταβλητή βρόχου πληροί την συνθήκη. Όσον αφορά τις λειτουργικές κλήσεις, διερευνήσαμε επίσης την επαναληπτική προσέγγιση για τις λειτουργικές κλήσεις.
=> Ελέγξτε ΟΛΑ τα Εκπαιδευτικά Java εδώ.
Σε αυτό το σεμινάριο, θα συζητήσουμε μια διαφορετική προσέγγιση στον προγραμματισμό, δηλαδή την αναδρομική προσέγγιση.
Τι θα μάθετε:
- Τι είναι η αναδρομή στην Java;
- Επανάληψη Vs Επανάληψη στην Ιάβα
- συμπέρασμα
Τι είναι η αναδρομή στην Java;
Η αναδρομή είναι μια διαδικασία με την οποία μια συνάρτηση ή μια μέθοδος αποκαλείται ξανά και ξανά. Αυτή η συνάρτηση που καλείται ξανά και ξανά είτε άμεσα είτε έμμεσα ονομάζεται «αναδρομική συνάρτηση».
Θα δούμε διάφορα παραδείγματα για να κατανοήσουμε την επανάληψη. Τώρα ας δούμε τη σύνταξη της αναδρομής.
Σύνταξη αναδρομής
Οποιαδήποτε μέθοδος που εφαρμόζει το Recursion έχει δύο βασικά μέρη:
- Μέθοδος κλήσης που μπορεί να ονομαστεί, δηλαδή αναδρομική
- Προϋπόθεση που θα σταματήσει την επανάληψη.
Σημειώστε ότι είναι απαραίτητη μια προϋπόθεση για οποιαδήποτε αναδρομική μέθοδο, καθώς, αν δεν σπάσουμε την επανάληψη, τότε θα συνεχίσει να λειτουργεί απεριόριστα και θα έχει ως αποτέλεσμα υπερχείλιση στοίβας.
Η γενική σύνταξη της αναδρομής έχει ως εξής:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Σημειώστε ότι η προϋπόθεση ονομάζεται επίσης βασική συνθήκη. Θα συζητήσουμε περισσότερα σχετικά με τη βασική κατάσταση στην επόμενη ενότητα.
Κατανόηση της αναδρομής στην Java
Σε αυτήν την ενότητα, θα προσπαθήσουμε να κατανοήσουμε τη διαδικασία αναδρομής και να δούμε πώς γίνεται. Θα μάθουμε για τη βασική κατάσταση, την υπερχείλιση στοίβας και θα δούμε πώς μπορεί να λυθεί ένα συγκεκριμένο πρόβλημα με την επανάληψη και άλλες τέτοιες λεπτομέρειες.
Βάση αναδρομής
Κατά τη σύνταξη του αναδρομικού προγράμματος, πρέπει πρώτα να παρέχουμε τη λύση για τη βασική περίπτωση. Στη συνέχεια, εκφράζουμε το μεγαλύτερο πρόβλημα σε σχέση με μικρότερα προβλήματα.
Ως παράδειγμα, μπορούμε να πάρουμε ένα κλασικό πρόβλημα υπολογισμού του παραγοντικού ενός αριθμού. Δεδομένου του αριθμού n, πρέπει να βρούμε ένα παραγοντικό του n που υποδηλώνεται από το n!
Τώρα ας εφαρμόσουμε το πρόγραμμα για να υπολογίσουμε το n factorial (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) is the base condition and when this condition is reached, the function returns 1. The else part of the function is the recursive call. But every time the recursive method is called, n is decremented by 1.
Έτσι μπορούμε να συμπεράνουμε ότι τελικά η τιμή του n θα γίνει 1 ή μικρότερη από 1 και σε αυτό το σημείο, η μέθοδος θα επιστρέψει την τιμή 1. Αυτή η βασική συνθήκη θα επιτευχθεί και η συνάρτηση θα σταματήσει. Σημειώστε ότι η τιμή του n μπορεί να είναι οτιδήποτε εφόσον ικανοποιεί τη βασική συνθήκη.
Επίλυση προβλημάτων χρησιμοποιώντας αναδρομή
Η βασική ιδέα πίσω από τη χρήση της αναδρομής είναι να εκφράσουμε το μεγαλύτερο πρόβλημα όσον αφορά τα μικρότερα προβλήματα. Επίσης, πρέπει να προσθέσουμε μία ή περισσότερες βασικές συνθήκες ώστε να μπορέσουμε να βγούμε από την επανάληψη.
Αυτό αποδείχθηκε ήδη στο παραπάνω παραγοντικό παράδειγμα. Σε αυτό το πρόγραμμα, εκφράσαμε το n factorial (n!) Σε όρους μικρότερων τιμών και είχαμε μια βασική συνθήκη (n<=1) so that when n reaches 1, we can quit the recursive method.
Σφάλμα υπερχείλισης στοίβας κατά την επανάληψη
Γνωρίζουμε ότι όταν καλείται οποιαδήποτε μέθοδο ή συνάρτηση, η κατάσταση της συνάρτησης αποθηκεύεται στη στοίβα και ανακτάται όταν επιστρέφει η συνάρτηση. Η στοίβα χρησιμοποιείται και για την αναδρομική μέθοδο.
Ωστόσο, σε περίπτωση αναδρομής, ενδέχεται να προκύψει πρόβλημα εάν δεν καθορίσουμε τη βασική κατάσταση ή όταν η βασική συνθήκη δεν έχει επιτευχθεί ή εκτελεστεί. Εάν συμβεί αυτή η κατάσταση, ενδέχεται να προκύψει υπερχείλιση στοίβας.
Ας εξετάσουμε το παρακάτω παράδειγμα παραγοντικής συμβολής.
Εδώ έχουμε δώσει μια λάθος βασική συνθήκη, n == 100.
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow 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. In this case, as well the method will never execute the base condition and result in a stack overflow.
Παραδείγματα επανάληψης στην 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 { //method to calculate fibonacci series 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; //print first 10 numbers of fibonacci series System.out.println ('Fibonacci Series: First 10 numbers:'); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + ' '); } } } Παραγωγή
# 2) Ελέγξτε εάν ένας αριθμός είναι Palindrome χρησιμοποιώντας την αναδρομή
Το palindrome είναι μια ακολουθία που είναι ίση όταν το διαβάζουμε από αριστερά προς τα δεξιά ή από τα δεξιά προς τα αριστερά.
Δεδομένου του αριθμού 121, βλέπουμε ότι όταν το διαβάζουμε από αριστερά προς τα δεξιά και από τα δεξιά προς τα αριστερά, είναι ίσο. Ως εκ τούτου, ο αριθμός 121 είναι ένα περίγραμμα.
Ας πάρουμε έναν άλλο αριθμό, 1242. Όταν το διαβάζουμε από αριστερά προς τα δεξιά είναι 1242 και όταν το διαβάζουμε από δεξιά προς τα αριστερά διαβάζεται ως 2421. Επομένως, αυτό δεν είναι παλέντουμ.
Εφαρμόζουμε το πρόγραμμα palindrome αναστρέφοντας τα ψηφία των αριθμών και συγκρίνουμε αναδρομικά τον δεδομένο αριθμό με την αντίστροφη αναπαράστασή του.
Το παρακάτω πρόγραμμα εφαρμόζει το πρόγραμμα για να ελέγξετε το palindrome.
import java.io.*; import java.util.*; public class Main { // check if num contains only one digit public static int oneDigit(int num) { if ((num >= 0) && (num <10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // base condition; return if num=0 if (num == 0) { return revNum; } else { //call utility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Check if first digit of num and revNum are equal if (num % 10 == revNum % 10) { // if yes, revNum will move with num return revNum / 10; } else { // exit throw new Exception(); } } //method to check if a given number is palindrome using palindrome utility function public static int isPalindrome(int num) throws Exception { 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('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } n = 1221; try { isPalindrome(n); System.out.println('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } } }Παραγωγή
# 3) Reverse String Recursion Java
Λαμβάνοντας υπόψη μια συμβολοσειρά 'Γεια' πρέπει να την αντιστρέψουμε έτσι ώστε η προκύπτουσα συμβολοσειρά να είναι 'olleH'.
Αυτό γίνεται χρησιμοποιώντας αναδρομή. Ξεκινώντας από τον τελευταίο χαρακτήρα στη συμβολοσειρά εκτυπώνουμε αναδρομικά κάθε χαρακτήρα έως ότου εξαντληθούν όλοι οι χαρακτήρες στη συμβολοσειρά.
Το παρακάτω πρόγραμμα χρησιμοποιεί αναδρομή για να αντιστρέψει μια δεδομένη συμβολοσειρά.
class String_Reverse { //recursive method to reverse a given string void reverseString(String str) { //base condition; return if string is null or with 1 or less character if ((str==null)||(str.length() <= 1)) System.out.println(str); else { //recursively print each character in the string from the end System.out.print(str.charAt(str.length()-1)); reverseString(str.substring(0,str.length()-1)); } } } class Main{ public static void main(String() args) { String inputstr = 'SoftwareTestingHelp'; System.out.println('The given string: ' + inputstr); String_Reverse obj = new String_Reverse(); System.out.print('The reversed string: '); obj.reverseString(inputstr); } } Παραγωγή
# 4) Αναδρομή δυαδικής αναζήτησης Java
Ένας αλγόριθμος δυαδικής αναζήτησης είναι ένας διάσημος αλγόριθμος αναζήτησης. Σε αυτόν τον αλγόριθμο, δεδομένου ενός ταξινομημένου πίνακα n στοιχείων, αναζητούμε αυτόν τον πίνακα για το δεδομένο βασικό στοιχείο. Στην αρχή, χωρίζουμε τον πίνακα σε δύο μισά βρίσκοντας το μεσαίο στοιχείο του πίνακα.
Στη συνέχεια, ανάλογα με το αν το κλειδί στα μέσα περιορίζουμε την αναζήτησή μας στο πρώτο ή το δεύτερο μισό του πίνακα. Με αυτόν τον τρόπο επαναλαμβάνεται η ίδια διαδικασία μέχρι να βρεθεί η θέση των βασικών στοιχείων.
Θα εφαρμόσουμε αυτόν τον αλγόριθμο χρησιμοποιώντας αναδρομή εδώ.
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray(), int left, int right, int key) { if (right >= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray(mid) == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search in the right subarray return binarySearch(numArray, mid + 1, right, key); } // no elements in the array, return -1 return -1; } } class Main{ public static void main(String args()) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray() = { 4,6,12,16,22}; System.out.println('The given array : ' + Arrays.toString(numArray)); int len = numArray.length; //length of the array int key = 16; //key to be searched 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 first element if only one element or minimum of the array elements 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('Given Array : ' + Arrays.toString(numArray)); int n = numArray.length; System.out.print('Minimum element of array: ' + getMin(numArray, 0, n) + '
'); } }Παραγωγή
Αυτά είναι μερικά από τα παραδείγματα της επανάληψης. Εκτός από αυτά τα παραδείγματα, πολλά άλλα προβλήματα στο λογισμικό μπορούν να εφαρμοστούν χρησιμοποιώντας αναδρομικές τεχνικές.
Τύποι αναδρομής
Η επανάληψη είναι δύο τύπων με βάση το πότε πραγματοποιείται η κλήση στην αναδρομική μέθοδο.
Αυτοί είναι:
# 1) Επανάληψη ουράς
Όταν η κλήση προς την αναδρομική μέθοδο είναι η τελευταία δήλωση που εκτελείται μέσα στην αναδρομική μέθοδο, ονομάζεται «Tail Recursion».
Στην ουρά αναδρομής, η αναδρομική δήλωση κλήσης εκτελείται συνήθως μαζί με τη δήλωση επιστροφής της μεθόδου.
Η γενική σύνταξη για αναδρομή ουράς δίνεται παρακάτω:
ερωτήσεις και απαντήσεις συνέντευξης μηχανικού διασφάλισης ποιότητας
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 Επανάληψη στην Ιάβα
| Αναδρομή | Επανάληψη |
|---|---|
| Η πολυπλοκότητα του χρόνου είναι πολύ υψηλή. | Η πολυπλοκότητα του χρόνου είναι σχετικά χαμηλότερη. |
| Η επανάληψη είναι μια διαδικασία όπου μια μέθοδος καλείται επανειλημμένα έως ότου ικανοποιηθεί μια βασική συνθήκη. | Η επανάληψη είναι μια διαδικασία με την οποία ένα κομμάτι κώδικα εκτελείται επανειλημμένα για πεπερασμένες φορές ή έως ότου πληρούται μια συνθήκη. |
| Είναι η εφαρμογή για συναρτήσεις. | Ισχύει για βρόχους. |
| Λειτουργεί καλά για μικρότερο μέγεθος κώδικα. | Λειτουργεί καλά για μεγαλύτερο μέγεθος κώδικα. |
| Χρησιμοποιεί περισσότερη μνήμη καθώς κάθε αναδρομική κλήση ωθείται στη στοίβα | Συγκριτικά λιγότερη μνήμη χρησιμοποιείται. |
| Δύσκολο εντοπισμό σφαλμάτων και συντήρηση | Ευκολότερο για εντοπισμό σφαλμάτων και συντήρηση |
| Αποτελεί υπερχείλιση στοίβας εάν η βασική συνθήκη δεν έχει καθοριστεί ή δεν επιτευχθεί. | Μπορεί να εκτελεστεί απεριόριστα, αλλά τελικά θα σταματήσει την εκτέλεση με τυχόν σφάλματα μνήμης |
Συχνές Ερωτήσεις
Ε # 1) Πώς λειτουργεί το Recursion στην Java;
Απάντηση: Στην αναδρομή, η αναδρομική συνάρτηση καλείται επανειλημμένα έως ότου ικανοποιηθεί μια βασική συνθήκη. Η μνήμη για τη λειτουργία που καλείται ωθείται στη στοίβα στο πάνω μέρος της μνήμης για τη λειτουργία κλήσης. Για κάθε κλήση συνάρτησης, δημιουργείται ξεχωριστό αντίγραφο τοπικών μεταβλητών.
Q # 2) Γιατί χρησιμοποιείται το Recursion;
Απάντηση: Η αναδρομή χρησιμοποιείται για την επίλυση αυτών των προβλημάτων που μπορούν να χωριστούν σε μικρότερα και ολόκληρο το πρόβλημα μπορεί να εκφραστεί με όρους μικρότερου προβλήματος.
Η αναδρομή χρησιμοποιείται επίσης για εκείνα τα προβλήματα που είναι πολύ περίπλοκα για να επιλυθούν χρησιμοποιώντας επαναληπτική προσέγγιση. Εκτός από τα προβλήματα για τα οποία η χρονική πολυπλοκότητα δεν αποτελεί πρόβλημα, χρησιμοποιήστε την επανάληψη.
Q # 3) Ποια είναι τα οφέλη της αναδρομής;
Απάντηση:
Τα οφέλη του Recursion περιλαμβάνουν:
- Η αναδρομή μειώνει την περιττή κλήση λειτουργίας.
- Η επανάληψη μας επιτρέπει να λύσουμε εύκολα προβλήματα σε σύγκριση με την επαναληπτική προσέγγιση.
Q # 4) Ποιο είναι καλύτερο - Επανάληψη ή επανάληψη;
Απάντηση: Η επανάληψη πραγματοποιεί επαναλαμβανόμενες κλήσεις μέχρι να επιτευχθεί η βασική λειτουργία. Έτσι υπάρχει μια μνήμη γενικά καθώς μια μνήμη για κάθε λειτουργία κλήσης ωθείται στη στοίβα.
Η επανάληψη από την άλλη πλευρά δεν έχει πολύ γενική μνήμη. Η εκτέλεση της επανάληψης είναι πιο αργή από την επαναληπτική προσέγγιση. Η αναδρομή μειώνει το μέγεθος του κώδικα ενώ η επαναληπτική προσέγγιση καθιστά τον κώδικα μεγάλο.
Q # 5) Ποια είναι τα πλεονεκτήματα της επανάληψης έναντι της επανάληψης;
Απάντηση:
- Η επανάληψη καθιστά τον κώδικα σαφέστερο και μικρότερο.
- Η αναδρομή είναι καλύτερη από την επαναληπτική προσέγγιση για προβλήματα όπως ο Πύργος του Ανόι, διασχίσεις δέντρων κ.λπ.
- Καθώς κάθε κλήση λειτουργιών έχει προωθηθεί η μνήμη στη στοίβα, το Recursion χρησιμοποιεί περισσότερη μνήμη.
- Η απόδοση της επανάληψης είναι πιο αργή από την επαναληπτική προσέγγιση.
συμπέρασμα
Το Recursion είναι μια πολύ σημαντική έννοια στο λογισμικό ανεξάρτητα από τη γλώσσα προγραμματισμού. Η αναδρομή χρησιμοποιείται κυρίως για την επίλυση προβλημάτων δομής δεδομένων όπως πύργους του Ανόι, διασχίσεις δέντρων, συνδεδεμένες λίστες κ.λπ. Αν και χρειάζεται περισσότερη μνήμη, η αναδρομή κάνει τον κώδικα απλούστερο και καθαρότερο.
Έχουμε διερευνήσει όλα σχετικά με το Recursion σε αυτό το σεμινάριο. Έχουμε επίσης εφαρμόσει πολλά παραδείγματα προγραμματισμού για καλύτερη κατανόηση της έννοιας.
=> Διαβάστε μέσω της σειράς Easy Java Training.
Συνιστώμενη ανάγνωση
- Επανάληψη σε C ++
- Java Iterator: Μάθετε να χρησιμοποιείτε Iterators στην Java με παραδείγματα
- Διασύνδεση ListIterator σε Java με παραδείγματα
- Εκπαιδευτικό πρόγραμμα JAVA για αρχάριους: 100+ πρακτικά εκπαιδευτικά βίντεο Java
- Java For Loop Tutorial με παραδείγματα προγράμματος
- Java While Loop - Εκμάθηση με παραδείγματα προγραμματισμού
- Java Do While Loop - Εκμάθηση με παραδείγματα
- Jagged Array In Java - Εκμάθηση με παραδείγματα