پشته فراخوانی

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

تابع‌های بازگشتی از ساختاری به نام پشته فراخوانی (Call Stack) استفاده می‌کنند. پشته فراخوانی ساختمان داده‌ای برای فراخوانی توابع است. برای فهم بهتر لازم است ابتدا تعریفِ پشته (stack) را بدانیم.

پشته

پشته (stack) یک ساختار برای ذخیره اطلاعات است. فرض کنید یک قوطی دارید که در آن اشیاء خود را قرار می‌دهید. فرض کنید ابتدا یک مداد سپس یک پاک‌کن و سپس یک توپ می‌اندازید. این وسایل به‌ترتیب روی هم قرار می‌گیرند، به‌طوری که اگر بخواهید پاک‌کن خود را بردارید، باید ابتدا توپ را بردارید و سپس به پاک‌کن دسترسی پیدا کنید. به عبارتی شما هربار تنها می‌توانید چیزی را روی همه‌ی داده‌های قبلی در قوطی بگذارید یا اینکه چیزی که بالاتر از همه در قوطی هست را بردارید.

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

در واقع برای برداشتن از پشته، شما هربار آخرین چیزی که گذاشته شده و هنوز برداشته نشده را می‌توانید بردارید. در مورد این ساختمان‌داده (داده‌ساختار یا data structure) در بخش ساختمان‌داده مفصل توضیح داده‌شده‌است.

عملکرد پشته فراخوانی

وقتی برنامه یک تابع را صدا می‌زند؛ تابعی که صدا زده شده به بالای Call Stack اضافه می‌شود و وقتی از تابعی‌ خارج می‌شویم عنصر بالای Call Stack (آخرین تابع پشته) را حذف می‌کنیم. این‌گونه همیشه تابعی که در آن هستیم در بالای Call Stack است؛ یعنی وقتی از یک تابع خارج شدیم و تابع بالا پشته را حذف کردیم در واقع آن تابع همان تابعی بوده است که از آن خارج شدیم.

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

نکات مهم در پایتون

در زبان پایتون بر روی تعداد اعضای Call Stack محدودیت وجود دارد. شما می‌توانید با استفاده از دو خط زیر، این محدودیت را بیشتر کنید:

import sys sys.setrecursionlimit(10**6)

این دستور محدودیت recursion یا همان اندازه‌ی Call Stack را به عدد ۱,۰۰۰,۰۰۰ تغییر می‌دهد که با توجه به سؤال می‌توانید مقدار ۱,۰۰۰,۰۰۰ را تغییر دهید.

sys.setrecursionlimit(*limit*)

برای اطلاعات بیشتر به این‌ پیوند مراجعه کنید.

توجه کنید که این تابع در زبان «pypy» کارایی ندارد و در سؤالاتی که نیاز به تابع بازگشتی یا مواردی مشابه دارند، پیشنهاد می‌شود کدتان را به زبان‌های python 3.8 و python 2 ارسال کنید.