Recursion در پایتون چیست؟

Recursion یا «بازگشت» یکی از مفاهیم مهم برنامه‌نویسی است که در آن یک تابع، خودش را دوباره فراخوانی می‌کند. این روش برای حل بعضی از مسائل که ساختار تکرارشونده یا تو در تو دارند، بسیار کاربردی است.

در این درس یاد می‌گیریم تابع بازگشتی چیست، چرا به Base Case نیاز داریم، چگونه از Recursion استفاده کنیم و چه تفاوتی بین Recursion و حلقه‌ها وجود دارد.

Recursion در پایتون چیست؟

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

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

یک مثال ساده از تابع بازگشتی

def countdown(n):

    if n == 0:
        print("پایان")
        return

    print(n)
    countdown(n - 1)


countdown(5)

خروجی:

5
4
3
2
1
پایان

در این مثال تابع countdown() خودش را با مقدار کوچک‌تر فراخوانی می‌کند تا در نهایت به صفر برسد.

Base Case چیست؟

Base Case یا «شرط پایه» شرایطی است که باعث می‌شود تابع بازگشتی دیگر خودش را فراخوانی نکند.

def countdown(n):

    if n == 0:
        return

    print(n)
    countdown(n - 1)

در این مثال:

• n == 0 شرط پایه است.
• وقتی این شرط برقرار شود، تابع متوقف می‌شود.

Recursive Case چیست؟

بخشی از تابع که باعث فراخوانی دوباره خودش می‌شود، Recursive Case نام دارد.

def countdown(n):

    if n == 0:
        return

    print(n)

    # Recursive Case
    countdown(n - 1)

در اینجا دستور countdown(n - 1) همان بخش بازگشتی است.

ساختار کلی یک تابع بازگشتی

def function(value):

    if base_condition:
        return result

    return function(smaller_value)

یک تابع بازگشتی معمولاً دو بخش مهم دارد:

1. شرط پایه یا Base Case
2. فراخوانی دوباره تابع یا Recursive Case

محاسبه فاکتوریل با Recursion

فاکتوریل یکی از مثال‌های معروف برای یادگیری Recursion است. فاکتوریل عدد n به شکل زیر تعریف می‌شود:

n! = n × (n-1) × (n-2) × ... × 1

برای مثال:

5! = 5 × 4 × 3 × 2 × 1 = 120

پیاده‌سازی بازگشتی:

def factorial(n):

    if n == 0 or n == 1:
        return 1

    return n * factorial(n - 1)


print(factorial(5))

خروجی:

120

نحوه اجرای factorial

اگر factorial(5) را اجرا کنیم، تابع به شکل مفهومی مراحل زیر را طی می‌کند:

factorial(5)
5 × factorial(4)
5 × 4 × factorial(3)
5 × 4 × 3 × factorial(2)
5 × 4 × 3 × 2 × factorial(1)
5 × 4 × 3 × 2 × 1

= 120

محاسبه مجموع اعداد با Recursion

می‌توانیم از Recursion برای محاسبه مجموع اعداد از 1 تا n نیز استفاده کنیم.

def total(n):

    if n == 0:
        return 0

    return n + total(n - 1)


print(total(5))

خروجی:

15

Fibonacci با Recursion

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

در این دنباله هر عدد از مجموع دو عدد قبلی به دست می‌آید.

def fibonacci(n):

    if n <= 1:
        return n

    return fibonacci(n - 1) + fibonacci(n - 2)


for i in range(10):
    print(fibonacci(i), end=" ")

خروجی:

0 1 1 2 3 5 8 13 21 34

Recursion و Call Stack

هر بار که یک تابع فراخوانی می‌شود، اطلاعات مربوط به اجرای آن در حافظه نگهداری می‌شود تا بعد از پایان تابع بتواند ادامه پیدا کند. در توابع بازگشتی، این فراخوانی‌ها می‌توانند چندین لایه ایجاد کنند.

def count(n):

    if n == 0:
        return

    print(n)
    count(n - 1)


count(3)

می‌توان اجرای آن را به صورت ساده این‌گونه تصور کرد:

count(3)
   ↓
count(2)
   ↓
count(1)
   ↓
count(0)
   ↓
return

پس از رسیدن به شرط پایه، فراخوانی‌ها یکی‌یکی برمی‌گردند.

خطای RecursionError چیست؟

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

def endless():

    endless()


endless()

در این مثال هیچ شرطی برای توقف وجود ندارد.

Recursion در مقایسه با Loop

بسیاری از مسائل بازگشتی را می‌توان با حلقه‌هایی مانند for و while نیز حل کرد.

مثال: فاکتوریل با Loop

همان مسئله فاکتوریل را می‌توان بدون Recursion نیز حل کرد:

def factorial(n):

    result = 1

    for i in range(1, n + 1):
        result *= i

    return result


print(factorial(5))

هر دو روش می‌توانند جواب یکسانی تولید کنند؛ انتخاب روش به ساختار مسئله و شرایط برنامه بستگی دارد.

چه زمانی از Recursion استفاده کنیم؟

Recursion در بعضی مسائل بسیار طبیعی و خوانا است؛ مخصوصاً مسائلی که ساختار آن‌ها خودشان را تکرار می‌کنند.

• کار با ساختارهای درختی
• بررسی پوشه‌ها و زیرپوشه‌ها
• الگوریتم‌های جستجو
• مسائل Divide and Conquer
• برخی الگوریتم‌های گراف
• حل مسائل ترکیبی و بازگشتی

مثال ساده برای ساختار تو در تو

یکی از کاربردهای مهم Recursion زمانی است که داده‌ها ساختار تو در تو داشته باشند.

def print_numbers(numbers):

    for item in numbers:

        if isinstance(item, list):
            print_numbers(item)
        else:
            print(item)


data = [1, [2, 3], [4, [5, 6]]]

print_numbers(data)

خروجی:

1
2
3
4
5
6

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

اشتباهات رایج در Recursion

• نداشتن Base Case
• رسیدن ندادن ورودی به شرط توقف
• فراخوانی بیش از حد تابع
• استفاده از Recursion برای مسئله‌ای که Loop ساده‌تر است
• نادیده گرفتن مصرف حافظه Stack
• استفاده از پیاده‌سازی بازگشتی ناکارآمد برای مسائل بزرگ

نکته مهم درباره کارایی Recursion

بازگشتی بودن یک الگوریتم لزوماً به معنی سریع‌تر بودن آن نیست. در بعضی مسائل، Recursion می‌تواند فراخوانی‌های زیادی ایجاد کند.

برای مثال، نسخه ساده Fibonacci که بالاتر دیدیم، بعضی محاسبات را چندین بار تکرار می‌کند.

در مسائل واقعی می‌توان از روش‌هایی مانند Memoization یا برنامه‌نویسی پویا برای کاهش محاسبات تکراری استفاده کرد.

تمرین ۱: شمارش معکوس

پاسخ تمرین ۱

def countdown(n):

    if n < 0:
        return

    print(n)

    countdown(n - 1)


countdown(5)

تمرین ۲: جمع اعداد

پاسخ تمرین ۲

def total(n):

    if n <= 0:
        return 0

    return n + total(n - 1)


print(total(10))

تمرین ۳: توان یک عدد

پاسخ تمرین ۳

def power(base, exponent):

    if exponent == 0:
        return 1

    return base * power(base, exponent - 1)


print(power(2, 4))

خروجی:

16

جمع‌بندی Recursion

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

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

• Base Case: شرایط توقف
• Recursive Case: فراخوانی دوباره تابع

Recursion برای بعضی مسائل مانند ساختارهای درختی، داده‌های تو در تو و برخی الگوریتم‌ها بسیار مفید است. با این حال، برای هر مسئله‌ای بهترین انتخاب نیست و گاهی استفاده از Loop ساده‌تر و کم‌هزینه‌تر است.

سؤالات متداول

Recursion در پایتون چیست؟

Recursion روشی است که در آن یک تابع در حین اجرای خودش، دوباره همان تابع را فراخوانی می‌کند.

Base Case چیست؟

Base Case شرطی است که باعث می‌شود تابع بازگشتی متوقف شود و دیگر خودش را فراخوانی نکند.

اگر Base Case نداشته باشیم چه اتفاقی می‌افتد؟

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

آیا Recursion بهتر از Loop است؟

پاسخ به نوع مسئله بستگی دارد. برخی مسائل با Recursion ساده‌تر بیان می‌شوند و برخی مسائل با Loop مناسب‌تر هستند.

آیا Recursion حافظه بیشتری مصرف می‌کند؟

فراخوانی‌های بازگشتی در Stack نگهداری می‌شوند؛ بنابراین Recursion عمیق می‌تواند مصرف Stack را افزایش دهد.

Recursion در چه پروژه‌هایی کاربرد دارد؟

از Recursion می‌توان در الگوریتم‌های جستجو، ساختارهای درختی، پردازش داده‌های تو در تو و بعضی الگوریتم‌های Divide and Conquer استفاده کرد.

مطالب مرتبط