5.4 Η αναδρομή (recursion) στην γλώσα C

Η αναδρομή (recursion) στην γλώσσα C είναι μια τεχνική προγραμματισμού όπου μια συνάρτηση μπορεί να καλέσει τον εαυτό της για να επιλύσει ένα πρόβλημα. Αυτό σημαίνει ότι η συνάρτηση μπορεί να περιέχει έναν κώδικα που την καλεί ξανά μέσα από τον εαυτό της.

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

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

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

Ένα απλό παράδειγμα αναδρομής στην C είναι ο υπολογισμός του παραγοντικού (factorial) ενός ακέραιου αριθμού. Ο παραγοντικός ενός ακέραιου αριθμού n ορίζεται ως το γινόμενο όλων των ακεραίων αριθμών από το 1 έως το n.

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

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

Μπορούμε να υπολογίσουμε τον παραγοντικό με τη χρήση της αναδρομής ως εξής:

#include <stdio.h>

// Συνάρτηση για τον υπολογισμό του παραγοντικού
int factorial(int n) {
    if (n == 0) {
        return 1; // Το παραγοντικό του 0 είναι 1
    }
    else {
        return n * factorial(n-1); // Αναδρομική κλήση της συνάρτησης για τον υπολογισμό του παραγοντικού
    }
}

int main() {
    int n;
    printf("Please enter an integer: "); // Εκτύπωση μηνύματος προς τον χρήστη
    scanf("%d", &n); // Ανάγνωση ακέραιας τιμής από τον χρήστη
    printf("Factorial of %d is %d", n, factorial(n)); // Εκτύπωση του παραγοντικού του αριθμού που δόθηκε από τον χρήστη
    return 0;
}

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

1. Η συνάρτηση factorial υπολογίζει το παραγοντικό ενός αριθμού n. Εάν ο αριθμός n είναι μηδέν, επιστρέφει 1 (βάση της αναδρομής). Διαφορετικά, καλεί αναδρομικά την ίδια τη συνάρτηση για τον υπολογισμό του παραγοντικού του n-1 και το πολλαπλασιάζει με το n.
2. Στην main, ζητείται από τον χρήστη να εισάγει έναν ακέραιο αριθμό.
3. Ο αριθμός που δόθηκε από τον χρήστη αποθηκεύεται στη μεταβλητή n.
4. Χρησιμοποιώντας τη συνάρτηση printf, εκτυπώνεται το μήνυμα “Factorial of %d is %d”, όπου %d αντικαθίσταται από τον αριθμό που δόθηκε από τον χρήστη και το υπολογισμένο παραγοντικό αντίστοιχα.
5. Η συνάρτηση factorial καλείται με όρισμα τη μεταβλητή n και επιστρέφει το υπολογισμένο παραγοντικό.
6. Τέλος, η main συναρτησιακή μονάδα επιστρέφει 0, υποδηλώνοντας ότι ο κώδικας ολοκληρώθηκε επιτυχώς.

Στο πρόγραμμα που δώσαμε παραπάνω, αν ο χρήστης εισάγει για παράδειγμα τον αριθμό 5, το πρόγραμμα θα επιστρέψει το παραγοντικό του, που είναι 120. Έτσι, η έξοδος στην οθόνη θα είναι:

Please enter an integer: 5
Factorial of 5 is 120