Η αναδρομή στη γλώσσα C-Sharp

Η αναδρομή στη γλώσσα C-Sharp

Η αναδρομή στη γλώσσα C-Sharp, όπως και σε κάθε άλλη γλώσσα προγραμματισμού, αποτελεί μία ιδιαίτερη τεχνική προγραμματισμού κατά την οποία μία συνάρτηση καλεί τον εαυτό της.

Αναδρομή ονομάζεται η διαδικασία επανάληψης αντικειμένων με τρόπο που αντιγράφουν τον εαυτό τους. Για παράδειγμα, όταν οι επιφάνειες δύο καθρεπτών βρίσκονται αντικρυστά και παράλληλες μεταξύ τους, τα εμφωλευμένα είδωλα που προκύπτουν αποτελούν μία μορφή ατέρμονης αναδρομής.  Ο όρος χρησιμοποιείται σε διάφορους τομείς, αλλά κατέχει εξέχουσα θέση στα μαθηματικά και κατ’ επέκταση στην επιστήμη της Πληροφορικής.  Ειδικότερα αναφέρεται σε ένα πολυάριθμο αλλά πεπερασμένο πλήθος από αντικείμενα υπολογιζόμενα από μία έκφραση πεπερασμένων επαναλήψεων. Ο υπολογισμός των αντικειμένων βασίζεται στο αποτέλεσμα υπολογισμού άλλων αντικειμένων της ακολουθίας, βάσει της συγκεκριμένης έκφρασης.

Η αναδρομή στη γλώσσα C-Sharp: υπολογισμός του παραγοντικού ενός ακέραιου αριθμού

Σύνηθες παράδειγμα είναι ο υπολογισμός του παραγοντικού ενός ακέραιου αριθμού. Το παραγοντικό του 0 θεωρείται αυθαίρετα ίσο με 1. Για κάθε άλλο ακέραιο αριθμό n μεγαλύτερο του 0, το παραγοντικό υπολογίζεται μέσω των παραγοντικών όλων των ακεραίων στο διάστημα 1 έως n. Η ακόλουθη έκφραση περιγράφει με λόγια τη συνάρτηση υπολογισμού του παραγοντικού ενός αριθμού:

“Εάν ο αριθμός είναι μικρότερος του μηδενός, απορρίπτεται. Εάν δεν είναι ακέραιος, απορρίπτεται. Εάν ο αριθμός ισούται με το μηδέν, το παραγοντικό του είναι ίσο με τη μονάδα. Εάν είναι μεγαλύτερος του μηδενός, το παραγοντικό του ισούται με το γινόμενο του αριθμού επί το παραγοντικό του αμέσως μικρότερου ακέραιου αριθμού.”

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

Η αναδρομή στη γλώσσα C-Sharp: πρόγραμμα υπολογισμού του παραγοντικού ενός ακέραιου αριθμού

Παρατίθεται ο κώδικας σε C-Sharp για τον υπολογισμό του παραγοντικού του αριθμού 5 με χρήση της αναδρομής στη γλώσσα C-Sharp:

class Program
{
    static void Main(string[] args)
    {
      Console.WriteLine("{0}", Factorial(5));
      Console.ReadKey();
    }
    static Int32 Factorial(int x)
    {
      if (x < 0) return 0;
      if ((x == 0) || (x == 1)) return 1;
      return (x * Factorial(x - 1));
    }
}
  • Στο κυρίως πρόγραμμα ( συνάρτηση Main( ) ), παρατηρούμε ότι η κλήση της συνάρτησης υπολογισμού του παραγοντικού ( Factorial( ) )γίνεται μία και μόνο φορά. Η επανάκληση εκτελείται από την ίδια τη συνάρτηση του παραγοντικού.

Μέσα στη συνάρτηση του παραγοντικού πλέον:

  • Ελέγχεται εν πρώτοις εάν ο αριθμός δεν είναι θετικός, οπότε στο κυρίως πρόγραμμα επιστρέφεται η τιμή μηδέν.
  • Ελέγχεται εάν ο αριθμός ισούται με το μηδέν ή τη μονάδα, οπότε στο κυρίως πρόγραμμα επιστρέφεται η τιμή της μονάδας.
  • Σε κάθε άλλη περίπτωση, πραγματοποιείται επανάκληση της ίδιας της συνάρτησης για κάθε μικρότερο ακέραιο αριθμό, πολύ πριν τον υπολογισμό του αρχικού ορίσματος. Η επιστρεφόμενη τιμή στο κυρίως πρόγραμμα θα έχει προέλθει από τον υπολογισμό των παραγοντικών των αριθμών 0, 1, 2, 3, 4, 5. Παρατηρούμε ότι η αναδρομή τερματίζεται όταν πλέον το χ έχει εξισωθεί με το μηδέν. Για χ<0 , στο πρόγραμμα επιστρέφεται το μηδέν.

Το αποτέλεσμα που προκύπτει στην οθόνη είναι το εξής:

120

Η αναδρομή στη γλώσσα C-Sharp: ανάγκη για ορθή σύνταξη

Εν γένει οι έννοιες της αναδρομής και της επανάληψης (looping) σχετίζονται μεταξύ τους με τρόπο που κάποιες φορές είναι δύσκολο να επιλεγεί κάποια εξ αυτών μέσα σε ένα πρόγραμμα. Συνήθως η ανάγκη για συγκεκριμένο τρόπο υπολογισμού οδηγεί στην επιλογή της πιο κατάλληλης τεχνικής. Η προσέγγιση έγκειται στην πιο αβίαστα επιλεγόμενη τεχνική.

Παρά την ευχρηστία και τη σημαντικότητα της τεχνικής της αναδρομής, είναι εύκολο να συνταχθεί ανάλογη συνάρτηση που δεν μπορεί να φθάσει σε υπολογιστικό τέλος. Λάθη ή παραλείψεις στον κώδικα μπορούν να οδηγήσουν το υπολογιστικό σύστημα σε ατέρμονους υπολογισμούς (infinite loop). Ως απόρροια τέτοιας περίπτωσης, η συνάρτηση δύναται να αξιοποιήσει όλους τους πόρους του συστήματος (πχ μνήμη). Το κάθε νέο επίπεδο (βάθους) αναδρομής δεσμεύει τους δικούς του πόρους. Με τη δέσμευση και μη απελευθέρωσή τους από τα πολυάριθμα επίπεδα, το σύστημα έρχεται πλέον σε κατάσταση exception, καθώς ο υπολογισμός δεν έχει φθάσει εις πέρας, ενώ ταυτόχρονα οι πόροι δεν επαρκούν για τη συνέχιση της διαδικασίας.

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

Απάντηση

Αυτός ο ιστότοπος χρησιμοποιεί το Akismet για να μειώσει τα ανεπιθύμητα σχόλια. Μάθετε πώς υφίστανται επεξεργασία τα δεδομένα των σχολίων σας.