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

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

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

#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