الگوریتم بازگشتی (Recursive) چیست؟ به همراه مثال و تمرین

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

برای مثال، می‌توانید یک تابع بازگشتی برای محاسبه فاکتوریل یک عدد بنویسید. در اینجا، تابع فاکتوریل برای محاسبه فاکتوریل عدد n، خود را با n-1 فراخوانی می‌کند تا به فاکتوریل عدد کوچکتری برسد، و سپس با ضرب آن به n، فاکتوریل n را محاسبه می‌کند.

مثال دیگری از الگوریتم بازگشتی

یک مثال دیگر از الگوریتم بازگشتی می‌تواند محاسبه توان یک عدد باشد. در این الگوریتم، می‌توانیم با تعریف یک تابع بازگشتی، توان یک عدد را به راحتی محاسبه کنیم. برای مثال، فرض کنید می‌خواهیم توان n اعداد صحیح a را محاسبه کنیم. در این صورت، تابع بازگشتی زیر را می‌توانیم تعریف کنیم:

def power(a, n):

    if n == 0:

        return 1

    elif n % 2 == 0:

        return power(a, n//2) * power(a, n//2)

    else:

        return power(a, n//2) * power(a, n//2) * a

در این تابع، در صورتی که توان n برابر با صفر باشد، مقدار ۱ برگردانده می‌شود. در غیر این صورت، اگر توان n فرد باشد، تابع دوباره خودش را با n-1 فراخوانی می‌کند تا توان را به صورت زوج درآورده و مقدار a را بیشتر کند. اگر توان n زوج باشد، تابع دوباره خودش را با n/2 فراخوانی می‌کند و مقدار a به توان n/2 را با استفاده از ضرب دوباره آن‌ها، محاسبه می‌کند. به صورت کلی، این الگوریتم به صورت بازگشتی توان عدد a را با استفاده از توان های نصف شده آن و بازگشتی محاسبه می‌کند.

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

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

در الگوریتم تکرارشونده، برای حل یک مسئله، از یک حلقه تکرار استفاده می‌شود و مسئله به صورت تکراری در هر مرحله حل می‌شود. در این حالت، مسئله به صورت تکرارشونده در هر مرحله حل می‌شود و نتیجه نهایی به دست می‌آید.

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

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

آیا پیچیدگی محاسباتی الگوریتم بازگشتی همیشه بیشتر از الگوریتم تکرارشونده است؟

خیر، پیچیدگی محاسباتی الگوریتم بازگشتی همیشه بیشتر از الگوریتم تکرارشونده نیست و بسته به مسئله‌ی مورد نظر و نحوه‌ی پیاده‌سازی الگوریتم، ممکن است در برخی موارد پیچیدگی محاسباتی الگوریتم بازگشتی کمتر از الگوریتم تکرارشونده باشد.

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

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

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

توضیح تکمیلی درباره‌ی نحوه‌ی پیاده‌سازی الگوریتم بازگشتی

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

سپس، باید دقت کرد که تابع بازگشتی به صورت نامحدود فراخوانی نشود. به عنوان مثال، در مسئله‌ی محاسبه‌ی عدد فیبوناچی با استفاده از الگوریتم بازگشتی، فراخوانی تابع برای مقادیر بزرگی از n ممکن است بسیار زمانبر باشد و حتی به مشکلات حافظه‌ای نیز برخورد کنیم. بنابراین، باید مراقب بود که تابع بازگشتی در هر مرحله به اندازه‌ی کافی کوچک شود تا به دست آوردن پاسخ نهایی برسیم.

همچنین، در برخی موارد، استفاده از حافظه‌ی موقت برای ذخیره‌ی مقادیر پاسخ می‌تواند به بهبود کارایی الگوریتم بازگشتی کمک کند. به عنوان مثال، در مسئله‌ی محاسبه‌ی عدد فیبوناچی، استفاده از یک لیست برای ذخیره‌ی مقادیر پاسخ در هر مرحله، می‌تواند به کاهش تعداد فراخوانی‌های تابع و بهبود کارایی الگوریتم کمک کند.

در نهایت، برای پیاده‌سازی الگوریتم بازگشتی، می‌توانیم از یک ساختار کنترل ترکیبی از شرط‌ها و حلقه‌ها استفاده کنیم تا به دست آوردن پاسخ نهایی برسیم. برای مثال، از شرط if-else و یا از حلقه‌ی for و while برای پیاده‌سازی الگوریتم بازگشتی استفاده می‌شود.

آیا همیشه استفاده از الگوریتم بازگشتی بهتر از الگوریتم‌های دیگر است؟

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

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

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

مثالی از یک مسئله‌ که الگوریتم تکرارشونده بهترین راه‌حل را ارائه کرده است

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

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

def power(x, n):

    result = 1

    while n > 0:

        if n % 2 == 1:

            result *= x

        x *= x

        n //= 2

    return result

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

آیا پیچیدگی محاسباتی الگوریتم بازگشتی همیشه بیشتر از الگوریتم‌های دیگر است؟

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

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

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

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

کاربرد الگوریتم بازگشتی چیست ؟

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

1.  محاسبات ریاضی: مسائلی مانند محاسبه توان، محاسبه فاکتوریل، محاسبه‌ی عدد فیبوناچی و ... با استفاده از الگوریتم بازگشتی حل می‌شوند.
2.  پردازش زبان‌های طبیعی: در پردازش زبان‌های طبیعی، ممکن است نیاز به پیدا کردن یک الگو در یک رشته داشته باشیم. الگوریتم بازگشتی می‌تواند در این حوزه مفید باشد.
3.  شبیه‌سازی و بازی‌های رایانه‌ای: در شبیه‌سازی و بازی‌های رایانه‌ای، اغلب نیاز به الگوریتم‌های بازگشتی برای شبیه‌سازی حرکات و محاسبه‌ی موقعیت آن‌ها وجود دارد.
4.  بررسی گراف و گرافیک رایانه‌ای: الگوریتم‌های بازگشتی در بررسی و پردازش گراف‌ها و همچنین در طراحی الگوریتم‌های گرافیکی کاربرد دارند.
5. هوش مصنوعی و یادگیری ماشین: در هوش مصنوعی و یادگیری ماشین، الگوریتم بازگشتی می‌تواند در پیاده‌سازی الگوریتم‌های یادگیری عمیق و شبکه‌های عصبی مصنوعی مورد استفاده قرار گیرد.

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

انواع بازگشت در الگوریتم بازگشتی

در الگوریتم بازگشتی، دو نوع بازگشت وجود دارد: بازگشت خطی و بازگشت غیرخطی.

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

def factorial(n):

    if n == 0:

        return 1

    else:

        return n * factorial(n-1)

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

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

def fib(n):

    if n == 0:

        return 0

    elif n == 1:

        return 1

    else:

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

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

با توجه به نوع بازگشت، می‌توان بهینه‌سازی‌های مختلفی در الگوریتم بازگشتی انجام داد. به عنوان مثال، در الگوریتم محاسبه‌ی عدد فیبوناچی، با استفاده از تکنیک حافظه‌ی نهان (memoization) می‌توان بازگشت غیرخطی را به بازگشت خطی تبدیل کرد و در نتیجه عملکرد الگوریتم را بهبود بخشید.

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

الگوریتم بازگشتی دنباله دار (Recursive Sequence)، الگوریتمی است که برای حل دنباله‌های بازگشتی استفاده می‌شود. این الگوریتم به صورت بازگشتی تعریف می‌شود و در هر مرحله، مقدار عناصر دنباله به صورت بازگشتی از مقادیر عناصر قبلی دنباله محاسبه می‌شوند.

:برای مثال، فرض کنید دنباله بازگشتی زیر داریم

a[0] = 1

a[1] = 1

a[n] = a[n-1] + 2*a[n-2]

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

def sequence(n):

    if n == 0:

        return 1

    elif n == 1:

        return 1

    else:

        return sequence(n-1) + 2*sequence(n-2)

در این تابع، با استفاده از بازگشتی، مقدار هر عنصر دنباله به صورت بازگشتی از مقادیر عناصر قبلی دنباله محاسبه می‌شود. برای مثال، برای محاسبه‌ی عنصر پنجم دنباله، تابع sequence برای محاسبه‌ی مقدار آن، به دو مرحله بازگشتی نیاز دارد:

sequence(5) = sequence(4) + 2*sequence(3)

            = (sequence(3) + 2*sequence(2)) + 2*(sequence(2) + 2*sequence(1))

            = (sequence(2) + 2*sequence(1)) + 2*(sequence(1) + 2*sequence(0)) + 2*(sequence(1) + 2*sequence(0))

            = (1 + 2*1) + 2*(1 + 2*1) + 2*(1 + 2*1)

            = 13

با استفاده از الگوریتم بازگشتی دنباله دار، می‌توان دنباله‌هایی با الگوهای مختلف را حل کرد. با این حال، در مواردی که طول دنباله بسیار بزرگ باشد، الگوریتم بازگشتی دنباله دار ممکن است به دلیل تعداد زیادی از فراخوانی‌های تابع، کارآیی پایینی داشته باشد. در چنین مواردی، بهتر است از روش‌های دیگری مانند حل با روش برنامه‌نویسی پویا (Dynamic Programming) استفاده کرد.