# Αναδρομή

> Προβλήματα που περιέχουν τον εαυτό τους, από το τρίγωνο Sierpinski ως το παραγοντικό, και η συνθήκη τερματισμού.

Πληροφορική, Γ΄ Γυμνασίου. https://www.akademio.gr/el/gym-c/informatics/recursion

## Τι θα μάθεις

- Να αναγνωρίζεις ένα πρόβλημα που περιέχει μια μικρότερη εκδοχή του εαυτού του, όπως το τρίγωνο Sierpinski.
- Να γράφεις αναδρομική συνάρτηση Python με συνθήκη τερματισμού και αναδρομικό βήμα.
- Να ακολουθείς βήμα βήμα τις κλήσεις και τις επιστροφές μιας αναδρομικής συνάρτησης, όπως του παραγοντικού.
- Να εξηγείς τι γίνεται όταν λείπει ή είναι λάθος η συνθήκη τερματισμού.

## Ένα σχήμα που περιέχει τον εαυτό του

Πάρε ένα ισόπλευρο τρίγωνο. Ένωσε τα μέσα των τριών πλευρών του: χωρίζεται σε
τέσσερα μικρότερα τρίγωνα. Σβήσε το μεσαίο. Μένουν **τρία** τρίγωνα, το καθένα
ίδιο με το αρχικό, μόνο μικρότερο.

Και τώρα κάνε **το ίδιο** σε καθένα από τα τρία. Και ξανά, σε καθένα από τα
εννιά που προκύπτουν. Αυτό που σχηματίζεται λέγεται **τρίγωνο Sierpinski**, από
τον Πολωνό μαθηματικό Βάτσλαβ Σερπίνσκι, που το περιέγραψε το 1915.

| Επίπεδο | 0 | 1 | 2 | 3  | 4  |
| ------- | - | - | - | -- | -- |
| Τρίγωνα | 1 | 3 | 9 | 27 | 81 |

Η οδηγία για να το σχεδιάσεις χωράει σε μία πρόταση: **«για να φτιάξεις το
τρίγωνο, φτιάξε τρία μικρότερα τρίγωνα με τον ίδιο τρόπο»**. Η οδηγία
χρησιμοποιεί τον εαυτό της. Αυτό λέγεται **αναδρομή** (recursion).

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

## Μια συνάρτηση που καλεί τον εαυτό της

Στην ενότητα των συναρτήσεων είδες ότι μια συνάρτηση μπορεί να καλεί άλλες.
Μπορεί όμως να καλεί και **τον εαυτό της**:

*Διαδραστικό στη σελίδα: Η αντίστροφη μέτρηση*

Η `antistrofi(3)` τυπώνει το `3` και ζητά από την `antistrofi(2)` να κάνει τα
υπόλοιπα. Αυτή τυπώνει `2` και καλεί την `antistrofi(1)`, που τυπώνει `1` και
καλεί την `antistrofi(0)`. Εκεί το `n` είναι `0`: τυπώνεται «Εκκίνηση!» και
**δεν γίνεται καμία νέα κλήση**. Η αλυσίδα σταματά.

Κάθε αναδρομική συνάρτηση έχει δύο κομμάτια:

- τη **συνθήκη τερματισμού** (base case): την περίπτωση που είναι τόσο απλή ώστε απαντιέται κατευθείαν, χωρίς νέα κλήση. Εδώ, `n == 0`.
- το **αναδρομικό βήμα**: κάνει ένα μικρό κομμάτι της δουλειάς και καλεί τον εαυτό της για ένα **μικρότερο** πρόβλημα. Εδώ, `antistrofi(n - 1)`.

> **Πρόσεχε**
>
> **Χωρίς συνθήκη τερματισμού, η αναδρομή δεν σταματά.**
>
> ```python
> def xoris_telos(n):
>     return n * xoris_telos(n - 1)
>
> xoris_telos(5)
> ```
>
> Η `xoris_telos(5)` καλεί την `xoris_telos(4)`, αυτή την `xoris_telos(3)`, και
> συνεχίζει στο $0$, στο $-1$, στο $-2$… Κάθε κλήση που περιμένει πιάνει λίγη μνήμη,
> οπότε η Python βάζει ένα όριο, συνήθως $1000$ κλήσεις τη μία μέσα στην άλλη, και
> μετά σταματά με σφάλμα:
>
> ```text
> RecursionError: maximum recursion depth exceeded
> ```
>
> Το ίδιο γίνεται κι όταν η συνθήκη υπάρχει αλλά **δεν τη συναντάς ποτέ**: αν η
> `antistrofi` καλούσε τον εαυτό της με `n - 2`, η `antistrofi(3)` θα πήγαινε 3, 1,
> −1, −3, … και δεν θα έπεφτε ποτέ ακριβώς στο $0$.

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

Το **παραγοντικό** ενός θετικού ακέραιου $n$ γράφεται $n!$ και είναι το γινόμενο
όλων των ακεραίων από το $1$ ως το $n$:

$$
5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120
$$

Πρόσεξε όμως ότι το $4 \cdot 3 \cdot 2 \cdot 1$ είναι το $4!$. Άρα
$5! = 5 \cdot 4!$, και γενικά:

$$
n! = n \cdot (n-1)!
$$

με αφετηρία το $1! = 1$.

Ο ορισμός είναι ήδη αναδρομικός, και περνά στην Python σχεδόν λέξη προς λέξη:

```python
def paragontiko(n):
    if n == 1:
        return 1
    return n * paragontiko(n - 1)

print(paragontiko(5))
```

```text
120
```

Τι γίνεται όμως πραγματικά όταν καλείς την `paragontiko(4)`; Η κλήση **δεν
μπορεί να τελειώσει** πριν μάθει πόσο κάνει η `paragontiko(3)`, οπότε
**περιμένει**. Οι κλήσεις στοιβάζονται η μία πάνω στην άλλη, σαν πιάτα, ώσπου η
τελευταία να απαντήσει κατευθείαν. Μετά οι απαντήσεις επιστρέφουν προς τα πάνω,
η μία μετά την άλλη.

*Διαδραστικό στη σελίδα: Οι κλήσεις της paragontiko(4)*

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

## Αναδρομή ή βρόχος;

Το παραγοντικό γράφεται και με έναν βρόχο `for`, όπως έμαθες στους βρόχους:

```python
def paragontiko_vroxos(n):
    apotelesma = 1
    for i in range(1, n + 1):
        apotelesma = apotelesma * i
    return apotelesma
```

Και οι δύο δίνουν $120$ για το $5$. Ο βρόχος συχνά είναι πιο απλός για έναν
υπολογισμό σαν αυτόν. Η αναδρομή γίνεται πολύτιμη όταν το πρόβλημα **είναι από
τη φύση του** «κάτι που περιέχει μικρότερα ίδια»: το τρίγωνο Sierpinski, ένα
γενεαλογικό δέντρο, οι φάκελοι μέσα σε φακέλους του υπολογιστή σου.

Ο αριθμός των τριγώνων του Sierpinski, για παράδειγμα, γράφεται αναδρομικά με
τον τρόπο που περιγράψαμε το σχήμα:

```python
def trigona(epipedo):
    if epipedo == 0:
        return 1
    return 3 * trigona(epipedo - 1)

print(trigona(4))
```

```text
81
```

## Παραδείγματα

### Παράδειγμα 1: Γράψε αναδρομική συνάρτηση athroisma(n) που επιστρέφει το άθροισμα 1 + 2 + … + n. Τι επιστρέφει η athroisma(4);

1. **Η αναδρομική ιδέα:** το άθροισμα ως το $n$ είναι το $n$ συν το άθροισμα ως το
   $n - 1$. Για παράδειγμα $1 + 2 + 3 + 4 = 4 + (1 + 2 + 3)$.
2. **Η συνθήκη τερματισμού:** το άθροισμα ως το $1$ είναι απλώς $1$.
   ```python
   def athroisma(n):
       if n == 1:
           return 1
       return n + athroisma(n - 1)
   ```
3. **Οι κλήσεις κατεβαίνουν:** η `athroisma(4)` θέλει `4 + athroisma(3)`, που
   θέλει `3 + athroisma(2)`, που θέλει `2 + athroisma(1)`. Η `athroisma(1)`
   επιστρέφει `1`.
4. **Οι απαντήσεις ανεβαίνουν:** $2 + 1 = 3$, μετά $3 + 3 = 6$, μετά $4 + 6 = 10$.
   Η `athroisma(4)` επιστρέφει **10**.

Η επόμενη συνάρτηση μετρά πόσα ψηφία έχει ένας θετικός ακέραιος:

```python
def psifia(n):
    if n < 10:
        return 1
    return 1 + psifia(n // 10)
```

### Παράδειγμα 2: Ακολούθησε τις κλήσεις της psifia(2026). Τι επιστρέφει;

1. **Τι κάνει το `n // 10`:** είναι η ακέραια διαίρεση με το $10$, που «κόβει» το
   τελευταίο ψηφίο: `2026 // 10` δίνει `202`.
2. **Η συνθήκη τερματισμού:** ένας αριθμός μικρότερος από $10$ έχει ένα ψηφίο.
3. **Οι κλήσεις:** `psifia(2026)` → `1 + psifia(202)` → `1 + psifia(20)` →
   `1 + psifia(2)`, και η `psifia(2)` επιστρέφει `1`.
4. **Οι επιστροφές:** $1 + 1 = 2$, $1 + 2 = 3$, $1 + 3 = 4$. Η `psifia(2026)`
   επιστρέφει **4**, όσα ψηφία έχει πράγματι ο αριθμός.

> **Θυμήσου**
>
> - Αναδρομική συνάρτηση = συνάρτηση που καλεί τον εαυτό της.
> - Πρώτα γράφεις τη **συνθήκη τερματισμού**, μετά το **αναδρομικό βήμα**.
> - Κάθε κλήση πρέπει να φέρνει το πρόβλημα πιο κοντά στη συνθήκη τερματισμού.
> - Οι κλήσεις στοιβάζονται και περιμένουν· οι απαντήσεις επιστρέφουν με την **ανάποδη** σειρά.
> - Χωρίς τερματισμό: `RecursionError`.

## Ερωτήσεις

1. Τι είναι η συνθήκη τερματισμού σε μια αναδρομική συνάρτηση;
   - Η περίπτωση που απαντιέται κατευθείαν, χωρίς νέα κλήση
   - Η γραμμή όπου η συνάρτηση καλεί ξανά τον εαυτό της
   - Το σφάλμα που βγάζει η Python όταν οι κλήσεις είναι πολλές
   - Η εντολή print που τυπώνει το τελικό αποτέλεσμα στο τέλος
2. Με την antistrofi της ενότητας, τι τυπώνει η antistrofi(2);
   - 2, 1, Εκκίνηση!
   - 2, 1, 0, Εκκίνηση!
   - Εκκίνηση!, 1, 2
   - 2 και μετά σφάλμα
3. Τι επιστρέφει η paragontiko(3);
   - 6
   - 3
   - 9
   - 1
4. Μια αναδρομική συνάρτηση δεν έχει καμία συνθήκη τερματισμού. Τι θα γίνει όταν την καλέσεις;
   - Οι κλήσεις συνεχίζουν ώσπου η Python να σταματήσει με RecursionError
   - Η Python καταλαβαίνει μόνη της πού να σταματήσει και επιστρέφει 0
   - Η συνάρτηση εκτελείται μία φορά και μετά επιστρέφει None
   - Το πρόγραμμα δεν ξεκινά καν, γιατί βγαίνει συντακτικό λάθος
5. Αν η antistrofi καλούσε τον εαυτό της με n - 2 αντί για n - 1, τι θα γινόταν με την antistrofi(5);
   - Θα πήγαινε 5, 3, 1, −1… χωρίς να φτάσει ποτέ στο 0
   - Θα τύπωνε 5, 3, 1 και μετά «Εκκίνηση!» κανονικά
   - Θα τύπωνε 5, 4, 3, 2, 1 όπως και πριν, αλλά πιο γρήγορα
   - Θα σταματούσε αμέσως, γιατί το 5 δεν διαιρείται με το 2
6. Όταν καλείς την paragontiko(4), ποια κλήση επιστρέφει πρώτη την απάντησή της;
   - Η paragontiko(1)
   - Η paragontiko(4)
   - Η paragontiko(2)
   - Όλες ταυτόχρονα
7. Πόσα τρίγωνα έχει το τρίγωνο Sierpinski στο 3ο επίπεδο, αν το αρχικό τρίγωνο είναι το επίπεδο 0;
   - 27
   - 9
   - 12
   - 64
8. Τι τυπώνει η f(3), αν η f είναι: def f(n): if n == 0: return · αλλιώς f(n - 1) και μετά print(n);
   - 1, 2, 3
   - 3, 2, 1
   - 0, 1, 2, 3
   - Μόνο 3

## Ασκήσεις

1. Τι επιστρέφει η paragontiko(6) της ενότητας;
2. Η dynami(a, n) υπολογίζει το a στη δύναμη n με το αναδρομικό βήμα return a * dynami(a, n - 1). Ποια συνθήκη τερματισμού χρειάζεται, και τι επιστρέφει;
3. def m(n): if n == 0: return 0 · αλλιώς return n % 10 + m(n // 10)
   α) Τι επιστρέφει η m(2026);
   β) Τι υπολογίζει γενικά η m;
4. Πάρε τη συνάρτηση trigona(epipedo) της ενότητας.
   α) Τι επιστρέφει η trigona(5);
   β) Πόσες κλήσεις της trigona γίνονται συνολικά για την trigona(5);
   γ) Αν το αναδρομικό βήμα ήταν 3 * trigona(epipedo + 1), τι θα γινόταν;

---

Οι απαντήσεις, τα διαδραστικά και τα παιχνίδια είναι στη σελίδα της ενότητας: https://www.akademio.gr/el/gym-c/informatics/recursion
