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

[mononok]

سلام
من برنامه ورابطه ی برنج هانوی را دارم و خودم از روی شکل می توانم نحوه ی کار آن را بفهمم مثلا برای تشکیل برج 4 تایی باید اول برج 3 تایی تشکیل شود و برای تشکیل برج 3 تایی باید 2 تایی اول تشکیل شود تا 1 و بعد 4 آزاد می شود و به ستون مورد نظر می رود و بعد دوباره همان 3 تایی روی ستونی که 4 هست دوباره تشکیل شودو... ولی وقتی از روی برنامه می خواهم تریس کنم نمی توانم درک کنم چه می شود یهنی در فهم چگونگی تابع بازگشتی آن مشکل دارم...ممنون می شم اگه کسی پیدا بشه و برایم توضیح بده..

procedure Hanoi(n: integer; from, dest, by: char);

Begin

    if (n=1) then

        writeln('Move the plate from ', from, ' to ', dest)

    else begin

        Hanoi(n-1, from, by, dest);

        Hanoi(1, from, dest, by);

        Hanoi(n-1, by, dest, from);

    end;

End;

[m.abbasi.kia]

با سلام خدمت شما دوست عزیز
تو روابط بازگشتی کلا مسوله به چند مسئله کوچکتر تقسیم میشه ، مثلا این الگوریتم هانوی به این شکل حل میشه که : ابتدا ما n-1 دیسک رو به طریق بازگشتی از A به B منتقل می کنیم و بعد اون یه مهره رو با یه حرکت به c منتقل می کنیم خوب حالا اون n-1 مهرهای که تو B هستن رو باز هم به طریق بازگشتی به C منتقل میکنیم . در واقع مسئله به یه مسئله با n-1 مهره تبدیل میشه چون ما یه مهره رو انتقال دادیم

[m.abbasi.kia]

یه مثال جالبتر میزنم که با این حتما متوجه میشی
به این شکل که مسئله همون برج های هانوی هست ولی اینجا ما نمیتونیم مستقیما مهره رو از A به C بفرستیم یعنی واسه انتقال اون ابتدا باید اون مهره رو به B و بعدش به C انتقال بدیم
خوب حالا حل این مسئله

ابتدا ما n-1 مهره رو به طریق بازگشتی از A به C منتقل می کنیم

سپس یک مهره باقی مانده در A را به B منتقل می کنیم

حالا n-1 مهره که تو میله c هستن رو به طریق بازگشتی به A منتقل می کنیم.


یک دیسک موجود در B رو به C منتقل می کنیم


در مرحله آخر n-1 مهره باقی مانده در a رو به طریق
بازگشتی به C منتقل می کنیم



تابع بازگشتیش هم این میشه:

procedure Hanoi(n: integer; A,C,B :char);

Begin

if (n=1) then;

else begin

Hanoi(n-1, A, C, B);

writeln('Move the plate from ', A , ' to ', B)

Hanoi(n-1, C, A, B);

writeln('Move the plate from ', B , ' to ', C)

Hanoi(n-1, A, C, B);

end;

End;

که پیچیدگی زمانی ش هم میشه T(n)=3T(n-1)+2 که مرتبه O(3^2 .

امیدوارم که به دردت بخوره .

[mononok]

دوست عزیز خیلی از کمکتون ممنونم ولی همون طور که گفتم از رو شکل کاملا همون چیزهایی که گفتید رو می فهمم ولی تو ترجمه ی این سه خط موندم:یعنی وقتی خودم رو کاغذ می یام یه عدد بدم و خط به خط برنامه رو بنویسم نمی دونم چطوری n-1 رو منتقل می کنه مشکلم خود تابع بازگشتی یه .این که چه طوری کارش رو انجام میده.
بازهم ممنون

[m.abbasi.kia]

خوب تابع بازگشتی هر سری با یه تابع کوچیکتر صدا زده میشه و بقیه مراحل برنامه رو
تو پشته میریزه (آدرس بازگشت از زیر برنامه) خوب حالا تا جایی این کار رو هی تکرار میکنه تا به شرط توقف برسه و بعد پشته رو پاپ میکنه. شما سعی کن واسه n های کوچیک مثل 3 یا 4 انجام بدی راحت متوجه میشی
مثلا این فرمول بازگشتی T(n)=2T(n-1)+1 حلش میشه
T(n)=2(2T(n-2)+1)+1
T(n)=2(2(2T(n-3)+1)+1)+1
.
.
.
T(n)=2^n T(1)+ n
وقتی به این مرحله میرسه کامپیوتر T(1) شرط توقف واسش برا همین همه مراحلی که فرستاده تو پشته رو یکی یکی پاپ میکنه و محاسبه میکنه