📋 Τι περιλαμβάνει αυτή η σελίδα:

Αρμονική Σειρά (sumSeries) — Μαθηματικός ορισμός, κώδικας C, φάσεις κάθοδου/ανόδου, animated στοίβα κλήσεων για sumSeries(4)
Αλγόριθμος Ευκλείδη (ΜΚΔ/GCD) — Αναδρομικός ορισμός, κώδικας C, πίνακας mod, animated στοίβα κλήσεων για gcd(48, 18)

Η Αρμονική Σειρά αναδρομικά

Η αρμονική σειρά είναι ένα κλασικό παράδειγμα αναδρομής: υπολογίζουμε το άθροισμα S(n) = 1/1 + 1/2 + 1/3 + ... + 1/n. Ο αναδρομικός ορισμός λέει ότι το άθροισμα μέχρι το n ισούται με 1/n συν το άθροισμα μέχρι το n-1. Βασική περίπτωση: όταν n == 1, το αποτέλεσμα είναι 1.0.

S(1) = 1.0 ← βασική περίπτωση S(n) = 1/n + S(n-1) ← αναδρομική περίπτωση Π.χ.: S(4) = 1/4 + 1/3 + 1/2 + 1 = 2.0833

📌 Γιατί double και όχι int; Επειδή τα 1/n δίνουν δεκαδικά αποτελέσματα (π.χ. 1/3 = 0.333…). Αν χρησιμοποιούσαμε int, θα είχαμε ακέραια διαίρεση (1/2 = 0, 1/3 = 0…) και θα χάναμε όλη την ακρίβεια! Γι' αυτό γράφουμε 1.0 / n (double διαίρεση).

Κώδικας σε C

#include <stdio.h>

/* Αναδρομική συνάρτηση για υπολογισμό του αθροίσματος */
double sumSeries(int n) {
    /* Βασική περίπτωση */
    if (n == 1) {
        return 1.0;
    } else {
        /* Αναδρομικός τύπος:
           S(n) = 1/n + S(n-1) */
        return (1.0 / n) + sumSeries(n - 1);
    }
}

int main() {
    printf("S(1)  = %.4f\n", sumSeries(1));
    printf("S(4)  = %.4f\n", sumSeries(4));
    printf("S(10) = %.4f\n", sumSeries(10));
    return 0;
}

S(1) = 1.0000 S(4) = 2.0833 S(10) = 2.9290

Βήμα-Βήμα: Φάσεις Κάθοδου & Ανόδου

Η εκτέλεση της sumSeries(4) ακολουθεί το γνωστό μοτίβο δύο φάσεων:

📉 ΚΑΘΟΔΟΣ (Κλήσεις)

sumSeries(4) → χρειάζεται sumSeries(3)

sumSeries(3) → χρειάζεται sumSeries(2)

sumSeries(2) → χρειάζεται sumSeries(1)

sumSeries(1) → ΒΑΣΗ! Επιστρέφει 1.0

📈 ΑΝΟΔΟΣ (Επιστροφές)

sumSeries(1) = 1.0

sumSeries(2) = 1/2 + 1.0 = 1.5

sumSeries(3) = 1/3 + 1.5 = 1.8333

sumSeries(4) = 1/4 + 1.8333 = 2.0833

Animated Βήμα-Βήμα: sumSeries(4)

Χρησιμοποιήστε τα κουμπιά για να δείτε ακριβώς πώς χτίζεται και αποχτίζεται η στοίβα κλήσεων:

🔍 Εκτέλεση του sumSeries(4)

Η στοίβα κλήσεων (call stack) — κάθε πλαίσιο κρατά την τιμή n

Βήμα 0 / 7

Πατήστε ▶ Επόμενο για να ξεκινήσετε, ή ⚡ Αυτόματο για αυτόματη αναπαραγωγή.

● ○ ○ ○ ○ ○ ○ ○

Τι Αποθηκεύεται στη Στοίβα;

Κάθε κλήση της sumSeries δημιουργεί ένα νέο πλαίσιο στοίβας (stack frame):

📦 Τι αποθηκεύεται σε κάθε πλαίσιο;

Η τιμή της παραμέτρου n (π.χ. n=4, n=3, …)
Η διεύθυνση επιστροφής — πού θα συνεχίσει ο κώδικας όταν τελειώσει
Το ενδιάμεσο αποτέλεσμα 1.0/n περιμένει τη συνέχεια

▲ ΚΟΡΥΦΗ ΣΤΟΙΒΑΣ (το πιο πρόσφατο frame)

🛑 sumSeries(1) → return 1.0 ← ΒΑΣΙΚΗ ΠΕΡΙΠΤΩΣΗ

↓ επιστρέφει 1.0 στο...

⏳ sumSeries(2) → return 1/2 + ? ← περιμένει sumSeries(1)

↓ θα επιστρέψει 1.5 στο...

⏳ sumSeries(3) → return 1/3 + ? ← περιμένει sumSeries(2)

↓ θα επιστρέψει 1.8333 στο...

⏳ sumSeries(4) → return 1/4 + ? ← περιμένει sumSeries(3)

▼ ΒΑΣΗ ΣΤΟΙΒΑΣ (η πρώτη κλήση από την main)

✅ Σημαντική παρατήρηση: Αντίθετα με το factorial που πολλαπλασιάζει, η sumSeries προσθέτει δεκαδικά κλάσματα. Γι' αυτό χρησιμοποιούμε τύπο double (και γράφουμε 1.0 / n αντί 1 / n).

Αλγόριθμος Ευκλείδη — Μέγιστος Κοινός Διαιρέτης (ΜΚΔ)

Ο Μέγιστος Κοινός Διαιρέτης (ΜΚΔ) δύο αριθμών α και β μπορεί να υπολογιστεί αναδρομικά με τον αλγόριθμο του Ευκλείδη — έναν αλγόριθμο ηλικίας 2.300+ ετών που είναι ίσως ο αρχαιότερος αλγόριθμος στην ιστορία!

ΜΚΔ(α, β) = α ← αν β == 0 (βασική περίπτωση) ΜΚΔ(α, β) = ΜΚΔ(β, α mod β) ← αν β ≠ 0 (αναδρομική) Π.χ.: ΜΚΔ(48, 18) → ΜΚΔ(18, 12) → ΜΚΔ(12, 6) → ΜΚΔ(6, 0) = 6

📌 Γιατί δουλεύει; Ο μέγιστος κοινός διαιρέτης δύο αριθμών δεν αλλάζει αν αντικαταστήσουμε τον μεγαλύτερο αριθμό με το υπόλοιπο της διαίρεσής του με τον μικρότερο. Δηλαδή ΜΚΔ(α, β) = ΜΚΔ(β, α mod β). Τελικά, το β θα γίνει 0, και τότε ο ΜΚΔ είναι ο α.

Τι σημαίνει `α mod β`;

Ο τελεστής % (modulo) επιστρέφει το υπόλοιπο της ακέραιας διαίρεσης:

Πράξη	Πηλίκο	Υπόλοιπο (mod)
48 ÷ 18	2	48 % 18 = 12
18 ÷ 12	1	18 % 12 = 6
12 ÷ 6	2	12 % 6 = 0

ΜΚΔ — Κώδικας σε C

#include <stdio.h>

/* Αλγόριθμος Ευκλείδη — αναδρομική υλοποίηση
   ΜΚΔ(α, β) = α              αν β == 0
   ΜΚΔ(α, β) = ΜΚΔ(β, α%β)   αν β ≠ 0  */
int gcd(int a, int b) {
    if (b == 0) {
        return a;              /* βασική περίπτωση */
    }
    return gcd(b, a % b);   /* αναδρομική κλήση */
}

int main() {
    printf("ΜΚΔ(48, 18) = %d\n", gcd(48, 18));
    printf("ΜΚΔ(56, 98) = %d\n", gcd(56, 98));
    printf("ΜΚΔ(12, 0)  = %d\n", gcd(12, 0));
    printf("ΜΚΔ(17, 5)  = %d\n", gcd(17, 5));
    return 0;
}

ΜΚΔ(48, 18) = 6 ΜΚΔ(56, 98) = 14 ΜΚΔ(12, 0) = 12 ΜΚΔ(17, 5) = 1

⚠️ Σημαντική διαφορά από factorial/fibonacci: Εδώ η αναδρομή δεν μειώνει απλά μια μεταβλητή κατά 1 — αλλάζει και τις δύο παραμέτρους ταυτόχρονα! Το a γίνεται b και το b γίνεται a%b. Η σύγκλιση στη βάση (b == 0) εξασφαλίζεται γιατί το υπόλοιπο πάντα μικραίνει.

ΜΚΔ — Φάσεις Κάθοδου & Ανόδου

Η εκτέλεση της gcd(48, 18) ακολουθεί δύο φάσεις — αλλά εδώ η «άνοδος» είναι πιο απλή, γιατί δεν γίνεται πράξη μετά την αναδρομική κλήση. Η τιμή απλά «περνά» πίσω:

📉 ΚΑΘΟΔΟΣ (Κλήσεις)

gcd(48, 18) → 48%18=12 → καλεί gcd(18, 12)

gcd(18, 12) → 18%12=6 → καλεί gcd(12, 6)

gcd(12, 6) → 12%6=0 → καλεί gcd(6, 0)

gcd(6, 0) → b==0, ΒΑΣΗ! Επιστρέφει 6

📈 ΑΝΟΔΟΣ (Επιστροφές)

gcd(6, 0) = 6 ← βασική

gcd(12, 6) = 6 ← περνά πίσω

gcd(18, 12) = 6 ← περνά πίσω

gcd(48, 18) = 6 ← τελικό!

✅ Tail Recursion (Ουρά Αναδρομή): Παρατηρήστε ότι η αναδρομική κλήση return gcd(b, a%b) είναι η τελευταία πράξη — δεν γίνεται πρόσθεση ή πολλαπλασιασμός μετά. Αυτό λέγεται tail recursion και θεωρητικά μπορεί να βελτιστοποιηθεί από τον compiler!

Animated Βήμα-Βήμα: gcd(48, 18)

Χρησιμοποιήστε τα κουμπιά για να δείτε ακριβώς πώς χτίζεται και αποχτίζεται η στοίβα κλήσεων:

🔍 Εκτέλεση του gcd(48, 18)

Η στοίβα κλήσεων (call stack) — κάθε πλαίσιο κρατά τις τιμές a και b

Βήμα 0 / 7

Πατήστε ▶ Επόμενο για να ξεκινήσετε, ή ⚡ Αυτόματο για αυτόματη αναπαραγωγή.

● ○ ○ ○ ○ ○ ○ ○

ΜΚΔ — Τι Αποθηκεύεται στη Στοίβα;

Κάθε κλήση της gcd δημιουργεί ένα νέο πλαίσιο στοίβας με τις τρέχουσες τιμές a και b:

▲ ΚΟΡΥΦΗ ΣΤΟΙΒΑΣ (το πιο πρόσφατο frame)

🛑 gcd(6, 0) → b==0, return 6 ← ΒΑΣΙΚΗ ΠΕΡΙΠΤΩΣΗ

↓ επιστρέφει 6 στο...

⏳ gcd(12, 6) → return gcd(6, 12%6) ← 12%6=0

↓ επιστρέφει 6 στο...

⏳ gcd(18, 12) → return gcd(12, 18%12) ← 18%12=6

↓ επιστρέφει 6 στο...

⏳ gcd(48, 18) → return gcd(18, 48%18) ← 48%18=12

▼ ΒΑΣΗ ΣΤΟΙΒΑΣ (η πρώτη κλήση από την main)

Η Αρμονική Σειρά αναδρομικά

Κώδικας σε C

Βήμα-Βήμα: Φάσεις Κάθοδου & Ανόδου

📉 ΚΑΘΟΔΟΣ (Κλήσεις)

📈 ΑΝΟΔΟΣ (Επιστροφές)

Animated Βήμα-Βήμα: sumSeries(4)

Τι Αποθηκεύεται στη Στοίβα;

Αλγόριθμος Ευκλείδη — Μέγιστος Κοινός Διαιρέτης (ΜΚΔ)

Τι σημαίνει α mod β;

ΜΚΔ — Κώδικας σε C

ΜΚΔ — Φάσεις Κάθοδου & Ανόδου

📉 ΚΑΘΟΔΟΣ (Κλήσεις)

📈 ΑΝΟΔΟΣ (Επιστροφές)

Animated Βήμα-Βήμα: gcd(48, 18)

ΜΚΔ — Τι Αποθηκεύεται στη Στοίβα;

Τι σημαίνει `α mod β`;