Επανάληψη έναντι αναδρομής — ποια είναι τα συμψηφίσματα;

Question

Accepted Answer

**Η επανάληψη** χρησιμοποιεί βρόχους· **η αναδρομή** χρησιμοποιεί αυτοκλήσεις. Είναι εξίσου ισχυρές (ό,τι μπορείς να κάνεις με τη μία μπορείς να κάνεις με την άλλη), αλλά διαφέρουν στη σαφήνεια και το κόστος.

## Δίπλα-δίπλα

```python
# Iterative sum: constant extra space
def sum_iter(n):
    total = 0
    for i in range(1, n + 1):
        total += i        # accumulate in a loop
    return total

# Recursive sum: uses the call stack
def sum_rec(n):
    if n == 0:
        return 0
    return n + sum_rec(n - 1)
```

## Σύγκριση

| Πτυχή | Επανάληψη | Αναδρομή |
|--------|-----------|-----------||
| Μνήμη | O(1) επιπλέον | O(βάθος) stack |
| Αναγνωσιμότητα | εξαιρετική για γραμμική εργασία | εξαιρετική για δέντρα / διαίρει-και-κυβέρνα |
| Κίνδυνος | άπειρος βρόχος | переполнение stack |
| Ταχύτητα | συνήθως ταχύτερη (χωρίς κόστος κλήσης) | κόστος κλήσης ανά frame |

## Πότε να χρησιμοποιήσεις ποια

- Χρησιμοποίησε **επανάληψη** για απλές γραμμικές διαπεράσεις και όταν το βάθος stack θα μπορούσε να είναι μεγάλο.
- Χρησιμοποίησε **αναδρομή** όταν το πρόβλημα είναι φυσικά αναδρομικό (δέντρα, γραφήματα, backtracking) και το βάθος είναι περιορισμένο.

## Παγίδες

Η βαθιά αναδρομή κινδυνεύει να переполнит το stack· μετατρέπει το ζεστό αναδρομικό κώδικα σε επανάληψη (συχνά με ένα ρητό stack) όταν το βάθος είναι απεριόριστο.

## Γιατί αυτό έχει σημασία

Η επιλογή του σωστού στυλ κρατά τον κώδικα τόσο σωστό όσο και αναγνώσιμο.

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

Αυτή η κρίση συμψηφίσματος είναι ακριβώς αυτό που έρευνούν οι συνεντευκτές όταν σε ζητούν να "μετατρέψεις αυτό σε επαναληπτικό."