مساله ی برج های هانوی (towers of Hanoi) از مساله های معروف در زمینه ی اگوریتم های بازگشتی است که در آن تعدادی دیسک را باید ازمیله ای به میله ی دیگر منتقل کرد.

شرایط اولیه: ۳ میله که یکی از آنها حاوی تعدادی دیسک  است که از پایین به بالا از بزرگ به کوچک قرار گرفته اند.

مسآله: همه ی دیسک ها را باید به یک میله ی خالی منتقل کنید.

قوانین:

۱-هنگام حرکت دادن دیسکها هیچ دیسکی روی دیسک کوچکتر از خود قرار نگیرد.

۲-درهر بار حرکت دادن دیسک ها نمیتوان بیش از یک دیسک را منتقل کرد.

حل: فرض کنیم n دیسک داریم و میله ها را origin , middle , destination مینامیم که ابتدا دیسکها در origin قرار دارند وباید به destination منتقل شوند. فرض کنیم (H(n تابعی باشد که این کار را انجام میدهد n دیسک را به روش زیر منتقل میکنیم:

۱-با(H(n-1  ابتدا n-1 دیسک بالایی از میله ی origin را به middle منتقل میکنیم.

۲-آخرین دیسک موجود در origin را به destination منتقل میکنیم.

۳-با(H(n-1  درآخر n-1 دیسک موجود در میله ی origin را به destination منتقل میکنیم.

پس داریم:(H(n)=H(n-1)+1+H(n-1 یعنی H(n)=2H(n-1)+1

کد این مساله به زبان سی پلاس پلاس( ++C):

#include "stdafx.h"
#include <iostream>
using namespace std;
void hanoi(int disk, int or, int des)
{ 
        //or=origion, des=destination
	int mid=6-(or+des);
	if(disk==1)
        {
		cout<<or<<"->"<<des<<endl;
	}
        else
        {
		hanoi(disk-1, or, mid);
		cout<<or<<"->"<<des<<endl;
		hanoi(disk-1,mid , des);
	}
}
int main(void)
{
	int dno,or,des; //number of disks, origion, destination
	cout<<"\tHanoi towers, tower 1, tower 2, tower 3 (inputs are numbers 1,2 and 3): "<<endl<<endl;
	//avoiding possible mistakes while entering inputs by using do-while loops
        do
        {
		cout<<"Enter the number of disks: ";
		cin>>dno;
	}
        while(dno<1);
	do{
		cout<<"Enter the origion: ";
		cin>>or;
	}
        while(or>3 || or<1);
	do
        {
		cout<<"Enter the destination: ";
		cin>>des;
	}
        while(des>3 || des<1 || des==or);
	hanoi(dno,or,des);
	cin.get();
	return 0;
}

جالب است بدانیم که جواب تابع  بازگشتی در این مساله برابر است با: hanoi(n)=(2^n)-1 یعنی تابع به اندازه ی hanoi(n)=(2^n)-1 فراخوانی میشود, پس با انجام

همین تعداد حرکت دیسکها از origin  به destination  منتقل میشوند.