بازگشت و پشته

بیایید به توابع برگردیم و آنها را عمیق تر مطالعه کنیم.

اولین موضوع ما بازگشت خواهد بود.

اگر برای برنامه نویسی تازه کار نیستید ، احتمالاً آشنا است و می توانید از این فصل پرش کنید.

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

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

دو روش تفکر

برای شروع کار ساده - بگذارید یک تابع POW (X ، N) بنویسیم که X را به یک قدرت طبیعی N منتقل می کند. به عبارت دیگر ، x به خودی خود چند برابر می شود.

دو روش برای اجرای آن وجود دارد.

تفکر تکراری: حلقه برای:

تفکر بازگشتی: کار را ساده کنید و با خود تماس بگیرید:

لطفاً توجه داشته باشید که چگونه نوع بازگشتی اساساً متفاوت است.

هنگامی که POW (X ، N) خوانده می شود ، اعدام به دو شاخه تقسیم می شود:

1. اگر n == 1 ، پس همه چیز بی اهمیت است. به آن پایه بازگشت گفته می شود ، زیرا بلافاصله نتیجه آشکار را تولید می کند: POW (x ، 1) برابر با x است.
2. در غیر این صورت ، ما می توانیم POW (x ، n) را به عنوان x * pow (x ، n - 1) نشان دهیم. در ریاضیات ، x n = x * x n-1 می نویسد. این یک مرحله بازگشتی نامیده می شود: ما کار را به یک عمل ساده تر (ضرب توسط X) و یک تماس ساده تر از همان کار (POW با N پایین) تبدیل می کنیم. مراحل بعدی آن را بیشتر و بیشتر ساده می کند تا N به 1 برسد.

همچنین می توانیم بگوییم که POW به صورت بازگشتی خود را تا n == 1 فراخوانی می کند.

به عنوان مثال ، برای محاسبه POW (2 ، 4) نوع بازگشتی این مراحل را انجام می دهد:

1. POW (2 ، 4) = 2 * POW (2 ، 3)
2. POW (2 ، 3) = 2 * POW (2 ، 2)
3. POW (2 ، 2) = 2 * POW (2 ، 1)
4. POW (2 ، 1) = 2

بنابراین ، بازگشت ، یک تماس عملکردی را به یک ساده تر و سپس - حتی ساده تر و غیره - کاهش می دهد تا نتیجه آشکار شود.

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

در اینجا می توانیم با استفاده از اپراتور شرطی ، همان را بازنویسی کنیم؟به جای اینکه اگر POW (X ، N) را ترسو تر و هنوز هم بسیار خواندنی تر کنید:

حداکثر تعداد تماس های تو در تو (از جمله اولین مورد) عمق بازگشت نامیده می شود. در مورد ما ، دقیقاً n خواهد بود.

حداکثر عمق بازگشت توسط Engine JavaScript محدود است. ما می توانیم به 10000 متکی باشیم ، برخی از موتورها اجازه بیشتری می دهند ، اما احتمالاً 100000 برای اکثر آنها محدود نیست. بهینه سازی های اتوماتیک وجود دارد که به کاهش این امر کمک می کند ("بهینه سازی تماس های دم") ، اما آنها هنوز در همه جا پشتیبانی نمی شوند و فقط در موارد ساده کار می کنند.

این کار استفاده از بازگشت را محدود می کند ، اما هنوز هم بسیار گسترده است. بسیاری از کارها وجود دارد که روش بازگشتی فکر کد ساده تر را حفظ می کند ، آسانتر برای حفظ آن.

زمینه اعدام و پشته

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

اطلاعات مربوط به فرآیند اجرای یک تابع در حال اجرا در زمینه اجرای آن ذخیره می شود.

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

یک تماس عملکرد دقیقاً یک زمینه اجرای مرتبط با آن دارد.

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

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

بیایید ببینیم چه اتفاقی می افتد در طول تماس POW (2 ، 3).

POW (2 ، 3)

در ابتدای تماس POW (2 ، 3) زمینه اجرای متغیرها را ذخیره می کند: x = 2 ، n = 3 ، جریان اجرای در خط 1 عملکرد است.

ما می توانیم آن را به عنوان:

این زمانی است که عملکرد شروع به اجرای آن می کند. شرط n == 1 فال است ، بنابراین جریان به شاخه دوم IF ادامه می یابد:

متغیرها یکسان هستند ، اما خط تغییر می کند ، بنابراین زمینه اکنون است:

برای محاسبه X * POW (X ، N - 1) ، ما باید با استدلال های جدید POW (2 ، 2) یک زیرگروه POW را تهیه کنیم.

POW (2 ، 2)

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

در اینجا ما همان عملکرد عملکرد را می نامیم ، اما کاملاً مهم نیست. این روند برای همه توابع یکسان است:

1. زمینه فعلی در بالای پشته "به یاد می آورد".
2. زمینه جدید برای زیرمجموعه ایجاد شده است.
3. پس از اتمام زیرمجموعه - زمینه قبلی از پشته ظاهر می شود و اجرای آن همچنان ادامه دارد.

هنگامی که وارد Subcall Pow (2 ، 2) شدیم ، پشته زمینه است:

زمینه جدید اجرای فعلی در بالا (و جسورانه) قرار دارد و زمینه های قبلی به یادگار مانده در زیر است.

هنگامی که زیر آب را تمام می کنیم - می توان زمینه قبلی را از سر گرفت ، زیرا هم متغیرها و هم مکان دقیق کد را که در آن متوقف شده است نگه می دارد.

در اینجا در تصویر ما از کلمه "خط" استفاده می کنیم ، همانطور که در مثال ما فقط یک زیرمجموعه در خط وجود دارد ، اما به طور کلی یک خط کد ممکن است حاوی چندین زیرگروه باشد ، مانند POW (…) + POW (…) + چیزی که (…)واد

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

POW (2 ، 1)

این روند تکرار می شود: یک زیرگروه جدید در خط 5 ساخته شده است ، اکنون با آرگومان x = 2 ، n = 1.

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

اکنون 2 زمینه قدیمی وجود دارد و 1 در حال حاضر برای POW (2 ، 1) در حال اجرا هستند.

خروج

در حین اجرای POW (2 ، 1) ، بر خلاف قبل ، شرط n == 1 حقیقت است ، بنابراین اولین شاخه IF کار می کند:

دیگر تماس های تو در تو وجود ندارد ، بنابراین عملکرد به پایان می رسد و 2 را برمی گرداند.

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

اجرای POW (2 ، 2) از سر گرفته می شود. این نتیجه از Subcall POW (2 ، 1) دارد ، بنابراین می تواند ارزیابی X * POW (X ، N - 1) را به پایان برساند ، و بازگشت 4.

سپس زمینه قبلی ترمیم می شود:

پس از اتمام ، ما نتیجه POW (2 ، 3) = 8 داریم.

عمق بازگشت در این مورد: 3.

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

به نیازهای حافظه توجه داشته باشید. زمینه ها حافظه را می گیرند. در مورد ما ، افزایش به قدرت N در واقع به حافظه برای متن های N نیاز دارد ، برای تمام مقادیر پایین n.

یک الگوریتم مبتنی بر حلقه صرفه جویی در حافظه است:

POW تکراری از یک زمینه واحد در حال تغییر من است و منجر به روند می شود. نیازهای حافظه آن کوچک ، ثابت است و به n بستگی ندارد.

هرگونه بازگشت را می توان به عنوان یک حلقه بازنویسی کرد. نوع حلقه معمولاً می تواند مؤثرتر شود.

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

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

گذرگاه های بازگشتی

یکی دیگر از کاربردهای عالی بازگشت ، یک گذرگاه بازگشتی است.

تصور کنید ، ما یک شرکت داریم. ساختار کارکنان را می توان به عنوان یک شی ارائه کرد:

به عبارت دیگر ، یک شرکت دارای بخش هایی است.

یک بخش ممکن است مجموعه ای از کارمندان داشته باشد. به عنوان مثال ، بخش فروش دارای 2 کارمند است: جان و آلیس.

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

همچنین ممکن است که وقتی یک بخش فرعی رشد می کند ، به زیر مجموعه ها (یا تیم ها) تقسیم می شود.

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

حال بیایید بگوییم که ما می خواهیم یک تابع برای دریافت مجموع حقوق داشته باشیم. چطور می توانیم انجامش دهیم؟

یک رویکرد تکراری آسان نیست ، زیرا ساختار ساده نیست. ایده اول ممکن است ایجاد حلقه برای شرکت با Subloop تو در تو در بخش های سطح 1 باشد. اما پس از آن ما به زیر مجموعه های بیشتری برای تکرار کارکنان در بخش های سطح 2 مانند سایت ها نیاز داریم ... و سپس یک زیرمجموعه دیگر در داخل بخش های سطح 3 که ممکن است در آینده ظاهر شوند؟اگر 3-4 زیر مجموعه های تو در تو را در کد قرار دهیم تا یک شیء واحد را طی کنیم ، بسیار زشت می شود.

بیایید تلاوت را امتحان کنیم.

همانطور که می بینیم ، وقتی عملکرد ما یک بخش را جمع می کند ، دو مورد ممکن وجود دارد:

1. یا این یک بخش "ساده" با مجموعه ای از افراد است - پس می توانیم حقوق را در یک حلقه ساده جمع کنیم.
2. یا این یک شی با زیر بخش N است - سپس می توانیم تماس های بازگشتی برقرار کنیم تا مبلغ هر یک از زیرمجموعه ها را بدست آوریم و نتایج را ترکیب کنیم.

مورد اول پایه بازگشت ، مورد بی اهمیت است ، وقتی یک آرایه می گیریم.

مورد 2 وقتی که یک شی دریافت می کنیم ، مرحله بازگشتی است. یک کار پیچیده برای بخش های کوچکتر به زیرنویس تقسیم می شود. آنها ممکن است به نوبه خود دوباره تقسیم شوند ، اما دیر یا زود تقسیم در (1) به پایان می رسد.