جلسه پنجم /// جلسه پنجم /// توابع بازگشتی

برنامه هايی که تا کنون نوشتيم يک تابع، تابع ديگری را فراخوانی می کرد. در برنامه نويسی ممکن است نياز پيدا کنيم که تابعی خودش را به صورت مستقيم يا غير مستقيم فراخوانی کند. به چنين توابعی، توابع بازگشتی گفته می شود . ابتدا از ديد رياضياتی توابع بازگشتی را بررسی می کنيم. دنباله اعداد زير را در نظر بگيريد :

2 , 5 , 11 , 23 , ...

جمله پنجم دنباله اعداد فوق چه عددی می باشد؟ حدس شما چيست؟ اگر کمی دقت کنيد متوجه خواهيد شد که هر جمله از دنباله فوق برابر است با دو برابر جمله قبلی بعلاوه يک. پس جمله پنجم برابر است با 2*23+1=47 دنباله فوق را توسط فرمول زير نيز می توان مشخص کرد :

d₁ = 2
d_n = 2*d_n-1+1

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

d(1) = 2
d(n) = 2*d(n-1)+1

همانطور  که  در  تابع فوق  می  بينيد يک  حالت پايه  وجود دارد که  همان d(1)=2 می باشد و يکه حالت بازگشتی که تابع با يک واحد کمتر دوباره فراخوانی می شود d(n) = 2*d(n-1)+1 . توابع بازگشتی به طور کلی دارای يک يا چند حالت پايه و يک بخش بازگشتی می باشند. که معمولاً در بخش بازگشتی تابع با مقداری کمتر مجدداً فراخوانی می شود. تابع بازگشتی فوق به زبان ++C به صورت زير می باشد :

long int d(long int n)
{
   if (n == 1) 
      return 2;
   else 
      return 2*d(n-1)+1;
}

در زير برنامه ای می نويسيم تا با استفاده از تابع فوق 20 جمله اول دنباله مذکور را نمايش دهد.

#include <iostream.h>

long int d(long int);
int main( )
{ 
   for (int i=1;i<=20;i++)
     {
      cout<<d(i)<<"\t";
      if (i%5==0) cout<<endl;
     }

   return 0;
}

long int d(long int n)
{
   if (n == 1) 
      return 2;
   else 
      return 2*d(n-1)+1;
}

2       5       11      23      47      
95      191     383     767     1535
3071    6143    12287   24575   49151   
98303   196607  393215  786431  1572863

به عنوان مثال برنامه فوق جمله پنجم را به شيوه زير محاسبه می کند :

تابع، بازگشت را تا رسيدن به حالت پايه ادامه می دهد و به محض رسيدن به حالت پايه محاسبات بازگشتی پی در پی موجب رسيدن به جواب مورد نظر می شود.

مسئله برجهای هانوی (Towers of Hanoi)

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

برای نوشتن اين برنامه ، مسئله را بايد با ديد بازگشتی نگاه کنيم . انتقال n ديسک را به شيوه زير انجام می دهيم :

1- ابتدا n-1 ديسک را از ستون اول به ستون دوم به کمک ستون سوم منتقل کن.
2- ديسک آخر (بزرگترين ديسک) را از ستون اول به ستون سوم منتقل کن.
3- n-1 ديسک قرار گرفته در ستون دوم را به کمک ستون اول به ستون سوم منتقل کن.

مراحل انجام کار هنگام انتقال آخرين ديسک يعنی وقتی که n=1 می باشد، يعنی حالت پايه به اتمام می رسد. در حالت n=1 يک ديسک بدون کمک ستون کمکی به ستون ديگر منتقل می شود.

تابع بازگشتی مورد استفاده برای حل مسئله برجهای هانوی را با چهار آرگومان می نويسيم.

1- تعداد ديسکها
2- ستون مبدأ
3- ستون کمکی
4- ستون مقصد

تابع هانوی و برنامه ای که در آن اين تابع مورد استفاده قرار گرفته است به صورت زير می باشد :

#include <iostream.h>

int hanoi(int, char, char, char);

int main( )
{ int disks;

  cout<<"Moving disks form tower A to C."<<endl;
  cout<<"How many disks do you want to move?";
  cin>>disks;
  cout<<hanoi(disks,'A','B','C')<<endl;

  return 0;
}

int hanoi(int n, char first, char help, char second) 
{
  if (n == 1) {
    cout << "Disk " << n << " from tower " << first
         << " to tower " << second << endl;
  } 
  else {
     hanoi(n-1, first, second, help);
     cout << "Disk " << n << " from tower " << first
          << " to tower " << second << endl;
     hanoi(n-1, help, first, second);
  }
  return 0;
}

خروجی برنامه با فرض اينکه می خواهيم مراحل انتقال چهار ديسک را ببينيم به صورت زير می باشد :

Moving disks form tower A to C.
How many disks do you want to move?4
Disk 1 from tower A to tower B
Disk 2 from tower A to tower C
Disk 1 from tower B to tower C
Disk 3 from tower A to tower B
Disk 1 from tower C to tower A
Disk 2 from tower C to tower B
Disk 1 from tower A to tower B
Disk 4 from tower A to tower C
Disk 1 from tower B to tower C
Disk 2 from tower B to tower A
Disk 1 from tower C to tower A
Disk 3 from tower B to tower C
Disk 1 from tower A to tower B
Disk 2 from tower A to tower C
Disk 1 from tower B to tower C
0

روال فراخوانی تابع هانوی به صورت شکل زير می باشد:

جلسه پنجم /// درس چهارم /// پيش تعريف توابع

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

يک راه چاره برای اجتناب از نوشتن کد همه توابع قبل از استفاده آنها در تابع main يا ساير توابع وجود دارد. اين راهکار پيش تعريف توابع می باشد. پيش تعريف تابع به صورت زير می باشد:

 نوع آرگومانهای تابع )  نام تابع    نوع داده خروجی );

توجه داشته باشيد که پيش تعريف تابع شامل دستورات تابع نمی شود و تنها شامل نوع داده خروجی ، نام تابع و نوع آرگومانها می باشد و در پايان نياز به علامت (;) دارد. به عنوان مثال پيش تعريف تابع power2 در مبحث قبلی به صورت زير می باشد:

long int power2( int );

ويا پيش تعريف تابع maximum به صورت زير است :

int maximum( int, int, int );

در اينجا برنامه تابع maximum در مبحث قبلی را با روش پيش تعريف تابع باز نويسی می کنيم :

#include <iostream.h>

int maximum (int ,int,int);

int main ()
{
  int num1,num2,num3;

  cout << "Enter three numbers: ";
  cin >> num1>>num2>>num3;
  cout << "Max is :"
       << maximum(num1,num2,num3)<<endl;
  cout << "Max of 5,20,1 is "
       << maximum(5,20,1)<<endl;

  return 0;
}

int maximum (int x,int y, int z)
{
  int max=x;

  if (y>max)
      max=y;
  if (z>max)
      max=z;

  return max;
}

Enter three numbers: -5 20 150
Max is :150
Max of 5,20,1 is 20

همانطور که در برنامه می بينيد، تابع main قبل از تابع maximum نوشته شده است و اين امکانی است که پيش تعريف تابع maximum به ما داده است.

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