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

مقدمه

در حین برنامه نویسی زمانی که می خواهیم بخشی از کد که کار مشخصی انجام می دهد را بارها تکرار کنیم، معمولاً به حلقه های for و while فکر می کنیم. این حلقه ها به ما کمک می کنند تا امکان تکرار کاری روی یک لیست یا مجموعه و یا تا رسیدن به شرایط خاصی را داشته باشیم.

با این حال، ساختار دیگری برای تکرار یک کار هم وجود دارد که اندکی متفاوت از حلقه هاست. با صدا زدن یک تابع درون خودش، مثلاً برای حل بخش کوچک تری از همان مسئله، ما در واقع داریم عملی بازگشتی انجام می دهیم.

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

یک مثال ساده تر و انسانی تر، عملکرد ما حین خوردن یک پیتزاست. شما شروع به تقسیم پیتزا از وسط می کنید و هر دفعه آن را از وسط به دو نیمه تقسیم می کنید. در ضمن هر بار هم بررسی می کنید که آیا اندازه فعلی به کوچکی یک لقمه شده است یا نه.

تابع بازگشتی چیست؟

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

به طور کلی می توان گفت که تابع بازگشتی دو بخش اصلی دارد:

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

بیایید یک مثال کوچک ببینیم تا این دو بخش را در عمل ببینیم:

# Assume that remaining is a positive integer
def hi_recursive(remaining):
    # The base case
    if remaining == 0:
        return
    print('hi')

    # Call to function, with a reduced remaining count
    hi_recursive(remaining - 1)

اینجا حالت پایه برای ما زمانی اتفاق می افتد که متغیر remaining برابر با صفر شود. به این صورت که این متغیر تعداد رشته های “hi” که باید چاپ شوند را مشخص می کند. در صورتی که حالت پایه رخ دهد، تابع فقط به فراخوانی قبل باز می گردد و چیز خاصی چاپ نمی کند.

همانطور که می بینید، بعد از دستور print ما مجدداً تابع hi_recursive را صدا می زنیم، اما این بار آرگومان آن یکی کمتر می شود.

این خیلی مهم است که شما فراخوانی تکراری و بازگشتی را با همان ورودی یا همان مسئله فعلی انجام ندهید و ورودی را تغییر دهید. وگرنه در تکراری بی نهایت گیر خواهید کرد و هیچ موقع حالت پایه یا پایانی اتفاق نخواهد افتاد.

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

• اولاً مشابه نباشد و تغییر کرده باشد،
• دوماً این تغییر به سمت نزدیک شدن به حالت پایه پیش برود تا بتوان اطمینان حاصل کرد که اجراهای بازگشتی به تکرار بی نهایت دچار نشود.

بیایید نگاهی به زنجیره اجرای بازگشتی تابع بالا با ورودی ۳ داشته باشیم.

هر بار پس از اینکه تابع رشته “hi” را چاپ می کند، خودش را با مقدار یکی کمتر از remaining فعلی، دوباره فراخوانی می کند تا اینکه بالاخره مقدار آرگومان به صفر برسد. در مقدار صفر، با دستور return تابع به فراخوانی قبلی بر می گردد. این فراخوانی ها هم به طور زنجیره ای به اولین مرحله باز می گردند.

چرا حلقه به جای بازگشتی استفاده نکنیم؟

همه این کارهای تکراری را می توان با همان حلقه ها هم انجام داد. اما راستش را که بخواهید، یک سری مسائل هستند که با راه حل تابع بازگشتی راحت تر حل می شوند.

یک استفاده معمول از بازگشتی ها، پیمایش درخت و گراف است:

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

 

ترکیب بازگشتی با درخت ها، به ما کمک می کند تا پردازش/پیمایش کل درخت را با پردازش جداگانه بخش های مختلف آن تکمیل کنیم و به پایان برسانیم.

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

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

ما سعی می کنیم با تعدادی مثال همین دید ساده را به کار بگیریم و چند تابع بازگشتی بنویسیم تا سرآغازی برای تمرینات شخصی شما باشد.

تابع بازگشتی مجموع اعداد داخل لیست

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

تابع بازگشتی مجموع اعضای لیست به صورت زیر می شود:

def sum_recursive(nums):
    if len(nums) == 0:
        return 0

    last_num = nums.pop()
    return last_num + sum_recursive(nums)

حالت پایه و پایانی این تابع بازگشتی، مواجه شدن با لیست خالی است. دقت کنید که هر بار ما با pop کردن لیست، در واقع آخرین عضو آن را می گیریم و از لیست حذف می کنیم. پس هر بار برای فراخوانی بعدی یکی از اندازه لیست کم شده و به سوی خالی شدن پیش می رود.

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

تابع بازگشتی محاسبه فاکتوریل

شما حتماً می دانید که تعریف فاکتوریل در ریاضیات چیست. فاکتوریل یک عدد، ضرب آن عدد در همه اعداد حسابی پیشین آن عدد است. مثال زیر را هم ببینید که از تعریف بگذریم و به کد برسیم:

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

حالا بیایید با در نظر گرفتن بخش های اصلی بازگشتی، یک تابع بازگشتی در پایتون بنویسیم که فاکتوریل یک عدد را حساب کند:

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

همانطور که در تعریف دیدید، همه اعداد حسابی پیشین هم باید در ضرب شرکت کنند. پس حالت پایه ما رسیدن به یک و صفر است که فاکتوریل هر دوی آن ها طبق تعریف برابر با ۱ است.

تابع بازگشتی دنباله فیبوناچی

یک دنباله فیبوناچی دنباله ای است که هر عدد از جمع دو عدد ماقبل خود ایجاد شده است. فرض این است که دنباله از صفر و یک شروع می شود و این دو مقدار دو جمله اول دنباله هستند. پس به طور مثال فیبوناچی سوم (با ایندکس ۲) برابر است جمع دو جمله قبلی یعنی ۱ = ۱ + ۰ .

بیایید ببینیم که دنباله فیبوناچی برای هر شماره به چه ترتیب است:

Integers:   0, 1, 2, 3, 4, 5, 6, 7
    Fibonacci:  0, 1, 1, 2, 3, 5, 8, 13

ما به سادگی می توانیم یک تابع بازگشتی پایتون پیاده سازی کنیم که با گرفتن شماره ایندکس جمله، مقدار آن را در دنباله فیبوناچی محاسبه کند:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

همانطور که می بینید حالت پایه، رسیدن به جملات اول و دوم (با ایندکس ۰ و ۱) است.

حالا یک پیاده سازی دیگر از همین کد را در نظر بگیرید که با حلقه for پیاده شده و بازگشتی نیست:

def fibonacci_iterative(n):
    if n <= 1:
        return n

    a = 0
    b = 1
    for i in range(n):
        temp = a
        a = b
        b = b + temp
    return a

در کد بالا می بینیم که نوشته شده اگر عدد ورودی شماره جمله، کوچکتر مساوی ۱ بود، خودش می شود. یعنی جمله ۰ برابر ۰ و جمله ۱ هم برابر ۱ است که این دقیقاً طبق فرض دنباله فیبوناچی است.

پس از آن در حلقه به طور مداوم دو جمله پیشین دنباله روی هم جمع می شوند تا بالاخره به شماره جمله خواسته شده برسیم و اجرای for تمام شود.

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

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

جمع بندی

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

همیشه در نظر داشته باشید که باید ورودی های فراخوانی های بازگشتی به تدریج به سمت نزدیک شدن به حالت پایه پیش بروند تا بتوان پایانی برای اجراهای تودرتوی بازگشتی متصور شد.

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

مطالعه بیشتر

ما در اوپن مایند، مطالب آموزشی زیادی داریم که استفاده از شیوه بازگشتی در مسائل مختلف را آموزش می دهند؛ از الگوریتم مرتب سازی حبابی یا Bubble-sort و برنامه بازگشتی محاسبه دترمینان ماتریس گرفته تا حل مسئله خورد کردن پول به دو روش و آشنایی با مفهوم برنامه ریزی پویا از طریق مثال .

شما می توانید تمام مطالب آموزشی با برچسب بازگشتی را در این صفحه ببینید : مطالب آموزشی بازگشتی .

در انتها، این مطلب با استفاده این مطلب “Understanding Recursive Functions with Python” نگارش شده است.

نوشته درک عملکرد تابع بازگشتی با پایتون اولین بار در اوپن مایند. پدیدار شد.