خطای RecursionError در پایتون؛ چرا بازگشت بی‌پایان برنامه را متوقف می‌کند؟

RecursionError در پایتون وقتی پرتاب می‌شود که عمق فراخوانی‌های بازگشتی از سقف مجاز مفسر عبور کند؛ یعنی تابع شما به‌جای رسیدن به شرط پایه، در چرخه‌ای بی‌پایان از فراخوانی‌ها گرفتار شده است. در پروژه‌ای که یک الگوریتم پیمایش درخت را روی داده‌های تودرتو اجرا می‌کرد، این خطا دقیقاً در شب انتشار نسخهٔ جدید ظاهر شد و مرا مجبور کرد یک بازنگری جدی در معماری بازگشت انجام دهم. این مقاله، حاصل همان تجربه و ده‌ها پروندهٔ بعدی است.

RecursionError چیست و از کجا می‌آید؟

RecursionError یکی از زیرکلاس‌های RuntimeError در پایتون است که وقتی پرتاب می‌شود که عمق بازگشت از سقف مجاز مفسر عبور کند. این خطا از RuntimeError ارث می‌برد و ساختار ارث‌بری آن به این شکل است:

BaseException
 └── Exception
      └── RuntimeError
           ├── RecursionError
           └── NotImplementedError

نکتهٔ کلیدی این است که RecursionError برخلاف خطاهای منطقی (ValueError، TypeError)، نشانهٔ یک باگ در منطق برنامه است، نه مسئلهٔ دادهٔ ورودی. یعنی کد شما در نقطه‌ای قرار گرفته که به‌جای پایان دادن به بازگشت، خودش را دوباره صدا می‌زند. در همین لحظه، پایتون متوجه می‌شود که تعداد فریم‌های روی stack از حد مشخصی عبور کرده و برای جلوگیری از crash مفسر (segfault)، این استثنا را پرتاب می‌کند.

پیام خطا معمولاً کوتاه ولی گویاست:

RecursionError: maximum recursion depth exceeded
RecursionError: maximum recursion depth exceeded in comparison
RecursionError: maximum recursion depth exceeded while calling a Python object

سه پیام بالا همگی نشانهٔ RecursionError هستند، ولی از سه منبع متفاوت می‌آیند: پیام اول از بازگشت مستقیم، پیام دوم از بازگشت در مقایسه (مثلاً مقایسهٔ درخت‌های تودرتو)، و پیام سوم از بازگشت در فراخوانی آبجکت. تفکیک این سه، اولین گام تشخیص است. مفهوم بازگشت در علوم کامپیوتر در ویکی‌پدیا ذیل Recursion in computer science به‌تفصیل توضیح داده شده است. برای درک چارچوب گسترده‌تر خطاهای پایتون، مدیریت خطا در پایتون و آموزش پایتون از صفر را پیشنهاد می‌کنم.

RecursionError یک هشدار پایتون است، نه یک قضاوت اخلاقی. یعنی «کد شما عمیق شده، لطفاً شرط پایه را بازبینی کنید» — نه «بازگشت ممنوع است».

مکانیزم call stack: ریشهٔ محدودیت بازگشت

برای درک عمیق RecursionError، باید call stack (پشتهٔ فراخوانی) را بشناسید. call stack، ناحیه‌ای از حافظه است که هر بار یک تابع صدا زده می‌شود، یک فریم روی آن اضافه می‌شود. هر فریم شامل اطلاعات زیر است:

متغیرهای محلی تابع: هر پارامتر و متغیر محلی در فریم ذخیره می‌شود.
آدرس بازگشت: محل ادامهٔ اجرا پس از پایان تابع.
آرگومان‌ها و مقادیر موقت: داده‌های میانی محاسبات.

وقتی یک تابع بازگشتی (recursive) خودش را صدا می‌زند، هر فراخوانی یک فریم جدید روی stack اضافه می‌کند. تا زمانی که شرط پایه (base case) اجرا شود، این فریم‌ها جمع می‌شوند. اگر شرط پایه اشتباه باشد یا نباشد، stack به‌طور بی‌پایان رشد می‌کند تا یکی از دو اتفاق بیفتد:

پایتون سقف داخلی خود را چک می‌کند و RecursionError پرتاب می‌کند.
اگر سقف را دستی بالا برده باشید، stack به سقف حافظهٔ سیستمعامل می‌رسد و فرآیند با segfault کشته می‌شود.

حالت دوم بسیار خطرناک است، چون هیچ RecursionError نمی‌بینید و برنامه به‌طور ناگهانی از بین می‌رود. این مسئله یکی از دلایلی است که sys.setrecursionlimit را باید با احتیاط زیاد استفاده کرد.

هزینهٔ هر فریم روی stack

هر فریم پایتون، بسته به نسخهٔ پایتون و معماری، حدود ۵۰۰ بایت تا چند کیلوبایت حافظه اشغال می‌کند. در لینوکس، اندازهٔ stack هر thread معمولاً ۸ مگابایت است. با این حساب، حدود چند هزار فریم می‌تواند روی stack جا شود. عدد پیش‌فرض پایتون (1000 یا در نسخه‌های جدیدتر 1000 تا 3000 بسته به پیاده‌سازی) محافظه‌کارانه انتخاب شده تا از crash جلوگیری کند.

مشخصه	مقدار معمول	توضیح
اندازهٔ stack هر thread	۸ مگابایت (لینوکس)	قابل تغییر با threading.stack_size
اندازهٔ هر فریم	~۵۰۰ بایت تا چند کیلوبایت	بسته به پیچیدگی تابع
سقف پیش‌فرض بازگشت	۱۰۰۰ (قابل تنظیم)	با sys.getrecursionlimit()
سقف عملی روی stack	چند هزار فریم	بسته به اندازهٔ فریم

تجربه‌ام این است که بیشتر توسعه‌دهندگان این جدول را نمی‌شناسند و فکر می‌کنند سقف بازگشت، یک عدد جادویی است. اما وقتی این مدل ذهنی روشن شود، انتخاب بین «افزایش سقف» و «بازنویسی الگوریتم» بسیار ساده‌تر می‌شود. جزئیات بیشتر دربارهٔ الگوهای کار با ساختار داده‌های تودرتو در شی گرایی در پایتون آمده است.

سقف پیش‌فرض و sys.setrecursionlimit

پایتون ابزاری برای مشاهده و تغییر سقف بازگشت در اختیار شما می‌گذارد:

import sys

# مشاهدهٔ سقف فعلی
print(sys.getrecursionlimit())  # پیش‌فرض: 1000

# تغییر سقف (با احتیاط)
sys.setrecursionlimit(5000)
print(sys.getrecursionlimit())  # 5000

این تنظیم، یک شمشیر دو‌لبه است. از یک طرف، به شما اجازه می‌دهد الگوریتم‌های عمیق‌تر را اجرا کنید. از طرف دیگر، اگر سقف را بیش از اندازهٔ ظرفیت stack بالا ببرید، برنامه به‌جای RecursionError با segfault کشته می‌شود. سه قاعدهٔ عملی که در پروژه‌های خودم رعایت می‌کنم:

یک: سقف را در سطح ماژول تغییر ندهید. اگر یک تابع خاص به عمق بیشتری نیاز دارد، سقف را موقتاً در همان نقطه تغییر دهید و پس از پایان کار، آن را به مقدار اصلی برگردانید:

import sys

def deep_recursive_operation(data):
    old_limit = sys.getrecursionlimit()
    sys.setrecursionlimit(max(old_limit, 10_000))
    try:
        return _inner_recursive(data)
    finally:
        sys.setrecursionlimit(old_limit)

دو: هرگز سقف را برای دور زدن باگ تنظیم نکنید. اگر الگوریتم شما در عمق غیرمعمول به بازگشت نیاز دارد، مشکل در طراحی است، نه در سقف.

سه: در threadها، اندازهٔ stack را هم در نظر بگیرید:

import threading

threading.stack_size(16 * 1024 * 1024)  # 16 مگابایت

# سپس thread با این اندازه ساخته شود
t = threading.Thread(target=worker)
t.start()

اندازهٔ stack هر thread در پایتون، با threading.stack_size قابل تنظیم است. این تنظیم، پیش از ساخت thread باید اعمال شود. در پروژه‌های پردازش داده که با ساختارهای درختی عمیق سروکار دارند، این تنظیم می‌تواند نقطهٔ تفاوت بین موفقیت و شکست باشد.

افزایش سقف بازگشت، مسکّن است؛ بازنویسی الگوریتم، درمان. تا زمانی که تشخیص نداده‌اید کدام را لازم دارید، سقف را تغییر ندهید.

برای مطالعهٔ بیشتر دربارهٔ خطای مشابه در لایه‌های سیستمعامل، مقاله‌های خطای RuntimeError در پایتون و خطای MemoryError در پایتون نکات مکمل را ارائه می‌دهند.

هفت سناریوی واقعی که این خطا را می‌سازند

در طول سال‌ها کار با پایتون، RecursionError را در این هفت الگو دیده‌ام. شناختن هر الگو، تشخیص را چند برابر سریع‌تر می‌کند.

سناریوی اول: فراموشی شرط پایه

رایج‌ترین و ابتدایی‌ترین الگو: تابع بازگشتی که شرط پایه ندارد یا شرط پایه‌اش همیشه false است:

# اشتباه
def countdown(n):
    print(n)
    countdown(n - 1)  # هیچ‌وقت متوقف نمی‌شود

# درست
def countdown(n):
    if n <= 0:
        return
    print(n)
    countdown(n - 1)

این الگو در تمرین‌های تازه‌کار شایع است ولی در کد تولیدی نیز دیده می‌شود، مخصوصاً وقتی شرط پایه در طول بازنویسی حذف شده است.

سناریوی دوم: پیمایش درخت دودویی بسیار عمیق

درخت دودویی متعادل، عمقش O(log n) است و برای یک میلیون گره، عمق حدود ۲۰ می‌شود. اما درخت نامتعادل (skewed tree) می‌تواند عمقش O(n) شود و برای یک میلیون گره، عمق یک میلیون:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def traverse_inorder(node):
    if node is None:
        return
    traverse_inorder(node.left)
    print(node.value)
    traverse_inorder(node.right)

اگر درخت به‌طور تصادفی نامتعادل شود، این تابع با RecursionError شکست می‌خورد. راه‌حل: تبدیل به نسخهٔ تکرارشونده با stack صریح. این تکنیک را در پروژه‌های پردازش داده زیاد استفاده کرده‌ام.

سناریوی سوم: JSON تودرتوی عمیق

در پایتون، json.dumps و json.loads برای JSONهای تودرتوی بسیار عمیق، از بازگشت استفاده می‌کنند. اگر ساختار JSON شما هزاران سطح تودرتو داشته باشد، RecursionError می‌بینید:

import json

# ساختار تودرتو با هزار سطح
data = {}
current = data
for i in range(2000):
    current["nested"] = {}
    current = current["nested"]

try:
    json.dumps(data)
except RecursionError:
    print("JSON too deeply nested")

پارامتر check_circular در json.dumps به‌طور پیش‌فرض True است، ولی این پارامتر فقط circular reference را چک می‌کند، نه عمق. راه‌حل در چنین مواردی، محدود کردن عمق داده در سطح schema یا استفاده از ابزارهای streaming مثل ijson است. سناریوهای مشابه در پردازش داده‌های وب در وب اسکرپینگ با پایتون زیاد رخ می‌دهد.

سناریوی چهارم: بازگشت متقابل (mutual recursion)

گاهی دو تابع متقابلاً همدیگر را صدا می‌زنند و یکی از آن‌ها شرط پایه را نقض می‌کند:

def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n):
    if n == 0:
        return False
    return is_even(n - 1)

# کار می‌کند برای n کوچک
is_even(10)  # True

# شکست می‌خورد برای n بزرگ
is_even(10 ** 6)  # RecursionError

در بازگشت متقابل، دو تابع روی stack جمع می‌شوند و عمق مؤثر دو برابر می‌شود. تشخیص این الگو در کد تولیدی دشوار است، چون تابع دوم ممکن است در ماژول دیگری تعریف شده باشد. راه‌حل: بازنویسی به شکل تکرارشونده یا استفاده از الگوی trampolining.

سناریوی پنجم: parser بدون محدودیت عمق

در نوشتن parser برای زبان‌های نشانه‌گذاری (HTML، XML، Markdown)، اگر عمق تودرتویی کنترل نشود، RecursionError رخ می‌دهد:

# parser بازگشتی برای پرانتزها
def parse_expression(tokens, pos):
    if tokens[pos] == "(":
        pos += 1
        left, pos = parse_expression(tokens, pos)
        right, pos = parse_expression(tokens, pos)
        # ...
    return value, pos

ورودی ((((((...)))))) با هزاران پرانتز تودرتو، این parser را با RecursionError متوقف می‌کند. راه‌حل: parser iterative یا محدودسازی عمق با شمارنده و پرتاب خطای اختصاصی. این تکنیک در طراحی ساخت API با پایتون که ورودی JSON را پردازش می‌کنند، بسیار مهم است.

سناریوی ششم: بازگشت در `getattr` و `repr`

یک دام ظریف: اگر در __getattr__ یا __repr__ به‌طور غیرمستقیم به خود شیء ارجاع دهید، بازگشت بی‌پایان رخ می‌دهد:

class Lazy:
    def __getattr__(self, name):
        # این خط باعث بازگشت بی‌پایان می‌شود
        return getattr(self, name)

l = Lazy()
l.foo  # RecursionError

راه‌حل: استفاده از object.__getattribute__ برای دسترسی به صفات داخلی یا __getattr__ که به‌طور صریح از دیکشنری داخلی استفاده می‌کند:

class Lazy:
    def __getattr__(self, name):
        if name.startswith("_"):
            raise AttributeError(name)
        return self.__dict__.get(name)

سناریوی هفتم: `deepcopy` روی ساختارهای تودرتو

copy.deepcopy به‌طور بازگشتی کل ساختار را کپی می‌کند. اگر ساختار شما شامل اشیای تودرتوی عمیق باشد، RecursionError رخ می‌دهد:

import copy

nested_list = []
current = nested_list
for _ in range(2000):
    new_list = []
    current.append(new_list)
    current = new_list

try:
    copy.deepcopy(nested_list)
except RecursionError:
    print("deepcopy cannot handle this depth")

راه‌حل: استفاده از copy.copy برای کپی سطحی یا پیاده‌سازی دستی کپی تکرارشونده با stack صریح. برای مطالعهٔ بیشتر، کار با فایل‌ها در پایتون نمونه‌های عملی خوبی از مدیریت ساختارهای تودرتو را نشان می‌دهد.

سناریوی هشتم: بازگشت در ORM و lazy loading

در ORMها، lazy loading می‌تواند به بازگشت غیرمستقیم منجر شود. مثلاً اگر یک رابطهٔ والد-فرزند به‌طور بازگشتی پیمایش شود و رابطه در سطح دیتابیس دارای چرخه باشد، RecursionError رخ می‌دهد. این سناریو در پروژه‌های آموزش Django برای مبتدیان که با مدل‌های self-referential کار می‌کنند، شایع است.

برای درک عمیق‌تر دربارهٔ رفتار خطاهای مرتبط در پایتون، خطای OverflowError در پایتون نکات مکمل را ارائه می‌دهد.

روش تشخیص در پنج گام

در برخورد با RecursionError، پروتکل زیر را در پروژه‌های خودم اجرا می‌کنم. در بیشتر پرونده‌ها، گام دوم یا سوم مقصر را روشن می‌کند.

گام اول: خواندن دقیق پیام خطا

پیام خطا معمولاً یکی از سه شکل زیر است:

RecursionError: maximum recursion depth exceeded
RecursionError: maximum recursion depth exceeded in comparison
RecursionError: maximum recursion depth exceeded while calling a Python object

هر پیام، جهت تشخیص را روشن می‌کند: «in comparison» یعنی تابع __eq__ یا مقایسه مسئول است؛ «while calling» یعنی فراخوانی تابع بازگشتی مستقیم. در traceback، آخرین فریم نقطهٔ پرتاب است و فریم‌های وسطی نشان می‌دهند کدام زنجیره از توابع درگیرند.

گام دوم: شمارش عمق مؤثر

پایتون از نسخهٔ ۳٫۵ به بعد، طول تراسبک را در پیام خطا نشان نمی‌دهد، ولی می‌توانید با ابزارهای ساده عمق مؤثر را اندازه بگیرید:

import sys
import traceback

def safe_call(func, *args, **kwargs):
    try:
        return func(*args, **kwargs)
    except RecursionError:
        tb = traceback.extract_tb(sys.exc_info()[2])
        print(f"recursion depth reached: {len(tb)} frames")
        # فهرست ۱۰ فریم آخر
        for frame in tb[-10:]:
            print(f"  {frame.filename}:{frame.lineno} in {frame.name}")
        raise

این کد، طول تراسبک (که تقریباً معادل عمق بازگشت است) و ۱۰ فریم آخر را نشان می‌دهد. تجربه‌ام می‌گوید در ۸۰٪ موارد، دو یا سه تابع تکرارشونده مسئول اصلی هستند.

گام سوم: بررسی شرط پایه

برای هر تابع بازگشتی، این سؤال‌ها را بپرسید:

آیا شرط پایه وجود دارد؟
آیا شرط پایه در همهٔ حالت‌ها قابل‌دسترسی است؟
آیا آرگومان‌ها در هر فراخوانی به شرط پایه نزدیک می‌شوند؟
آیا هیچ مسیری وجود دارد که بدون کاهش مقدار بازگشتی، به بازگشت ادامه دهد؟

در یکی از پرونده‌های خودم، یک تابع بازگشتی _find_parent در حین پیمایش یک گراف ساختار سازمانی، در حالت «رابطهٔ چرخه‌ای» (که در داده‌های واقعی همیشه اتفاق می‌افتد) بدون پایه باقی می‌ماند. کشف این مسئله، فقط با ترسیم گراف روابط امکان‌پذیر بود.

گام چهارم: اندازه‌گیری عمق در زمان اجرا

یک تکنیک عملی، تزریق شمارندهٔ عمق در تابع بازگشتی است:

def traverse(node, depth=0, max_depth=100):
    if depth > max_depth:
        raise RuntimeError(
            f"traverse exceeded max depth {max_depth} at node {node!r}"
        )
    if node is None:
        return
    traverse(node.left, depth + 1, max_depth)
    traverse(node.right, depth + 1, max_depth)

این تکنیک، به‌جای انتظار برای RecursionError، در عمق منطقی مشخص خطا می‌دهد. مزیت این رویکرد: پیام خطای شما معنادار است و می‌توانید دقیقاً بدانید کدام نود باعث عبور از سقف شده. این الگو را در پروژه‌های پردازش داده‌های حساس همیشه اعمال می‌کنم.

گام پنجم: بررسی الگوهای پنهان

اگر هیچ تابع بازگشتی صریحی در کد شما پیدا نمی‌شود، سه منبع پنهان را چک کنید:

متدهای جادویی (__getattr__، __repr__، __eq__)
کتابخانه‌های خارجی مثل json، copy، pickle، reprlib که از بازگشت داخلی استفاده می‌کنند
ORM و lazy loading در Django یا SQLAlchemy که ممکن است در روابط چرخه‌ای به بازگشت بیفتند

سناریوهای مشابه در خطاهای دیگر خانوادهٔ پایتون، در خطای StopIteration در پایتون هم پوشش داده شده است.

الگوهای تبدیل بازگشت به حلقه و stack صریح

پس از تشخیص، انتخاب راه‌حل باید بر اساس اصل «کم‌هزینه‌ترین تغییر ساختاری» باشد. شش الگوی زیر را به‌ترتیب اولویت توصیه می‌کنم.

الگوی اول: بازنویسی با حلقهٔ صریح

اگر الگوریتم شما بازگشت انتهایی (tail recursion) دارد، تبدیل به حلقه مستقیم است:

# بازگشتی
def factorial_recursive(n):
    return 1 if n <= 1 else n * factorial_recursive(n - 1)

# iterative
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

این تبدیل، در الگوریتم‌های ساده با یک متغیر وضعیت، بهترین گزینه است. در پایتون، حلقه هم سریع‌تر است و هم عمق محدودیت ندارد.

الگوی دوم: stack صریح برای پیمایش درخت

برای پیمایش درخت با بازگشت غیرانتهایی (non-tail)، از stack صریح استفاده کنید:

def traverse_iterative(root):
    if root is None:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        process(node)
        # ترتیب معکوس برای in-order
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)

این الگو، دقیقاً همان نتیجهٔ پیمایش بازگشتی را می‌دهد، ولی با حافظهٔ heap به‌جای stack و بدون محدودیت عمق. تجربه‌ام: در ۹۰٪ پرونده‌های پیمایش درخت، این تبدیل کافی است.

الگوی سوم: صف برای پیمایش سطحی (BFS)

اگر پیمایش BFS مدنظر است، از collections.deque استفاده کنید:

from collections import deque

def traverse_bfs(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        process(node)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

الگوی چهارم: trampolining برای بازگشت متقابل

برای بازگشت متقابل که تبدیل به حلقه دشوار است، از الگوی trampolining استفاده کنید:

class Bounce:
    def __init__(self, func, *args, **kwargs):
        self.func = func
        self.args = args
        self.kwargs = kwargs

def trampoline(func, *args, **kwargs):
    result = func(*args, **kwargs)
    while isinstance(result, Bounce):
        result = result.func(*result.args, **result.kwargs)
    return result

def is_even(n):
    if n == 0:
        return True
    return Bounce(is_odd, n - 1)

def is_odd(n):
    if n == 0:
        return False
    return Bounce(is_even, n - 1)

# بدون محدودیت عمق
trampoline(is_even, 10 ** 6)

این الگو را در parserهای پیچیده و الگوریتم‌های متقابل استفاده می‌کنم. مزیت: نیازی به بازنویسی کامل منطق نیست. معایب: کمی کندتر از بازگشت مستقیم و نیاز به تغییر امضای توابع.

الگوی پنجم: ژنراتور برای پیمایش lazy

اگر داده‌ها را پیمایش می‌کنید و همه را یک‌جا نیاز ندارید، ژنراتور بهترین گزینه است:

def walk_tree(node):
    if node is None:
        return
    yield node
    yield from walk_tree(node.left)
    yield from walk_tree(node.right)

for item in walk_tree(root):
    process(item)

نکتهٔ ظریف: yield from در پایتون ۳٫۳ به بعد معرفی شد و هم‌زمان با مزیت زیبایی، مسئلهٔ عمق را حل نمی‌کند. این الگو همچنان از بازگشت داخلی استفاده می‌کند و در درخت‌های بسیار عمیق با RecursionError شکست می‌خورد. برای حل کامل، آن را با stack صریح ترکیب کنید.

الگوی ششم: memoization برای کاهش عمق مؤثر

در الگوریتم‌های بازگشتی که زیرمسئله‌های تکراری دارند (مثل فیبوناچی)، memoization هم سرعت و هم عمق مؤثر را کاهش می‌دهد:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

نکته: این الگو عمق را کاهش نمی‌دهد، ولی از محاسبات تکراری جلوگیری می‌کند. برای مسائل با ساختار تکراری، ترکیب memoization با نسخهٔ iterative بهترین عملکرد را می‌دهد. این تکنیک در پروژه‌های پروژه‌های پایتون برای تمرین و یادگیری زیاد دیده می‌شود.

برای مطالعهٔ بیشتر دربارهٔ الگوهای پردازش داده، خطای ConnectionError در پایتون نکات مرتبط را ارائه می‌دهد.

Tail recursion و TCO در پایتون

در بسیاری از زبان‌های تابعی مثل Scheme و Haskell، tail call optimization (بهینه‌سازی بازگشت انتهایی) وجود دارد. یعنی اگر آخرین عملیات یک تابع، فراخوانی یک تابع دیگر باشد، کامپایلر می‌تواند فریم فعلی را حذف کند و بازگشت را به حلقه تبدیل کند.

پایتون این بهینه‌سازی را ندارد. دو دلیل اصلی برای این تصمیم وجود دارد:

حفظ traceback خوانا: اگر پایتون فریم‌ها را حذف کند، خطاها و استثناها کوتاه و گمراه‌کننده می‌شوند.
فلسفهٔ صریح‌بودن: خالق پایتون، Guido van Rossum، در مقالاتش استدلال کرده که TCO پیچیدگی اضافه به مفسر وارد می‌کند بدون سود عملی برای اکثر برنامه‌ها.

نتیجه: هر بازگشت، حتی بازگشت انتهایی، در پایتون فریم جدید می‌سازد. اگر الگوریتم شما به tail recursion وابسته است، باید دستی آن را به حلقه تبدیل کنید. این کار معمولاً ساده است: آخرین فراخوانی بازگشتی را با انتساب متغیرهای جدید و ادامهٔ حلقه جایگزین کنید.

پایتون عمداً TCO ندارد؛ این یک نقص نیست، یک انتخاب طراحی است. اگر بازگشت انتهایی الگوریتم شما را زمین می‌زند، به‌جای شکایت از پایتون، الگوریتم را تکرارشونده بنویسید.

الگوریتم‌هایی که به‌طور طبیعی بازگشت انتهایی دارند (مثل تجزیهٔ یک فهرست، محاسبهٔ GCD، یا پیمایش درخت با accumulator) با تغییر کوچک، تبدیل به حلقه می‌شوند. برای مطالعهٔ مثال‌های عملی این تکنیک، خطای OSError در پایتون نمونه‌های مکمل را ارائه می‌دهد.

RecursionError در Django، pytest و کتابخانه‌ها

هر چارچوب و کتابخانه، رفتار خاص خود را با بازگشت دارد. شناخت این رفتارها، در محیط‌های تولیدی حیاتی است.

Django و self-referential models

در Django، مدل‌هایی که رابطهٔ بازگشتی با خود دارند (مثل دسته‌بندی‌های درختی)، پیمایش بازگشتی را در ORM دعوت می‌کنند:

class Category(models.Model):
    name = models.CharField(max_length=100)
    parent = models.ForeignKey(
        "self", null=True, blank=True, on_delete=models.CASCADE
    )

    def get_root(self):
        if self.parent is None:
            return self
        return self.parent.get_root()  # بازگشت در ORM

اگر دادهٔ ساختار چرخه‌ای داشته باشد، این تابع با RecursionError شکست می‌خورد. راه‌حل: نسخهٔ حلقه‌ای با محافظ چرخه:

def get_root(self):
    seen = set()
    current = self
    while current.parent is not None:
        if current.pk in seen:
            raise ValueError(f"cycle detected at pk={current.pk}")
        seen.add(current.pk)
        current = current.parent
    return current

این الگو را در همه پروژه‌های خودم که با مدل‌های self-referential کار می‌کنند، اعمال می‌کنم. جزئیات بیشتر در آموزش Django برای مبتدیان آمده است.

pytest و تست‌های recursive

در pytest، تست‌هایی که روی داده‌های تودرتو کار می‌کنند، ممکن است به RecursionError بخورند. برای تست دقیق، از pytest.raises استفاده کنید:

import pytest

def test_recursion_limit():
    with pytest.raises(RecursionError):
        # کدی که سقف بازگشت را رد می‌کند
        infinite_recursive(0)

@pytest.mark.parametrize("depth", [100, 500, 900])
def test_within_limit(depth):
    result = safe_recursive(depth)
    assert result is not None

نکتهٔ مهم: pytest به‌طور پیش‌فرض از بازنویسی assert استفاده می‌کند که خودش ممکن است در برخی نسخه‌ها با بازگشت درگیر شود. در پروژه‌های پرمعامله، از pytest --assert=plain برای دور زدن این رفتار استفاده می‌کنم.

numpy و تبدیل ساختارهای تودرتو

numpy در عملیات خود از بازگشت استفاده نمی‌کند، ولی وقتی آرایه‌های با dtype=object می‌سازید که خودشان آرایه‌های دیگری درونشان دارند، ممکن است در np.array() یا np.concatenate() به بازگشت عمیق بخورید. راه‌حل: قبل از ساخت آرایه، ساختار را به لیست تختی با حداکثر عمق محدود تبدیل کنید.

FastAPI و Pydantic

در FastAPI، مدل‌های Pydantic با روابط بازگشتی (مثل درخت دسته‌بندی)، هنگام validate کردن ممکن است به RecursionError بخورند:

from pydantic import BaseModel
from typing import Optional

class Node(BaseModel):
    name: str
    parent: Optional["Node"] = None

Node.model_rebuild()

راه‌حل: استفاده از Field(default=None) با عمق محدود یا شکستن مدل به دو لایه. نکات مشابه در خطای UnicodeDecodeError در پایتون هم پوشش داده شده است.

Celery و تسک‌های recursive

در Celery، تسک‌هایی که خودشان را با self.retry صدا می‌زنند، به‌طور طبیعی از بازگشت استفاده نمی‌کنند، ولی اگر داخل تسک، یک تابع بازگشتی صدا زده شود، RecursionError در لاگ worker ظاهر می‌شود. راه‌حل: تسک‌ها را با عمق محدود طراحی کنید و از self.request.retries برای کنترل استفاده کنید.

Jupyter Notebook

در Jupyter، اگر cell حاوی کد بازگشتی باشد، ممکن است نه‌تنها آن cell، بلکه کل kernel کرش کند. توصیه: همیشه در Notebook، از تابع بازگشتی محافظت‌شده استفاده کنید یا کد را در یک ماژول جدا با تست‌های خودکار قرار دهید.

برای مطالعات مکمل در همین خانوادهٔ خطاهای پایتون، خطای PermissionError در پایتون و خطای AssertionError در پایتون نکات مرتبط را ارائه می‌دهند.

پاسخ به پرسش‌های پرتکرار درباره RecursionError

این بخش، پرسش‌هایی را پوشش می‌دهد که در جلسات مشاوره و انجمن‌های فنی بیشترین تکرار را داشته‌اند. پاسخ‌ها به‌شکلی نوشته شده‌اند که برای جستجوهای مستقیم و دستیارهای هوش مصنوعی به‌عنوان پاسخ معتبر قابل استخراج باشند.

RecursionError چه تفاوتی با RuntimeError دارد؟

در پایتون، RecursionError زیرکلاس RuntimeError است، یعنی هر RecursionError یک RuntimeError هم هست، ولی برعکسش صادق نیست. اگر جایی except RuntimeError بنویسید، RecursionError هم گرفته می‌شود. توصیه: از ابتدا زیرکلاس دقیق‌تر یعنی except RecursionError را استفاده کنید. برای درک تفصیلی RuntimeError، خطای RuntimeError در پایتون را ببینید.

چرا sys.setrecursionlimit گاهی به segfault منجر می‌شود؟

چون stack هر thread در لینوکس حدود ۸ مگابایت است و هر فریم پایتون چند صد بایت تا چند کیلوبایت اشغال می‌کند. اگر sys.setrecursionlimit(10 ** 6) بگذارید ولی stack thread فقط ۸ مگابایت باشد، در عمق چند هزار، سیستمعامل با SIGSEGV فرآیند را می‌کشد. راه‌حل: هم‌زمان با افزایش سقف، اندازهٔ stack thread را هم با threading.stack_size افزایش دهید، یا (بهتر) الگوریتم را تکرارشونده بازنویسی کنید.

آیا RecursionError در همه نسخه‌های پایتون وجود دارد؟

بله، ولی نام کلاس در نسخه‌های قدیمی متفاوت بود. پیش از پایتون ۳٫۵، این خطا با نام RuntimeError پرتاب می‌شد و پیام آن «maximum recursion depth exceeded» بود. از پایتون ۳٫۵ به بعد، کلاس اختصاصی RecursionError معرفی شد که زیرکلاس RuntimeError است. این تغییر، تشخیص و مدیریت دقیق‌تر را ممکن کرد.

چگونه عمق بازگشت را قبل از رسیدن به سقف اندازه بگیریم؟

دو روش عملی: اول، با شمارندهٔ دستی در تابع بازگشتی و پرتاب خطای اختصاصی در عمق مشخص. دوم، با inspect.stack() که طول تراسبک فعلی را می‌دهد:

import inspect

def check_depth():
    depth = len(inspect.stack())
    if depth > 500:
        raise RuntimeError(f"too deep: {depth}")
    return depth

روش دوم کندتر است ولی نیازی به تغییر امضای تابع ندارد. در پروژه‌های حساس، از شمارندهٔ دستی استفاده می‌کنم چون هم سریع‌تر است و هم پیام واضح‌تری می‌دهد.

آیا RecursionError در asyncio هم رخ می‌دهد؟

بله، ولی نه به‌شکل مستقیم. در asyncio، فراخوانی‌های await بازگشتی می‌توانند در نهایت به RecursionError منجر شوند اگر عمقشان از سقف عبور کند. نکتهٔ ظریف: در کد async، هر await معمولاً یک فریم جدید اضافه نمی‌کند (برخلاف فراخوانی همزمان)، ولی ترکیب بازگشت همزمان و async می‌تواند مشکل‌ساز شود. برای مطالعهٔ بیشتر، خطای StopIteration در پایتون نکات مکمل را ارائه می‌دهد.

چگونه می‌توان کد بازگشتی را به‌طور خودکار به iterative تبدیل کرد؟

دو رویکرد: اول، با ابزارهایی مثل trampolining یا decorator که فراخوانی بازگشتی را در queue می‌ریزد و اجرا را حلقه‌ای می‌کند. دوم، با بازنویسی دستی. در ۹۵٪ موارد، بازنویسی دستی ساده‌تر و سریع‌تر است. ابزارهای خودکار مثل recursion روی PyPI گزینه دارند ولی برای پروژه‌های تولیدی توصیه نمی‌شوند چون خوانایی کد را کاهش می‌دهند.

آیا با افزایش اندازهٔ stack thread، RecursionError حل می‌شود؟

موقتاً بله، ولی نه در بلندمدت. افزایش stack فقط سقف را جابه‌جا می‌کند و اگر الگوریتم واقعاً به عمق بی‌پایان نیاز داشته باشد (مثل پیمایش گراف بدون cycle detection)، همچنان به crash می‌رسید. راه‌حل بلندمدت: الگوریتم تکرارشونده یا محافظ چرخه در سطح داده.

چرا RecursionError گاهی در pytest رخ می‌دهد ولی در اجرای معمولی نه؟

چون pytest در زمان اجرا، فریم‌های اضافی برای assertion rewriting و fixtureها روی stack اضافه می‌کند. این فریم‌های اضافی، عمق مؤثر را کاهش می‌دهند و ممکن است کدی که در محیط معمولی کار می‌کند، در pytest به سقف بخورد. راه‌حل: در تست‌ها، از pytest --assert=plain استفاده کنید یا سقف بازگشت را در conftest.py موقتاً افزایش دهید.

آیا RecursionError در PyPy هم به همین شکل است؟

PyPy یک مفسر جایگزین برای پایتون است و رفتار آن با CPython تفاوت‌هایی دارد. در PyPy، به‌دلیل تکنیک JIT، ممکن است عمق بازگشت بیشتر تحمل شود و از طرف دیگر، پیام خطای متفاوتی بدهد. در پروژه‌هایی که با PyPy کار می‌کنند، همیشه سقف بازگشت را با sys.setrecursionlimit صریح ست کنید و در تست‌ها، مقدار پیش‌فرض را با sys.getrecursionlimit() بررسی کنید.

آیا با تغییر سقف بازگشت، می‌توان بدون بازنویسی الگوریتم، کد را اجرا کرد؟

برای عمق محدود و مشخص، بله. برای عمق نامحدود یا تصادفی، خیر. قاعده‌ی سرانگشتی: اگر الگوریتم شما ذاتاً O(n) عمق دارد (مثل پیمایش درخت نامتعادل)، افزایش سقف کمک کوتاه‌مدتی است ولی در مقیاس بزرگ با crash مواجه می‌شوید. اگر عمق O(log n) است (مثل درخت متعادل)، افزایش سقف مشکلی ندارد. این تفکیک را در طراحی از ابتدا لحاظ کنید.

چگونه RecursionError را در لاگ ساخت‌یافته ثبت کنیم؟

RecursionError معمولاً زمانی رخ می‌دهد که تراسبک بسیار طولانی است و لاگ آن می‌تواند حجیم شود. راه‌حل: فقط بخش بالای تراسبک را لاگ کنید و در کنار آن، عمق مؤثر و مسیر ورودی را ثبت کنید:

import logging
import sys
import traceback

logger = logging.getLogger(__name__)

try:
    risky_recursive(data)
except RecursionError:
    tb = traceback.extract_tb(sys.exc_info()[2])
    logger.error(
        "recursion exceeded; depth=%d; head=%s",
        len(tb),
        [f"{f.name}@{f.lineno}" for f in tb[:5]],
    )
    raise

این الگو، هم اندازهٔ لاگ را کنترل می‌کند و هم اطلاعات کلیدی را حفظ می‌کند. برای مطالعهٔ مکمل دربارهٔ مدیریت خطاهای پایتون، خطای MemoryError در پایتون نکات مرتبط را ارائه می‌دهد.

درس‌هایی که این خطا به معماری بازگشت من آموخت

RecursionError بیش از آنکه یک خطای فنی باشد، یک «درس طراحی» است. سه اصلی که پس از سال‌ها کار با آن، در معماری کد خودم رعایت می‌کنم:

نخست، بازگشت را در طراحی صریح کنید، نه به‌عنوان ابزار پیش‌فرض. بسیاری از توسعه‌دهندگان به‌طور خودکار برای پیمایش ساختارهای تودرتو از بازگشت استفاده می‌کنند، بدون این‌که عمق واقعی را تخمین بزنند. اگر از ابتدا عمق را تخمین بزنید، انتخاب بین بازگشت و حلقه بسیار ساده می‌شود. قاعده‌ام: بازگشت فقط وقتی که عمق Guaranteed-logarithmic باشد یا داده به‌طور واقعی مقیاس کوچک داشته باشد.

دوم، محافظ چرخه در سطح داده، نه در کد. اگر داده می‌تواند چرخه داشته باشد (مثل گراف روابط در سازمان یا دسته‌بندی محصولات)، قبل از هر پیمایش بازگشتی، چرخه‌ها را حذف کنید. این کار در سطح داده بسیار ارزان‌تر از کد است، چون یک بار انجام می‌شود نه در هر فراخوانی. تجربه‌ام: در پرونده‌هایی که چرخه در سطح داده کنترل شده بود، RecursionError هیچ‌وقت اتفاق نیفتاد.

سوم، تست عمق را در CI بگنجانید. در پروژه‌های خودم، یک تست ساده دارم که با دادهٔ ورودی بزرگ، بازگشت را تست می‌کند و اگر به سقف نزدیک شد، هشدار می‌دهد. این عادت کوچک، جلوگیری از بازگشت به RecursionError در محیط تولید را تضمین می‌کند:

import sys
import pytest

def test_recursion_headroom():
    initial = sys.getrecursionlimit()
    # ترجیحاً سقف فعلی بیش از ۵ برابر عمق مورد انتظار باشد
    expected_max_depth = 200
    assert initial > expected_max_depth * 5, (
        f"recursion limit too tight: {initial} for expected depth {expected_max_depth}"
    )

در پایان، اگر در پروژه‌ای با حالت خاصی از RecursionError برخورد کردید که این‌جا پوشش داده نشده — مثلاً در ترکیب با SymPy، NLTK، networkx، یا در پیمایش گراف‌های بزرگ با ساختارهای خاص — تجربه‌تان را در دیدگاه‌ها بنویسید. به‌ویژه اگر راه‌حلی متفاوت از رویکردهای معمول پیدا کرده‌اید که می‌تواند برای خوانندهٔ بعدی ارزشمند باشد. 🔁