بازگشت ، بازگشت دم و ساختار داده های بازگشتی: شیرجه عمیق

مقدمه

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

بازگشت چیست؟ (و چرا خود را صدا می کند؟ 🧐)

در هسته اصلی آن ، بازگشت ، تابعی است که خود را برای حل نمونه های کوچکتر از یک مشکل فرا می خواند. این مانند یک عروسک لانه سازی روسی است – هر عروسک کوچکتر نشان دهنده یک زیرنویس کوچکتر است و در نهایت ، شما به یک مورد پایه برخورد می کنید ، که کوچکترین عروسک شما است (یا در صورت بازگشت ، “پرونده پایه” شما).

چگونه کار می کند؟

بیایید با یک مثال کلاسیک شروع کنیم: فاکتوریل. فاکتوریل شماره N (مشخص شده N!) محصول همه اعداد صحیح از 1 تا n است. بنابراین ،

n! = n * (n – 1) * (n – 2) * … * 1

در بازگشت ، این چیزی شبیه به:

FACTORIAL DEF (N):
اگر n == 0: # مورد پایه
بازگشت 1
دیگری:
بازگشت n * فاکتوریل (n – 1) # تماس بازگشتی

در این مثال ، فاکتوریل عملکرد خود را با یک آرگومان کوچکتر (N-1) فراخوانی می کند ، و ادامه می یابد تا N 0 شود ، جایی که به پرونده پایه برخورد می کند و شروع به بازگشت نتایج می کند.

مورد پایه و مورد بازگشتی: دوتایی پویا

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

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

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

قسمت تاریک بازگشت (مشکلات حافظه با نام مستعار)

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

بازگشت دم: ابرقهرمان بازگشت 🦸‍♂

اکنون ، دنیایی را تصور کنید که بازگشت به پشته مانند یک سرآشپز بیش از حد که غذاهای کثیف را جمع می کند ، به پشته تماس اضافه نمی کند. بازگشت به دم را وارد کنید. این جایی است که بازگشت بسیار کارآمد می شود و می تواند در یک فرآیند تکراری بهینه شود و باعث صرفه جویی در حافظه و پردازش قدرت شود.

چه چیزی باعث می شود بازگشت دم خاص باشد؟ 🤔

در بازگشت دم ، تماس بازگشتی آخرین چیزی است که قبل از بازگشت عملکرد نتیجه می گیرد. این امر به کامپایلرها یا مترجمان اجازه می دهد تا با استفاده از “استفاده مجدد” از قاب پشته عملکرد فعلی ، بازگشت را بهینه کنند ، که باعث می شود بازگشت بیشتر شبیه به تکرار باشد-پررنگ تر و حافظه گرسنه کمتر.

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

def factorial_tail (n ، acc = 1):
اگر n == 0:
بازگشت ACC
دیگری:
بازگشت factorial_tail (n – 1 ، acc * n)

به تفاوت توجه می کنید؟ ما در حال عبور از یک باتری (ACC) هستیم تا نتیجه را همانطور که می خواهیم پیگیری کنیم. این عملکرد خود را صدا می کند ، اما پس از تماس بازگشتی هیچ کاری باقی نمانده است – این تماس دم است. این یک عملکرد بازگشتی با یک استراتژی خروج روشن است! 🚪

چرا بازگشت دم بهتر است؟ 💡

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

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

ساختار داده های بازگشتی: مسابقه مناسب برای بازگشت

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

1. لیست های مرتبط

یک لیست پیوندی ساختاری است که در آن هر عنصر (گره) حاوی اشاره به گره بعدی است. بازگشتی است زیرا هر لیست در اصل “لیست” یک عنصر واحد است که به دنبال آن لیست دیگری است. در اینجا یک گذرگاه بازگشتی ساده از یک لیست مرتبط وجود دارد:

def traverse_linked_list (گره):
اگر گره هیچکدام نیست: # مورد پایه: لیست خالی
بازگشت
دیگری:
چاپ (node.value) # گره فعلی فرآیند
traverse_linked_list (node.next) # تماس بازگشتی

هر گره مانند یک مشکل کوچک است که به یک مشکل کوچکتر (گره بعدی) اشاره دارد. بنابراین ، به طور طبیعی ، بازگشت مانند یک دستکش مناسب است.

1. درختان باینری

درختان باینری ساختار داده دیگری است که ذاتاً بازگشتی است. هر گره دارای دو فرزند (چپ و راست) است و آن کودکان خود درخت هستند. اگر می خواهید یک درخت را طی کنید یا دستکاری کنید ، بازگشت طبیعی ترین راه برای پیشبرد است. در اینجا یک مسیر ساده جستجوی عمق اول (DFS) وجود دارد:

def traverse_tree (گره):
اگر گره هیچ کدام نیست:
بازگشت
چاپ (node.value) # گره فعلی را پردازش کنید
traverse_tree (node.left) # تماس بازگشتی در مورد کودک چپ
traverse_tree (node.right) # تماس بازگشتی در مورد کودک مناسب

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

1. نمودارها

نمودارها کمی پیچیده تر هستند ، اما بازگشت هنوز از طریق ✨ می درخشد. این که آیا شما در حال انجام جستجوی عمق اول (DFS) هستید یا اجزای متصل را کاوش می کنید ، بازگشت می تواند مسافر مانند Champ را انجام دهد. اگر می دانید که چگونه می توانید از طریق گذرگاه های بازگشتی درختان را کنترل کنید ، نمودار نمودار خیلی عقب نیست.

چرا ساختار داده های بازگشتی بسیار دوستانه است؟ 🤷‍♂

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

پایان

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

بنابراین ، دفعه بعد که با مشکلی روبرو شدید که به نظر می رسد برای حل یک حلقه بسیار پیچیده است ، از خود بپرسید: “آیا می توانم این را به صورت بازگشتی بشکنم؟” و اگر جواب “بله” است ، پس می خواهید وارد دنیای بازگشت فوق العاده ، بی نهایت (اما نه خیلی نامتناهی) شوید-جایی که هر تماس فقط یک لایه دیگر از خوبی های حل مسئله است. برنامه نویسی مبارک! 👨‍💻👩‍💻