# Αναδρομή

> Συναρτήσεις που καλούν τον εαυτό τους, και πώς ξέρουν πότε να σταματήσουν.

Πληροφορική, Β΄ Λυκείου. https://www.akademio.gr/el/lyk-b/informatics/recursion

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

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

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

**Αναδρομή** (recursion) είναι όταν μια συνάρτηση, για να λύσει ένα πρόβλημα, καλεί **τον εαυτό της** πάνω σε ένα **μικρότερο** κομμάτι του ίδιου προβλήματος.

Το παραγοντικό είναι το κλασικό παράδειγμα. Αφού $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$ και $4! = 4 \cdot 3 \cdot 2 \cdot 1$, ισχύει $5! = 5 \cdot 4!$. Γενικά:

$$
n! = \begin{cases} 1, & n = 0 \\ n \cdot (n-1)!, & n > 0 \end{cases}
$$

Ο ορισμός μεταφέρεται σχεδόν αυτούσιος σε Python:

*Διαδραστικό στη σελίδα: Οι κλήσεις του factorial(5)*

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

| Μέρος                        | Ρόλος                                               | Στο παραγοντικό         |
| ---------------------------- | --------------------------------------------------- | ----------------------- |
| Βασική περίπτωση (base case) | απαντά **χωρίς** αναδρομή, και σταματά την αλυσίδα  | `n == 0` επιστρέφει `1` |
| Αναδρομική κλήση             | λύνει το πρόβλημα με τη βοήθεια ενός **μικρότερου** | `n * factorial(n - 1)`  |

> **Κλειδί**
>
> **Για να γράψεις αναδρομή, εμπιστέψου ότι η μικρότερη κλήση δουλεύει.**
>
> Μην προσπαθείς να παρακολουθήσεις νοερά όλες τις κλήσεις. Ρώτα δύο πράγματα μόνο: υπάρχει βασική περίπτωση που απαντά σωστά; Και αν το `factorial(n - 1)` δίνει σωστό αποτέλεσμα, δίνει και το `factorial(n)`; Αν ναι, και κάθε κλήση πλησιάζει τη βασική περίπτωση, η συνάρτηση είναι σωστή. Είναι η ίδια λογική με τη μαθηματική επαγωγή.

## Η στοίβα κλήσεων

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

*Διαδραστικό στη σελίδα: Η στοίβα του factorial(4)*

## Όταν λείπει η βάση

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

```python
def forever(n):
    return forever(n - 1)  # καμία βασική περίπτωση

try:
    forever(5)
except RecursionError as error:
    print("RecursionError:", error)
```

Το πρόγραμμα τυπώνει `RecursionError: maximum recursion depth exceeded`.

> **Πρόσεχε**
>
> **Η βασική περίπτωση πρέπει και να υπάρχει και να φτάνεται.**
>
> Το `factorial(-1)` καλεί το `factorial(-2)`, αυτό το `factorial(-3)`, και ποτέ δεν συναντά το `n == 0`. Η βάση υπάρχει, αλλά οι κλήσεις απομακρύνονται από αυτήν αντί να την πλησιάζουν. Ένας πιο ανθεκτικός έλεγχος είναι `if n <= 0`, ή ένα ρητό μήνυμα λάθους για αρνητική είσοδο.

## Αναδρομή ή επανάληψη;

Κάθε αναδρομή γράφεται και με επανάληψη, και το ανάποδο:

```python
def factorial_loop(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

print(factorial_loop(5))  # 120
```

Για το παραγοντικό, η επανάληψη είναι απλούστερη και δεν γεμίζει τη στοίβα. Η αναδρομή κερδίζει όταν το πρόβλημα είναι **από τη φύση του αναδρομικό**: φάκελοι που περιέχουν φακέλους, δέντρα, ή αλγόριθμοι «διαίρει και βασίλευε» (divide and conquer) που σπάνε το πρόβλημα στα δύο, όπως η δυαδική αναζήτηση και η ταξινόμηση με συγχώνευση.

Οι **πύργοι του Ανόι** είναι το κλασικό παράδειγμα. Για να μεταφέρεις $n$ δίσκους από τον στύλο Α στον Γ, με τον Β βοηθητικό, χωρίς ποτέ μεγάλος δίσκος πάνω σε μικρό: μετάφερε τους $n - 1$ πάνω δίσκους στον Β, μετακίνησε τον μεγαλύτερο στον Γ, και ξαναβάλε τους $n - 1$ από τον Β πάνω του στον Γ.

*Διαδραστικό στη σελίδα: Οι πύργοι του Ανόι με 3 δίσκους*

Με επανάληψη το ίδιο πρόγραμμα γράφεται πολύ δυσκολότερα.

## Όταν η αναδρομή κοστίζει

Η ακολουθία Fibonacci ορίζεται αναδρομικά: $F_0 = 0$, $F_1 = 1$ και $F_n = F_{n-1} + F_{n-2}$. Η ευθεία μεταφορά σε κώδικα είναι σωστή αλλά πολύ αργή:

```python
calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

for n in [10, 20, 30]:
    calls = 0
    print(n, fib(n), calls)
```

| $n$  | $F_n$      | Κλήσεις       |
| ---- | ---------- | ------------- |
| $10$ | $55$       | $177$         |
| $20$ | $6765$     | $21\,891$     |
| $30$ | $832\,040$ | $2\,692\,537$ |

Ο λόγος: το `fib(30)` καλεί το `fib(29)` και το `fib(28)`, αλλά και το `fib(29)` καλεί ξανά το `fib(28)`. Τα ίδια υποπροβλήματα λύνονται ξανά και ξανά, και οι κλήσεις μεγαλώνουν **εκθετικά**.

Η διόρθωση λέγεται **απομνημόνευση** (memoization): κάθε αποτέλεσμα αποθηκεύεται την πρώτη φορά που υπολογίζεται, και απλώς διαβάζεται τις επόμενες.

```python
memo = {}

def fib_memo(n):
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

print(fib_memo(100))  # 354224848179261915075, αμέσως
```

Κάθε $F_k$ υπολογίζεται πλέον **μία** φορά, άρα ο χρόνος γίνεται γραμμικός.

> **Θυμήσου**
>
> - Βασική περίπτωση **και** πρόοδος προς αυτήν σε κάθε κλήση.
> - Κάθε ενεργή κλήση πιάνει θέση στη στοίβα· η Python επιτρέπει περίπου $1000$.
> - Αν οι αναδρομικές κλήσεις ξαναλύνουν τα ίδια υποπροβλήματα, απομνημόνευσε τα αποτελέσματα.

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

### Παράδειγμα 1: Γράψε αναδρομική συνάρτηση που υπολογίζει το άθροισμα των ψηφίων ενός φυσικού αριθμού, και βρες τι επιστρέφει για το \$472\$.

1. **Βασική περίπτωση:** ένας μονοψήφιος αριθμός έχει άθροισμα ψηφίων τον εαυτό του. Άρα αν `n < 10`, επιστρέφουμε `n`.
2. **Αναδρομική κλήση:** το τελευταίο ψηφίο είναι `n % 10` και ο υπόλοιπος αριθμός είναι `n // 10`. Άρα `digit_sum(n) = n % 10 + digit_sum(n // 10)`.
3. **Σε Python:**
   ```python
   def digit_sum(n):
       if n < 10:
           return n
       return n % 10 + digit_sum(n // 10)

   print(digit_sum(472))
   ```
4. **Υπολογισμός:** το `digit_sum(472)` δίνει $2$ συν `digit_sum(47)`, που δίνει $7$ συν `digit_sum(4)`, που είναι η βασική περίπτωση και δίνει $4$. Σύνολο $2 + 7 + 4 = 13$.

### Παράδειγμα 2: Πόσες κινήσεις χρειάζονται οι πύργοι του Ανόι για \$n\$ δίσκους; Πόσες για \$3\$ και πόσες για \$64\$;

1. **Αναδρομική σχέση:** αν $M_n$ είναι οι κινήσεις για $n$ δίσκους, τότε $M_n = M_{n-1} + 1 + M_{n-1} = 2M_{n-1} + 1$, με $M_0 = 0$.
2. **Πρώτοι όροι:** $M_1 = 1$, $M_2 = 3$, $M_3 = 7$, $M_4 = 15$. Κάθε φορά ένα λιγότερο από δύναμη του $2$: $M_n = 2^n - 1$.
3. **Για $3$ δίσκους:** $2^3 - 1 = 7$ κινήσεις, όσες τυπώνει το πρόγραμμα.
4. **Για $64$ δίσκους:** $2^{64} - 1 \approx 1{,}8 \cdot 10^{19}$ κινήσεις. Με μία κίνηση το δευτερόλεπτο, πάνω από $500$ δισεκατομμύρια χρόνια. Ο αλγόριθμος είναι σωστός και $O(2^n)$.

### Παράδειγμα 3: Η συνάρτηση total(items) επιστρέφει items\[0] + total(items\[1:]). Τι λάθος έχει και πώς διορθώνεται;

1. **Η αναδρομική κλήση είναι σωστή:** το πρώτο στοιχείο συν το άθροισμα των υπολοίπων, και η λίστα μικραίνει κατά ένα σε κάθε κλήση.
2. **Λείπει η βασική περίπτωση.** Όταν η λίστα αδειάσει, το `items[0]` προκαλεί `IndexError`.
3. **Διόρθωση:** πρόσθεσε στην αρχή `if not items: return 0`. Το άθροισμα της κενής λίστας είναι $0$.
4. **Και ένα όριο που μένει:** για λίστα $5000$ στοιχείων η συνάρτηση θα ξεπεράσει το όριο της στοίβας. Εκεί η απλή επανάληψη, ή το `sum(items)`, είναι η σωστή επιλογή.

## Ερωτήσεις

1. Ποια δύο μέρη χρειάζεται κάθε σωστή αναδρομική συνάρτηση;
   - βασική περίπτωση και αναδρομική κλήση σε μικρότερο πρόβλημα
   - μια επανάληψη και μια συνθήκη
   - δύο αναδρομικές κλήσεις
   - μια καθολική μεταβλητή που μετρά τις κλήσεις και μια παράμετρο
2. Τι γίνεται στην Python αν μια αναδρομική συνάρτηση δεν έχει βασική περίπτωση;
   - σταματά με RecursionError κοντά στα $1000$ επίπεδα στοίβας
   - τρέχει για πάντα, όπως ένας βρόχος while True χωρίς break
   - επιστρέφει $0$
   - δεν εκτελείται καθόλου, λόγω συντακτικού λάθους
3. Η factorial έχει βασική περίπτωση `n == 0`. Τι γίνεται με την κλήση factorial(-2);
   - οι κλήσεις απομακρύνονται από το $0$ και καταλήγουν σε RecursionError
   - επιστρέφει $1$
   - επιστρέφει $2$
   - η Python απορρίπτει αμέσως την κλήση, επειδή το όρισμα είναι αρνητικό
4. Πόσες κλήσεις της factorial βρίσκονται ταυτόχρονα στη στοίβα, στο βαθύτερο σημείο του factorial(4);
   - $5$
   - $4$
   - $1$
   - $24$
5. Ποια κλήση του factorial(4) τελειώνει πρώτη;
   - η factorial(0)
   - η factorial(4)
   - η factorial(1)
   - τελειώνουν όλες μαζί
6. Γιατί η απλή αναδρομική fib(30) κάνει πάνω από δύο εκατομμύρια κλήσεις;
   - γιατί υπολογίζει τα ίδια υποπροβλήματα ξανά και ξανά
   - γιατί η Python είναι διερμηνευόμενη, άρα πιο αργή γλώσσα
   - γιατί δεν έχει βασική περίπτωση
   - γιατί το $F_{30}$ είναι πολύ μεγάλος αριθμός
7. Τι κάνει η απομνημόνευση (memoization);
   - αποθηκεύει κάθε αποτέλεσμα την πρώτη φορά και μετά το ξαναδιαβάζει
   - αυξάνει το όριο της στοίβας, ώστε να χωρούν περισσότερες αναδρομικές κλήσεις
   - μετατρέπει την αναδρομή σε επανάληψη, ώστε να μη γεμίζει η στοίβα
   - θυμάται ποιες κλήσεις απέτυχαν, ώστε να μην τις ξαναδοκιμάσει
8. Σε ποιο πρόβλημα η αναδρομή είναι η πιο φυσική επιλογή;
   - στη μέτρηση όλων των αρχείων ενός φακέλου και των υποφακέλων του
   - στο άθροισμα των στοιχείων μιας πολύ μεγάλης λίστας, με $100\,000$ θέσεις
   - στην εκτύπωση των αριθμών από $1$ ως $10$
   - στην ανάγνωση ενός αριθμού από το πληκτρολόγιο
9. Πόσες κινήσεις χρειάζονται οι πύργοι του Ανόι με $5$ δίσκους;
   - $31$
   - $32$
   - $10$
   - $25$
10. Τι επιστρέφει η `f(3)`, αν `f(n)` επιστρέφει $0$ για n ίσο με $0$ και αλλιώς `n + f(n - 1)`;
   - $6$
   - $3$
   - $0$
   - $5$

## Ασκήσεις

1. Ποια είναι η βασική περίπτωση της συνάρτησης factorial της ενότητας;
2. Τι επιστρέφει η `digit_sum(9081)`;
3. Η συνάρτηση `power(x, n)` επιστρέφει `1` αν `n == 0`, αλλιώς `x * power(x, n - 1)`.
   α) Τι επιστρέφει η `power(3, 4)`;
   β) Πόσες κλήσεις της power γίνονται συνολικά;
4. Η απλή αναδρομική fib της ενότητας καλείται με όρισμα $5$.
   α) Τι επιστρέφει;
   β) Πόσες κλήσεις της fib γίνονται συνολικά;
   γ) Πόσες φορές καλείται η fib(2);

---

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