Τι είναι η αναδρομή (Recursion);

Question

Accepted Answer

**Αναδρομή (Recursion)** είναι όταν μια συνάρτηση καλεί τον εαυτό της για να λύσει μια μικρότερη έκδοση του ίδιου προβλήματος. Κάθε αναδρομή χρειάζεται μια **βασική περίπτωση (base case)** που την σταματά και μια **αναδρομική περίπτωση (recursive case)** που κινείται προς τη βασική περίπτωση.

## Η ιδέα

Διαιρέστε ένα πρόβλημα σε μικρότερα πανομοιότυπα υποπροβλήματα. Κάθε κλήση ωθεί ένα πλαίσιο στη **στοίβα κλήσεων (call stack)**· οι επιστροφές τα αφαιρούν.

## Παράδειγμα

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## Ιχνη

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## Πολυπλοκότητα

Εδώ **O(n)** χρόνος και **O(n)** χώρος στοίβας (ένα πλαίσιο ανά κλήση).

## Παγίδες

- **Λείπουσα βασική περίπτωση** -> άπειρη αναδρομή -> υπερχείλιση στοίβας.
- Βαθιά αναδρομή μπορεί να εξαντλήσει τη στοίβα· μερικές γλώσσες στερούνται βελτιστοποίησης tail-call.
- Η επανυπολογισμός επικαλυπτόμενων υποπροβλημάτων μπορεί να φτάσει σε εκθετικό χρόνο (διορθώστε με memoization).

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

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

Είναι το νοητικό μοντέλο πίσω από merge sort, backtracking και δυναμικό προγραμματισμό.

Η κατανόηση της στοίβας κλήσεων σας κάνει επίσης καλύτερους στο debugging και στη συλλογιστική σχετικά με τη μνήμη.