وقتی میخواین بازگشتی رو برای کسی توضیح بدین شاید اولین مثالی که به ذهن شما میرسه مسئله هانوی نباشه ولی قطعا یکی از مثال های معروف هست. اما شاید برای کسی که تازه میخواد این مفهوم رو یاد بگیره توضیح ساده ای وجود نداشته باشه.
مسئله هانوی دو تا قانون اصلی داره:
۱.در هر مرحله فقط مجاز به جابجایی یک دیسک هستیم.
۲.هیچ دیسکی با شعاع بزرگتر نباید روی دیسکی با شعاع کوچکتر قرار بگیره.
با رعایت این دو قانون باید بازی رو ادامه بدیم و با کمترین تعداد جابجایی n دیسک رو از استک مبدا با استفاده از استک کمکی٬ به استک مقصد ببریم.
در این پست میخوام به شکل ساده تری براتون توضیح بدم در مسیر حل این مسئله به روش recursive دقیقا چه اتفاقی میفته. میتونین از سایت mathisfun استفاده کنید و با استفاده از سه میله و n دیسک دلخواه حالت های مختلف رو امتحان کنید. اولین قدمی که در حل این سوال به فکرمون میرسه حل کردن به کمک اعداد کوچکه.
مثلا اگر فقط یک دیسک داشته باشیم راه حل ساده ست. کافیه این دیسک رو از استک مبدا به مقصد منتقل کنیم و تمام. اگر دو دیسک داشته باشیم چی؟ بذارین دیسک ها رو به ترتیب بزرگی شعاع٬ با عدد مشخص کنیم٬ به این ترتیب که کوچک ترین دیسک رو با عدد یک و بزرگ ترین دیسک رو با عدد n شماره گزاری کنیم. دیسک ۱ رو به میله کمکی میبریم. به این ترتیب در استک مبدا یک دیسک باقی میمونه و میتونیم به سادگی دیسک ۲ رو به مقصد منتقل کنیم. در آخرین قدم هم دیسک ۱ رو از کمکی به مقصد میبریم.
حالتی که سه دیسک داشته باشیم تعداد حرکت ها بیشتر میشه. در تصویر زیر هر مرحله رسم شده. به جابجایی هر دیسک در هر مرحله توجه کنید.
هم در حالتی که دو دیسک داریم و هم در حالتی که سه دیسک داریم در واقع تلاش میکنیم بزرگترین دیسک در مبدا تنها بشه چرا که وقتی به این مرحله برسیم٬ مثل وقتی که یک دیسک داریم میتونیم بزرگترین دیسک رو به مقصد منتقل کنیم. این مرحله یک ویژگی دیگه هم داره. n-1 دیسک در میله کمکی قرار میگیرند. ابتدا بزرگ ترین دیسک رو به مقصد منتقل میکنیم و بعد n-1 دیسکی که روی کمکی قرار گرفتند رو به مقصد میبریم.
در واقع این مسئله از سه قسمت اصلی تشکیل میشه :
حالا میتونیم همین سه خط رو به کد تبدیل کنیم. مادامی که میله مبدا یک دیسک نداره n-1 دیسک رو از مبدا به کمکی منتقل می کنیم. چرا n-1 ؟ چون میخوایم بزرگترین دیسک در مبدا تنها بشه تا به مقصد منتقل شه. بعد از این مرحله کافیه n-1 دیسک رو از کمکی به مقصد ببریم.
void T(char from, char to, char help, int n){
if (n == 1) {
cout << n << ' ' << from << ' ' << to << '\n';
return;
}
// first recursive call
T(from, help, to, n-1);
cout << n << ' ' << from << ' ' << to << '\n';
// second recursive call
T(help, to, from, n-1);
}
برای اینکه این کد و نحوه فراخوانی های بازگشتی واضح بشه با هم مسئله رو برای n=4 تریس میکنیم. از روی تصویر زیر قدم به قدم با هم پیش میریم. قبل از ادامه دقت کنید وقتی میخوایم مبدا و مقصد و کمکی رو در هر مرحله مشخص کنیم٬ برای مرحله n به مرحله n+1 توجه میکنیم. یعنی در مرحله n+1 چه ستونی مبدا، چه ستونی مقصد و کدوم کمکی هست. مثلا وقتی (T(2,a,c,b کال شده و میخوایم نسخه های n=1 رو بسازیم٬ مرجع فراخوانی n=2 میشه٬ که در اون کمکی b هست و چون ما میخوایم اولین فراخوانی بازگشتی رو بسازیم باید n-1 دیسک رو به استک کمکی ببریم. با دونستن این نکته ادامه ادامه میدیم.
اولین نسخه از فراخوانی متد (T(4,a,c,b هست که یعنی میخوایم ۴ دیسک رو از مبدا a به مقصد c با کمک b ببریم. به ترتیب:
این نسخه از فراخوانی متد در استک ساخته میشه. اول چک میکنه ایا تعداد دیسک ها برابر با یک شده. اگر نه باید اولین فراخوانی بازگشتی کال بشه. یعنی (T(3,a,b,c یا بهتر بگم n-1 دیسک رو از a ببر به b به کمک c.
خب این نسخه از متد هم ساخته میشه و دوباره متد خط به خط پیش میره تا میرسه به اولین فراخوانی بازگشتی. قراره یکی از تعداد دیسک ها کم بشه اما دقت کنید وقتی n=3 بود مبدا a و مقصد b بود. پس در اولین فراخوانی بازگشتی برای n=2 فراخوانی میشه: (T(2,a,c,b. باید دیسک ها رو از مبدا به کمکی ببریم یعنی از a به c به کمک b.
این نسخه هم اجرا میشه و چون هنوز تعداد دیسک های این فراخوانی برابر با یک نشده ادامه میدیم و میرسیم به فراخوانی بازگشتی اول. باز هم دقت کنید وقتی به این خط میرسیم در نسخه ای قرار داریم که میخواد دو دیسک رو از a به c ببره. در نتیجه این بار با چه مقادیری تابع فراخوانی میشه؟ بله درسته (T(1,a,b,c که به سادگی میگه n-1 دیسک رو از مبدا ببر به کمکی. مبدا کیه؟ در این مرحله a کمکی؟b
این نسخه هم متد رو فراخوانی میکنه. عالی شد n=1 هست و base case برقرار شد. پس مسئله برای (T(1,a,b,c حل شد و از استک پاپ میشه. نسخه ای که در استک زیر این فراخوانی قرار داشته: (T(2,a,c,b
این متد تا خطی که اولین فراخوانی بازگشتی رو انجام میده اجرا شده پس میره سراغ بقیه لاین ها. دستور بعدی چاپ مبدا و مقصد جابجایی انجام شده هست. یعنی دومین جابجایی که چاپ میشه برابر با a->c هست. بریم سراغ دومین فراخوانی بازگشتی در این نسخه. یکی از تعداد دیسک ها کم میکنیم و میشه یک دیسک. اما از کدوم ستون به کدوم ستون میریم. در این مرحله ابتدا دیسک ها رو از a به c بردیم حالا باید از c به مقصد ببریم. مقصد رو با مقصد اولیه که موقع اولین فراخوانی متد در نظر گرفتیم اشتباه نکنید. مرجع شما در این مرحله n=2 هست که میخواسته دو دیسک رو از a به c ببره به کمک b.
پس دومین فراخوانی بازگشتی باید n-1 دیسکی که از مبدا به کمکی رفته رو از کمکی به مقصد ببره. (سه مرحله کلی که برای حل سوال مشخص کردیم رو به یاد دارید؟) در نتیجه این فراخوانی هست T(1,b,c,a)
چون در این فراخوانی تعداد دیسک ها برابر با یک هست وارد شرط پایه میشیم و جابجایی چاپ میشه این زیرمسئله هم حل میشه. با حل شدن این استپ (T(2,a,c,bفراخوانی هم از استک پاپ میشه و روترین نسخه از فراخوانی ها که باقی مونده٬ (T(3,a,b,c هست. حالا شما ادامه مسیر رو با توضیحاتی که دادم تریس کنید و هم چنین مسئله رو برای n متفاوتی حل کنید.
پیشنهاد میکنم این مسئله رو به صورت غیربازگشتی هم حل کنید و اگر دوست داشتید در کامنت ها بگین که یک مقاله هم در این باره بنویسم.
