بازگشت یعنی تابعی که برای حل مسئله خودش را روی یک نسخه کوچک‌تر از همان مسئله صدا می‌زند. تنها چیزی که آن را از یک حلقه بی‌پایان جدا می‌کند شرط پایان است: ورودی‌ای که تابع بدون صدا زدن خودش جوابش را می‌داند.
نسخه بدون شرط پایان بی‌نهایت اجرا نمی‌شود. اندازه‌گیری‌شده روی پایتون 3.14 در تاریخ ۲۰۲۶-۰۹-۰۳، یک تابع که فقط خودش را صدا می‌زند در حدود دو ده‌هزارم ثانیه با RecursionError می‌ایستد. یعنی اشتباه گران نیست، فوری است، و اگر برنامه‌ای دقایقی طول کشیده و بعد ایستاده، مسئله بازگشت بی‌پایان نبوده.
شکل درست، سه سطر و همیشه همین ترتیب:
def hajm(gerehha):if not gerehha: return 0return sum(v["andaze"] + hajm(v["zir"]) for v in gerehha.values())
سطر دوم اول نوشته می‌شود و بعد بقیه. دلیلش سبک نیست: تا وقتی شرط پایان نوشته نشده، هر بار اجرا کردن کد یک شکست است و شما دارید چیزی را اشکال‌زدایی می‌کنید که هنوز کامل نیست.
بازگشت برای داده‌ای است که خودش تودرتوست
معیار ساده این است: اگر داده شما داخل خودش داده‌ای از همان جنس دارد، بازگشت طبیعی‌ترین شکل نوشتن است. یک دسته‌بندی که زیردسته دارد، یک پوشه که پوشه دارد، یک نظر که پاسخ دارد. اگر داده تخت است، بازگشت فقط یک حلقه است که گران‌تر نوشته شده.
هر فراخوانی یک قاب روی پشته می‌گیرد و همان است که سقف را می‌سازد؛ چرایی‌اش در برنامه چطور یادش می‌ماند باید کجا برگردد است. بالا بردن آن سقف با sys.setrecursionlimit راه‌حل نیست و تقریبا همیشه به‌جای یک خطای تمیز، یک سقوط کامل مفسر می‌دهد. اگر عمق واقعی زیاد است، همان الگوریتم را با یک پشته دستی بنویسید: آخرین ورودی اول، اولین ورودی اول، و جای هرکدام.
دو نشانه که بازگشتتان غلط است
اول، فراخوانی بازگشتی که ورودی را کوچک‌تر نمی‌کند. اگر همان دیکشنری یا همان رشته را دوباره پاس می‌دهید، شرط پایان هیچ‌وقت نمی‌رسد هرچقدر هم درست نوشته شده باشد. هر فراخوانی باید ثابت کند که به پایان نزدیک‌تر شده.
دوم، شاخه‌ای که مقدار برگشتی را دور می‌ریزد. نوشتن hajm(v["zir"]) بدون اینکه در جمع بیاید یا برگردانده شود، خطایی است که هیچ پیامی ندارد و فقط عدد نهایی را کم می‌کند. در تابعی که خودش را صدا می‌زند، هر فراخوانی باید یا در محاسبه شرکت کند یا صریحا برگردانده شود.
جایی که کار گیر می‌کند، فاکتوریل است
در تقریبا هر دوره فارسی، بازگشت با فاکتوریل و فیبوناچی معرفی می‌شود، و هر دو مثال‌های بدی هستند: هر دو با یک حلقه ساده‌تر و سریع‌تر نوشته می‌شوند، پس چیزی که در ذهن می‌ماند این است که بازگشت یک راه پیچیده‌تر برای انجام کار حلقه است. آدم بعدا با یک درخت دسته‌بندی یا با یک پوشه تودرتو روبه‌رو می‌شود و اصلا به بازگشت فکر نمی‌کند، چون چیزی که یاد گرفته بود تزیینی به نظر می‌رسید. اولین بازگشتی که ارزش نوشتن دارد همان چیزی است که این صفحه نشان داد: پیمایش یک ساختار تودرتو.
ابزار، و سالی که این حرف درست است
در سال ۲۰۲۶، functools.lru_cache در کتابخانه استاندارد و رایگان است و جای نگه داشتن دستی یک دیکشنری از نتیجه‌ها را می‌گیرد؛ روی توابع بازگشتی که یک زیرمسئله را چند بار حل می‌کنند تفاوتش از یک ثانیه به یک صدم است. برای دیدن اینکه واقعا چند بار صدا زده شده، cProfile در همان کتابخانه ستون تعداد فراخوانی را می‌دهد و همان ستون است که تکرار را لو می‌دهد.
پرسش بعدی دقیقا همان است: وقتی یک زیرمسئله بارها حل می‌شود، چطور می‌شود جواب را نگه داشت به‌جای اینکه دوباره حساب شود، که به یاد سپردن زیرمسئله‌ها، به‌جای محاسبه دوباره است. و ساختاری که بیشترین بازگشت‌های واقعی روی آن نوشته می‌شود در سلسله‌مراتب، و گشتن در آن بدون خواندن همه‌اش است.