Αναδρομή

Αναδρομικοί ορισμοί

Το παραγοντικό

Το παραγοντικό ενός φυσικού $n$ είναι το γινόμενο των φυσικών από το 1 έως το $n$: $n! = 1 \cdot 2 \cdots n$, με τη σύμβαση $0! = 1$. Οι τελείες αυτού του τύπου κρύβουν έναν βρόχο, και το μάθημα Βρόχοι δίδαξε πώς γράφεται. Ωστόσο, ο ίδιος ορισμός δέχεται και μια άλλη μορφή, που δεν αναφέρει κανέναν βρόχο: το παραγοντικό του $n$ είναι $n$ φορές το παραγοντικό του $n - 1$, και το παραγοντικό του 0 είναι 1.

Αυτός είναι ένας αναδρομικός ορισμός: ορίζει το παραγοντικό του $n$ μέσω του παραγοντικού ενός μικρότερου αριθμού. Δεν είναι κυκλικός, γιατί κάθε εφαρμογή του δεύτερου κανόνα κατεβαίνει ένα σκαλί και η σκάλα τελειώνει στον πρώτο: $3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 \cdot 0! = 6$. Οι δύο κανόνες έχουν όνομα. Ο πρώτος είναι η βασική περίπτωση, που δίνει το αποτέλεσμα χωρίς να αναφέρεται σε τίποτε άλλο· ο δεύτερος είναι η αναδρομική περίπτωση, που ανάγει το πρόβλημα σε ένα μικρότερο στιγμιότυπο του ίδιου προβλήματος.

Η C++ επιτρέπει σε μια συνάρτηση να καλεί τον εαυτό της, και έτσι ο ορισμός μεταφέρεται σχεδόν λέξη προς λέξη.

#include <print>​// Παραγοντικό του n.// Προσυνθήκη: 0 <= n <= 12 (το φράγμα αιτιολογείται παρακάτω).// Μετασυνθήκη: επιστρέφει n! = 1 · 2 · ... · n, με 0! = 1.int factorial(int n){    if (n == 0) {        return 1;                   // βασική περίπτωση    }    return n * factorial(n - 1);    // αναδρομική περίπτωση}​int main(){    for (int n{0}; n <= 6; ++n) {        std::println("{}! = {}", n, factorial(n));    }}

0! = 11! = 12! = 23! = 64! = 245! = 1206! = 720

Η σύμβαση δεν είναι διακοσμητική: με $n = -1$ η αναδρομική περίπτωση θα καλούσε με $-2$, έπειτα με $-3$, και δεν θα έφτανε ποτέ στο 0· και το $13!$ δεν χωρά σε έναν int. Πολλά εισαγωγικά κείμενα γράφουν αυτό το παραγοντικό με τη βασική περίπτωση if (n == 0 || n == 1), περιττή αλλά αβλαβή, και χωρίς να λένε τίποτα για τους αρνητικούς ούτε για το μέγεθος του αποτελέσματος: ο κώδικάς τους δεν τερματίζει με $n < 0$ και δίνει ένα αποτέλεσμα χωρίς νόημα από το $13!$ και πέρα. Και τα δύο ελαττώματα θα εξεταστούν στην παράγραφό τους.

Βασική περίπτωση και αναδρομική περίπτωση

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

Η δύναμη $x^n$, με $n$ φυσικό, ορίζεται από τις $x^0 = 1$ και $x^n = x \cdot x^{n - 1}$: το μέγεθος είναι ο εκθέτης. Το άθροισμα των ψηφίων ενός φυσικού $n$ (του 2026 είναι $2 + 0 + 2 + 6 = 10$) ορίζεται ως εξής: αν $n < 10$, το άθροισμα είναι $n$, γιατί έχει ένα μόνο ψηφίο· αλλιώς, είναι το άθροισμα των ψηφίων του $\lfloor n / 10 \rfloor$, που είναι ο $n$ χωρίς το τελευταίο του ψηφίο, συν αυτό το τελευταίο ψηφίο, $n \bmod 10$. Εδώ το μέγεθος είναι το πλήθος των ψηφίων.

#include <print>​// x υψωμένο στη n.// Προσυνθήκη: n >= 0.// Μετασυνθήκη: επιστρέφει x^n, με x^0 = 1.double power(double x, int n){    if (n == 0) {        return 1.0;    }    return x * power(x, n - 1);}​// Άθροισμα των δεκαδικών ψηφίων του n.// Προσυνθήκη: n >= 0.// Μετασυνθήκη: επιστρέφει το άθροισμα των ψηφίων του n.int digitSum(int n){    if (n < 10) {        return n;    }    return digitSum(n / 10) + n % 10;}​int main(){    std::println("2^10 = {}", power(2.0, 10));    std::println("1.5^3 = {}", power(1.5, 3));    std::println("άθροισμα των ψηφίων του 2026: {}", digitSum(2026));}

2^10 = 10241.5^3 = 3.375άθροισμα των ψηφίων του 2026: 10

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