آموزش توابع بازگشتی (Recursion) در پایتون

سطح مقدماتی (Beginner Level)

مفهوم بازگشت (Recursion) در برنامه‌نویسی به حالتی گفته می‌شود که یک تابع، خودش را فراخوانی کند. این تکنیک روشی قدرتمند برای شکستن مسائل بزرگ به زیرمسائل کوچک‌تر و مشابه است.

هر تابع بازگشتی باید دو بخش اصلی داشته باشد تا در یک حلقه بی‌نهایت گرفتار نشود:

1. شرط توقف (Base Case): شرایطی که در آن تابع دیگر خودش را صدا نمی‌زند و یک مقدار برمی‌گرداند.
2. گام بازگشتی (Recursive Step): بخشی که تابع با ورودی‌های متفاوت (معمولاً کوچک‌تر) خودش را صدا می‌زند تا به شرط توقف نزدیک شود.

مثال اول: شمارش معکوس ساده

در این مثال، یک تابع بازگشتی می‌نویسیم که از یک عدد شروع کرده و تا صفر می‌شمارد.

مثال دوم: محاسبه فاکتوریل

فاکتوریل عدد $n$ (نماد $n!$) برابر است با ضرب عدد $n$ در فاکتوریل $n-1$. این یک تعریف کلاسیک بازگشتی است. $5! = 5 \times 4 \times 3 \times 2 \times 1$

مثال سوم: ساختار اشتباه (بدون شرط توقف)

اگر شرط توقف را فراموش کنید، برنامه دچار خطای RecursionError می‌شود. کد زیر صرفاً برای نمایش ساختار است و نباید اجرا شود چون خطا می‌دهد.

# Example 3: Infinite Recursion (Static - Don't run this without limits)
def run_forever():
    print("Running...")
    run_forever()  # No base case! infinite loop till stack overflow

سطح پیشرفته (Professional Level)

در سطح حرفه‌ای، باید با نحوه مدیریت حافظه در بازگشت (Call Stack)، محدودیت‌های پایتون و روش‌های بهینه‌سازی مانند Memoization آشنا شوید.

پشته فراخوانی (Call Stack) و محدودیت‌ها

هر بار که یک تابع بازگشتی صدا زده می‌شود، یک "قاب" (Frame) جدید در حافظه (Stack) ایجاد می‌شود تا متغیرهای آن مرحله را نگه دارد. پایتون برای جلوگیری از پر شدن حافظه، محدودیتی برای عمق بازگشت دارد (معمولاً ۱۰۰۰).

شما می‌توانید با ماژول sys این محدودیت را بررسی یا تغییر دهید.

بهینه‌سازی با Memoization (کش کردن نتایج)

یکی از مشکلات بازگشت در الگوریتم‌هایی مثل فیبوناچی، محاسبات تکراری زیاد است. برای حل این مشکل از تکنیک Memoization استفاده می‌کنیم. در پایتون دکوریتور lru_cache از ماژول functools این کار را به صورت خودکار انجام می‌دهد.

مثال بدون بهینه‌سازی (کند):

# Static snippet showing naive logic
def fib_naive(n):
    if n < 2: return n
    return fib_naive(n-1) + fib_naive(n-2)
# Calculating fib_naive(35) takes noticeable time

مثال بهینه شده (سریع):

در اینجا نتایج فراخوانی‌های قبلی ذخیره می‌شوند تا دوباره محاسبه نشوند.

پیمایش ساختارهای تو در تو (Nested Structures)

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