توی این قسمت میخوایم مروری بر مبحث مهم Recursive Function داشته باشیم.

قبل از شروع بحث در مورد Recursive میخوام یکم راجع به Stack صحبت کنیم…

Stack چیه؟

Stack یه دیتااستراکچر شبیه به List هست که میتونیم یه سری item داخلش بریزیم. مثل وقتی که از List از int ها داری و میتونی یه تعداد integer داخلش بریزی, به همین صورت میتونی یه Stack از int ها داشته باشی. ولی تفاوت اصلی و اساسی Stack با List در نحوه ی ورود و خروج ایتم هاست. توی یه لیست به هر ایتم یه index اختصاص داده میشه و بعدش میتونیم با استفاده از اون index ایتم مورد نظر رو از لیست دریافت کنیم. برای این منظور متد های مختلفی داریم, مثل Add که یه ایتم جدید رو به لیست اضافه میکنه و متد get یه یه شماره index میگیره و ایتم متناظر با اون index رو ریترن میکنه.

ولی توی Stack داستان یه خورده فرق میکنه. توی Stack دو تا Operation اصلی داریم:

• Push
• Pop

با استفاده از Push یه ایتم به Stack اضافه میکنیم و با استفاده از Pop یه ایتم ازش خارج میکنیم. ولی نکته ی مهم نحوه ی ورود و خروج ایتم هاست.

Stack رو میتونیم مثل یه لیوان در نظر بگیریم که وقتی یه ایتم جدید بهش اضافه میکنیم (Push), اون ایتم میره و روی ایتم های قبلی قرار میگیره و وقتی که میخوایم یه ایتمی رو خارج کنیم(pop), ایتمی که سر لیوان قرار داره زودتر از همه خارج میشه. پس اون ایتمی که اخر از همه اضافه شده زودتر هم خارج میشه.

بیا با یه مثال جلو بریم. اول کار یه Stack خالی رو در نظر میگیریم:

حالا یه ایتم جدید بهش اضافه میکنم (Push):

حالا یه ایتم دیگه بهش اضافه میکنم (Push):

میبینی که ایتم جدید روی ایتم قبلی قرار گرفت و الان اگه بخوام یه ایتم از Stack خارح کنم (Pop), اول Hasan خارج میشه:

و با Pop بعدی Ali خارج میشه:

به این مکانیزم میگن Last in First Out. یعنی اونی که دیرتر اومده تو, زودتر میره بیرون و این دقیقن برعکس Queue هست که مکانیزم First in First Out داره, یعنی اونی که زودتر اومده تو, زودتر هم بیرون میره.

Function Call Stack

وقتی که برنامه مون رو اجرا میکنیم, حافظه یا رم به دو بخش اصلی heap و stack تقسیم میشه (به علاوه بخش های دیگه). به طور خلاصه ابجکت هایی که میسازیم توی بخش heap ذخیره میشن که فعلن کاری باهاش نداریم و موضوع بحث ما نیست و به ازای هر فانکشنی که توی برنامه کال میشه یه ایتم به stack یا به اصطلاح call stack پوش میشه و تا وقتی که اون فانکشن در حال اجرا هست توی stack میمونه و وقتی اجرای اون فانکشن تموم شد از call stack پاپ میشه.

موضوع رو با یه مثال دنبال کنیم:

void main(List<String> arguments) {
  
  print("some thing");
 
}

توی کد بالا فقط و فقط یه دونه فانکشن با اسم main داریم که entry point برنامه هم هست. وقتی که برنامه هنوز به این فانکشن نرسیده, call stack خالی هست:

حالا وقتی برنامه به متد main میرسه, این متد به داخل call stack پوش میشه:

توی متد main متد print کال میشه و بنابراین در مرحله ی بعدی این متد هم به call stack پوش میشه:

متد print متن مورد نظر رو روی Console چاپ میکنه و کارش تموم میشه و بنابراین از call stack پاپ میشه:

بعد از اون که متد print از استک پاپ شد, دوباره کنترل برنامه میوفته دست متد main و ادامه ی متد main اجرا میشه تا به انتها برسه و اونم از استک پاپ بشه:

وقتی که call stack دوباره خالی شد, برنامه exit میشه و خاتمه پیدا میکنه.

حالا یه مثال دیگه رو ببینیم:

void main(List<String> arguments) {
  
  doSomething();
 
}


void doSomething()
{
  print("some thing");
}

خب طبق معمول اول کار کال استک خالی هست:

بعدش متد main وارد میشه و کنترل برنامه میوقت دست متد main.

نکته مهم

هر فانکشنی که سر استک باشه, کنترل برنامه دست همون فانکشن هست و اون فانکشن در حال اجرا هست. وقتی که اون فانکشن به انتها برسه, از استک پاپ میشه و کنترل برنامه دوباره میوفته دست caller.

متد main متد doSomething رو کال میکنه و در واقع متد main میشه caller و بنابراین متد doSomething به کال استک پوش میشه و کنترل برنامه میوفته دستش:

حالا داخل متد soSomething هم متد print کال میشه و کنترل برنامه میوفته دستش:

بعد از اینکه متد print کارشو انجام داد از استک پاپ میشه و کنترل برنامه مجددن میوفته دست متد doSomething که caller متد print بوده:

بعد از اون متد doSomething کنترل رو دست میگیره و کارشو ادامه میده و وقتی که کارش تموم شد از کال استک پاپ میشه و کنترل مجددن میوفته دست متد main که caller متد doSomething بوده:

و بعدش هم همین بلا سر main میاد و وقتی کال استک خالی شد برنامه exit میشه:

حالا بریم و یه مثال دیگه رو ببینیم:

void main(List<String> arguments) {
  
  print("Sum of 1 to 10 is : ${sumOfOneTo(10)}");
 
}


int sumOfOneTo(int end)
{
  var result = 0;
  for(var i = 0; i <= end; i++){
    result += i;
  }
  return result;
}

خب کد خیلی ساده هست.

یه متد به اسم sumOfOneTo داریم که یه ورودی به اسم end میگیره و جمع اعداد 1 تا عدد end رو محاسبه و ریترن میکنه. توی main هم این متد رو با ورودی 10 فراخونی کردیم. پس کال استک به ترتیب مراحل زیر رو طی میکنه: (پوش ها رو برای سادگی خلاصه کردم و مرحله به مرحله انجام ندادم)

حالا فانکشن sumOfOneTo رو به شکل زیر بازنویسی میکنم:

int sumOfOneTo(int end)
{
  if(end == 0)
    return 0;

  return end + sumOfOneTo(end - 1);
}

و یه بار دیگه این فانکشن رو توی main کال میکنم (البته این بار با ورودی 4):

void main(List<String> arguments) {
  
  print("Sum of 1 to 4 is : ${sumOfOneTo(4)}");
 
}

حالا بریم ببیینم که کال استک این دفعه چه شکلی میشه!!!

اول کار که خالیه و بعدش متد main و بعدش متد print داخلش قرار میگیرن و تا اینجا همه چیز مثل قبله و ساده هست:

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

حالا وقتی که این فانکشن به return میرسه:

return end + sumOfOneTo(end – 1)

که مقدار end برابر با 4 هست, پس این عبارت به شکل زیر در میاد:

return 4 + sumOfOneTo(3)

بنابراین این فانکشن خودش رو (ینی فانکشن sumOfOneTo رو) با عدد 3 کال میکنه و بنابراین یه دونه sumOfOneTo دوباره پوش میشه توی کال استک:

حالا دوباره وقتی به return میرسیم اینو داریم:

return end + sumOfOneTo(end – 1)

و چون ایندفعه end برابر با 3 هست:

return 3 + sumOfOneTo(2)

پس یه بار دیگه این فانکشن به کال استک پوش میشه, ولی این بار با ورودی 2:

و بازم مراحل قبل تکرار میشه:

return end + sumOfOneTo(end – 1)

که با جایگذاری 2 داریم:

return 2 + sumOfOneTo(1)

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

دوباره میرسیم به خط return :

return end + sumOfOneTo(end – 1)

و با جایگذاری عدد 1:

return 1 + sumOfOneTo(0)

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

int sumOfOneTo(int end)
{
  if(end == 0)
    return 0;

  return end + sumOfOneTo(end - 1);
}

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

حالا کنترل میوفته دست اون فانکشنی که با ورودی 1 کال شده بود. اون فانکشن توی کدوم خط گیر کرده بود؟

افرین توی این خط:

return 1 + sumOfOneTo(0)

در واقع به این خط که رسیده بود یه فانکشن دیگه رو کال کرده بود و کنترل رو داده بود به اون و منتظر مونده بود که اون فانکشن بهش جواب بده. حالا مقدارsumOfOneTo(0) مشخص شده و کنترل به این فاکشن برگشته و داریم:

return 1 + 0

پس این فانکشن هم مقدار 1 رو ریترن میکنه و از کال استک پاپ میشه:

توی مرحله ی بعدی کنترل میوفته دست فانکشنی که با ورودی 2 کال شده بود. همون طور که میدونی اون هم توی خط ریترن گیر کرده بود:

return 2 + sumOfOneTo(1)

و توی این خط یه فانکشن دیگه (sumOfOneTo(1)) رو کال کرده بود و کنترل رو بهش سپرده بود. حالا که جواب اون فانکشن اومده و از کال استک پاپ شده, کنترل مجددن میوفته دست این فانکشن و داریم:

return 2 + 1

حالا این فانکشن هم به انتهای خودش میرسه و مقدار 3 رو ریترن میکنه و از کال استک پاپ میشه:

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

return 3 + sumOfOneTo(2)

و حالا که فانکشن بالایی پاپ شده, یه بار دیگه کنترل رو دستش میگیره و :

return 3 + 3

مقدار 6 رو ریترن میکنه و از کال استک پاپ میشه:

حالا کنترل میوفته دست اولین فانکشن این زنجیره, یعنی اونی که با ورودی 4 کال شده بود و اون هم توی خط زیر گیر کرده بود:

return 4 + sumOfOneTo(3)

و با جایگذاری عدد 6 داریم:

return 4 + 6

بنابراین این فانکشن هم عدد 10 رو ریترن میکنه و پاپ میشه:

و حالا کنترل میوفته دست متد print و با استفاده از خروجی 10 پیام مورد نظر رو چاپ میکنه و ادامه ی ماجرا…

Recursive Function

به فانکشن sumOfOneTo میگیم Recursive Function که ترجمه ی فارسیش میشه بازگشتی, ولی ترجمش نکنی بهتره.

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

نکته ی مهم در مورد Recursive ها اینه که باید یه base condition داشته باشن تا یه جایی این پوش کردنه متوقف بشه. برای مثال یه بار دیگه کد رو نگاه کن:

int sumOfOneTo(int end)
{
  if(end == 0)
    return 0;

  return end + sumOfOneTo(end - 1);
}

اینجا base condition امون این هست:

if(end == 0)
    return 0;

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

اگه این اتفاق نیوفته و base condition نداشته باشیم, فانکشن ها پشت سر هم توی کال استک پوش میشن و از یه جایی به بعد گنجایش کال استک پر میشه و خطای Stack Overlow رو میگیری.

تمرین

یه فانکشن برای محاسبه ی فاکتوریل یه عدد بنویس و همین جوری تجزیه و تحلیلش کن!!!