توابع بازگشتی

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

2 , 5 , 11 , 23 , ...

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

d1 = 2
dn = 2*dn-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

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