Python RecursionError — πρώτα έλεγξε τον τερματισμό

Τι συμβαίνει

Κάθε αναδρομική κλήση προσθέτει frame. Χωρίς base case ή χωρίς πρόοδο προκύπτει RecursionError. Η αύξηση του sys.setrecursionlimit σε τεράστια τιμή μπορεί να καταρρεύσει τον interpreter· δεν διορθώνει τον αλγόριθμο.

def bad_count(n):
    return 1 + bad_count(n)  # το n δεν μειώνεται· μην το τρέξεις ως test

Κατασκεύασε μέτρο που μειώνεται

Χρειάζεται τερματική περίπτωση και τιμή που μειώνεται αυστηρά σε κάθε βήμα.

def count_down(n: int) -> int:
    if n < 0:
        raise ValueError("nonnegative input required")
    if n == 0:
        return 0
    return 1 + count_down(n-1)

assert count_down(4) == 4
assert count_down(0) == 0

Μεγάλο βάθος: προτίμησε iteration

Όταν ο αριθμός βημάτων μπορεί να είναι μεγάλος, χρησιμοποίησε loop αντί για αλλαγή interpreter limit:

def iterative_count(n: int) -> int:
    if n < 0: raise ValueError("negative")
    result = 0
    while n:
        result += 1
        n -= 1
    return result

assert iterative_count(20000) == 20000

Άσκηση: σχεδίασε τα frames για count_down(3), βρες invariant και έλεγξε αρνητική είσοδο. Πηγή: https://docs.python.org/3/library/exceptions.html#RecursionError

Βάθος, κύκλοι και εναλλακτικός αλγόριθμος

Το RecursionError δεν σημαίνει πάντοτε «λάθος όριο της Python». Μπορεί να υπάρχει κυκλική αναφορά στο γράφημα: A → B → A αναγκάζει έναν αφελή recursive walker να επισκέπτεται τα ίδια στοιχεία για πάντα. Δοκίμασε χωριστά μια αλυσίδα 20.000 κόμβων, ένα γράφημα με κύκλο και πολλά αδέλφια σε μικρό βάθος. Μια iterative λύση με δική της stack αντιμετωπίζει το μεγάλο βάθος, αλλά στον κύκλο χρειάζεται επιπλέον visited set. Το υπερβολικό sys.setrecursionlimit δεν διορθώνει τον κύκλο και μπορεί να καταλήξει σε native stack overflow.