توجه! قبل از مطالعه‌ی این مطلب، جهت آشنایی و دریافت جزئیات بیشتر مسئله‌ی برج‌های هانوی را ببینید.

همان‌طور که می‌دانید، مسئله‌ی برج‌های هانوی به جابه‌جایی n مهره از یک میله به میله‌ی دیگر با استفاده از میله‌ی کمکی اشاره دارد. ما در این مطلب روش‌های مختلفی برای حل آن ارائه دادیم. یکی از این روش‌ها که با رویکرد تقسیم و غلبه طراحی شده، از یک تابع بازگشتی بنام Move() استفاده می‌کند. برنامه‌ی کامل آن در زیر آورده شده است:

1#include <iostream>
2using namespace std;
3void Move(int n, char srcPeg, char trgPeg, char tmpPeg) {
4  if (n == 1)
5    cout << "Move disk #1 from peg "
6      << srcPeg << " to " << trgPeg << endl;
7  else {
8    Move(n - 1, srcPeg, tmpPeg, trgPeg);
9    cout << "Move disk #" << n << " from peg "
10      << srcPeg << " to " << trgPeg << endl;
11    Move(n - 1, tmpPeg, trgPeg, srcPeg);
12  }
13}
14void main() {
15  int n;
16  cin >> n;
17  Move(n, 'A', 'C', 'B');
18}

تابع Move() در خط 17 از داخل تابع main() برای جابه‌جایی n مهره فراخوانی شده است. آرگومان‌های ارسالی به تابع به‌ترتیب عبارتند از تعداد مهره‌ها (اندازه‌ی مسئله)، برچسب میله‌ی مبداء (در اینجا A)، برچسب میله‌ی مقصد (C) و برچسب میله‌ی کمکی (B). این تابع بصورت بازگشتی طراحی شده و همان‌طور که ملاحظه می‌کنید برای هر تعداد مهره مانند n، دو بار در خطوط 8 و 11 با اندازه‌ی کوچکتر (n-1) بازفراخوانی می‌شود. ضمن این‌که مابین دو فراخوانی بازگشتی، نسبت به جابجایی مهره‌ی بزرگتر نیز اقدام می‌کند. بنابراین می‌توان گفت که زمان جابجایی n مهره عبارتست از مجموع زمان‌های دو بار جابجایی n-1 مهره به اضافه‌ی یک:

T(n) = 2 × T(n - 1) + 1

رابطه‌ی بازگشتی بالا را حل می‌کنیم. با تغییر n به n-1 داریم:

T(n - 1) = 2 × T(n - 2) + 1

با جایگذاری رابطه‌ی اخیر در رابطه‌ی قبلی داریم:

T(n) = 2 × [2 × T(n - 2) + 1] + 1 = 4 × T(n - 2) + 3

به همین ترتیب با تغییر n به n-2 داریم:

T(n - 2) = 4 × T(n - 4) + 3

با جایگذاری رابطه‌ی اخیر در رابطه‌ی قبلی داریم:

T(n) = 4 × [4 × T(n - 4) + 3] + 3 = 16 × T(n - 4) + 15

با ادامه‌ی این روند به الگوی زیر خواهیم رسید:

T(n) = 2ⁱ × T(n - i) + 2ⁱ - 1

با توجه به این‌که T(1) = 1، لذا با قرار دادن n - i = 1 ⇔ i = n - 1 خواهیم داشت:

T(n) = 2^n-1 × T(1) + 2^n-1 - 1 = 2^n-1 + 2^n-1 - 1
T(n) = 2 × 2^n-1 - 1 = 2ⁿ - 1

رابطه‌ی اخیر یعنی T(n) = 2ⁿ - 1 که رابطه‌ای مستقیم و غیربازگشتی است، نشان می‌دهد که پیچیدگی زمانی تابع T(n) از مرتبه‌ی O(2ⁿ) است. با وجود بالا بودن مرتبه‌ی زمانی آن هنوز بهترین الگوریتمی است که برای این مسئله وجود دارد.

برای آشنایی با نماد O (اُ بزرگ) و دریافت جزئیات بیشتر در مورد مرتبه‌ی زمانی، مطلب مربوط به تحلیل کارایی و محاسبه‌ی پیچیدگی زمانی الگوریتم‌ها را ببینید.