تابع بازگشتی چگونه کار میکنه؟

[E G A L E]

سلام.

من چند روز هست دارم روی این مبحث بازگشتی کار میکنم متاسفانه نمیدونم چرا انقدر پیچیده است!.

و روی مسئله هانوی کار میکنم و بحث من سر برج هانوی نیست و روی مبحث بازگشت مشکل دارم.




چند سوال پیش میاد

(منظورم من از q4 و q2 نوع خروجی است.)

چرا وقتی ما به q۴ میرسیم برمیگرده به q2 ? مگه برنامه تموم نمیشه؟

چرا وقتی ما از q۴ میره به q2 مقدار q افزایش پیدا میکنه؟ مثلا q۴ مقدارش ۲ است ولی q2 میشه ۳؟ و در آخر به ۴ هم میرسه!!! این از کجا میاد؟

اتابع از کجا میفهمه که تموم بشه؟

یه جا برنامه هست وسطهاش که اجراش میکنیم میبینم که q4 دوبار تکرار شده و بعدش میره قسمت q2 ! چرا؟





#include <iostream>

using namespace std;
void mile(int ,int ,int ,int);
int main()

{
int n;


cout<<"chand halghe:";

cin>>n;

mile(n,1,3,2);

return 0;

}

void mile(int q,int w,int r,int s)

{



if(q==1){


cout<<w<<" >>>>> "<<r<<endl;


return;
}

cout<<"q :"<<q<<endl;
mile(q-1,w,s,r);


cout<<"q2 :"<<q<<endl;
cout<<w<<" >>>>> w "<<r<<endl;

cout<<"q3 :"<<q<<endl;
mile(q-1,s,r,w);

cout<<"q3 :"<<q<<endl;
}

[E G A L E]

کسی نیست جواب من رو بده؟

برای n هم 4 انتخاب کنین. بهتره.

[sh4mid]

سلام
ببین تو مسایل بازگشتی باید اول مفهوم ریاضی اون رو درک کرده باشی معروفترین مثال فاکتوریل است بگذار از اون شروع کنیم
طبق تعریف داریم


|1 if n=0
n!=-|
|n(n-1)! otherwise
خوب مسئله اینجاست یک لحظه بی خیال برنامه نویسی شو و ببین معادله بالا از لحاظ ریاضی درست هست یا نه ؟ وقتی که مفهوم رو فهمیدی 99% کار انجام شده .ببین ما اینجا (از لحاظ ریاضی) اصلا کار نداریم!(n-1) چطور محاسبه می شه فقط میگیم روش اینه


تابع از کجا میفهمه که تموم بشهتو مثال بالا اون شرط n=0 این کارو انجام میده

خوب حالا بریم سراغ کد



long Fact(int n)
{
if(n==0 || n==1) return 1;
else return n*Fact(n-1);
}
ببین کار خاصی انجام نشده فقط معادله ریاضی بالا رو کد کردیم

حالا مثلا یه جا تو برنامه همچین کدی رو می نویسیم



cout<<Fact(3);ببینیم چی میشه

اول ترتیب فراخوانی ها رو ببینیم



1)Fact(3)---+
2)----------| return 3*Fact(2)---+
3)-------------------------------|retutn 2*Fact(1)---+
4)---------------------------------------------------|return 1
5)-------------------------------|return 2*1
6)----------|retutn 3*(2*1)

خوب این یعنی چی یعنی وقتی ما تابع رو در خط 1 بالا فراخوانی می کنیم اون میاد (Fact(2 فراخوانی می کنه و بعد (Fact(2 خودش (Fact(1 رو فراخوانی میکنه
حالا مقدار متغیر ها رو نگاه کنیم
تو خط اول مقدار n=3 هست وقتی تابع به این قسمت میرسه (n*Fact(n-1 تابع میاد خودشو دوباره فراخوانی میکنه خوب چی میشه این دفعه تابع Fact فراخوانی شده ولی اینجا n=2 ، خوب مقدار قبلی n کجا ذخیره شده؟ (حتما یه جایی باید ذخیره بشه ؟ درسته؟) مقدار قبلی n تو stack تابع Fact ذخیره شده(اینکه Stack چیه رو تو همین جا جستجو کن پیدا میکنی)
حالا فرض کن تابع (2)Fact جواب مارو یه جوری محاسبه کرده (حالا کار نداریم) و جواب شده 2
وقتی به جواب رسیدیم تابع به Return می رسه و مقدار جواب رو برمیگردونه (به کجا برمی گردونه؟) به اونجایی که این تابع فراخوانی شد یعنی (3)Fact یعنی حالا می دونیم (2)Fact برابر 2 هست در ضمن وقتی که تابع از (2)Fact برگشته مقدار موجود درstack رو برداشته و الان دوباره مقدار n همون 3 خودمونه گرفتی؟
همون شکل های بالا رو نگاه بندازی دستت میاد

حالا اگه ما اون شرط رو برا نگذاریم
if(n==0 || n==1) return 1;امتحان کن ببین چی میشه :لبخندساده: برنامه هی خودشو فراخوانی می کنه تا سیستم عامل هنگ کنه چون هیچ عددی برنمیگرده فقط فراخوانی محضه

خوب بریم سر برج های هانوی
خوب اول بریم سر بحث ریاضیش
ما سه تا میله داریم من اسمهاشون رو می ذارم Src Dst Aux



| | |
=|= | |
//src:First Bar A ==|== | |
//dst:Destination Bar C ------- ----- -----
//aux:Auxiliary Bar B A B C
مساله اینه که ما باید تعداد n تا صفحه رو از میله A به میله C ببریم و میله B اینجا نقش میله کمکی رو داره

خوب چطور باید این کارو انجام بدیم؟
بگذار بازگشتی فکر کنیم
اگر N=1 باشه چطور حل می شود(این حالت خاص مثل همون n=0 تو تابع فاکتوریل) اگر N=1 باشه یعنی یک صفحه داریم که براحتی می تونیم اونو از میله Src به Dst منتقل کنیم
اگر N>1 باشه چی؟ در این حالت می گیم باید اول n-1 صفحه رو از میله Src به میله Aux منتقل کنیم با کمک میله Dst بعدش آخرین صفحه رو از میله Src منتقل کنیم به میله Dst
خوب حالا بزرگترین صفحه توی میله Dst هست میله Aux هم n-1 صفحه داره میله Srcهم خالیه بعدش باید n-1 صفحه رو از میله Aux به میله Dst منتقل کنیم با کمک میله Src
و کار تمومه (ببین اینجا هم نگفتیم چطور می شه n-1 صفحه رو منتقل کرد فقط فرض کردیم به یه طریقی این کارو انجام دادیم)



1)
| | |
=|= | |
==|== | |
===|=== | |
------- ----- -----
A B C


2) move n-1 disc from A to B by C
| | |
| | |
| =|= |
===|=== ==|== |
------- ----- -----
A B C

3) move big disc from A to C
| | |
| | |
| =|= |
| ==|== ===|===
------- ------- -------
A B C
4) move n-1 disc from B to C by A
| | |
| | =|=
| | ==|==
| | ===|===
------- ------- -------
A B C

ببین اگر از نظر ریاضی مطلب رو بگیری کار تمام شده است
حالا بریم سر کد



void Hanoi(int n,char src,char dst,char aux)
{
if(n==1){cout<<src<<"--->"<<dst<<endl;}
else
{
Hanoi(n-1,src,aux,dst);
cout<<src<<"--->"<<dst<<endl;
Hanoi(n-1,aux,dst,src);
}
}
حالا تو برنامه اصلی همچین تابعی رو فراخوانی می کنیم



Hanoi(n,'a','c','b');
ترتیب فراخوانی ها اینجوریه




1)Hanoi(3,'a','c','b')---+"src='a' dst='c' aux='b'" <-----------It is Stack value
|Hanoi(2,'a','b','c')---+ "src='a' dst='b' aux='c'"
| |Hanoi(1,'a','c','b')---+ "src='a' dst='c' aux='b'
| | |n==1 ==> cout<<src<<"--->"<<dst<<endl *a-->c 1st Print(Function return)
| |cout<<src"--->"dst<<endl; src='a' dst='b' *a-->b 2nd Print
| |Hanoi(1,'c','b','a')---+ "src='c' dst='b' aux='a'"
| |n==1 ==> cout<<src<<"--->"<<dst<<endl *c-->b 3rd Print(Function return)
|cout<<src<<"--->"<<dst<<endl; src='a' dst='c' *a-->c 4th Print
|Hanoi(2,'b','c','a')---+ "src='b' dst='c' aux='a'
| |Hanoi(1,'b','a','c')---+ "src='b' dst='a' aux='c'
| | |n==1 ==> cout<<src<<"--->"<<dst<<endl *b-->a 5th Print(Function return)
| |cout<<src"--->"dst<<endl; src='b' dst='c' *b-->c 6th Print
| |Hanoi(1,'a','c','b')---+ "src='a' dst='c' aux='b'
| |n==1 ==> cout<<src<<"--->"<<dst<<endl *a-->c 7th Print(Function return)

اگه دقت کنی اینجا هم اون شرط اول تابع هست که باعث میشه یه جایی فراخوانی ها تموم بشه و تابع دچار فراخوانی بینهایت نشه اون شکل بالا رو روش دقت کن فکر کنم مشکلت حل بشه:کف::کف::کف:

[E G A L E]

سلام

ممنون از جواب شما. من قسمت فاکتوریل رو قبل بلد بودم و فهمیده بودم و میدونستم که چجوری کار میکنه. اما برج هانوی خیلی پیچیده است!.

راه حلی که شما دادین یه چیزیهایی فهمیدم ولی مشکل من در هانوی همینجاست!.

جواب برنامه رو میزارم:


chand halghe:4


q :4
q :3
q :2
1 >>>>> 2
q1 :2
1 >>>>> 3
q2 :2
2 >>>>> 3
q3 :2
q1 :3
1 >>>>> 2
q2 :3
q :2
3 >>>>> 1
q1 :2
3 >>>>> 2
q2 :2
1 >>>>> 2
q3 :2
q3 :3 ????????????????????????????A
q1 :4
1 >>>>> 3
q2 :4
q :3
q :2
2 >>>>> 3
q1 :2
2 >>>>> 1
q2 :2
3 >>>>> 1
q3 :2
q1 :3
2 >>>>> 3
q2 :3
q :2
1 >>>>> 2
q1 :2
1 >>>>> 3
q2 :2
2 >>>>> 3
q3 :2
q3 :3
q3 :4??????????????????????????????B

من 2 قسمت علامت ?? کردم.

قسمت A چرا q3 دو بار تکرار شده؟ مگه وقتی q3 اولی که مقدارش 2 هست نباید اجرا بشه؟
و بعدش q1 که مقدار 4 هست در واقع برنامه برگشت اول ؟ یا مقدار stack رو برگردوند؟


قسمت B چرا q3 سه بار تکرار شده؟ برنامه وقتی به عدد صفر برسه تموم میشه درسته؟ پس چرا نشون نداده؟

[sh4mid]

ولی مشکل من در هانوی همینجاستدوباره این تکه رو با دقت بخون بهت گفتم اگر مفهوم ریاضی شو درک کنی کار تمومه

اگر N>1 باشه چی؟ در این حالت می گیم باید اول n-1 صفحه رو از میله Src به میله Aux منتقل کنیم با کمک میله Dst بعدش آخرین صفحه رو از میله Src منتقل کنیم به میله Dst
خوب حالا بزرگترین صفحه توی میله Dst هست میله Aux هم n-1 صفحه داره میله Srcهم خالیه بعدش باید n-1 صفحه رو از میله Aux به میله Dst منتقل کنیم با کمک میله Src
و کار تمومه (ببین اینجا هم نگفتیم چطور می شه n-1 صفحه رو منتقل کرد فقط فرض کردیم به یه طریقی این کارو انجام دادیم)
رنامه وقتی به عدد صفر برسه تموم میشه درسته؟ پس چرا نشون نداده؟ نه برنامه وقتی n=1 بشه برمیگرده به شرطی که گذاشتی دقت کن



if(q==1)
{
cout<<w<<" >>>>> "<<r<<endl;
return;
}

این همون ترمز است که نمی گذاره برنامه تو حلقه بی نهایت فراخوانی بیفته


من 2 قسمت علامت ?? کردم.

قسمت A چرا q3 دو بار تکرار شده؟ مگه وقتی q3 اولی که مقدارش 2 هست نباید اجرا بشه؟
و بعدش q1 که مقدار 4 هست در واقع برنامه برگشت اول ؟ یا مقدار stack رو برگردوند؟


قسمت B چرا q3 سه بار تکرار شده؟ خوب بریم سروقت کدت
اولا چندتا نکته
نامگذاری متغیرهات رو بهتر کن (بنظرت کدوم اینها معنی دار تر هستند)



void Hanoi(int nDisc,char src,char dst,char aux)
void mile(int q,int w,int r,int s)

برای همچین برنامه ای بهتر است برای نام گذاری میله ها از 'a' 'b' 'c' استفاده کنی چون جواب واضح تری بهت میده(این نظر شخصی خودمه)




Hanoi(n,'a','c','b');
mile(n,1,3,2);


برای برنامه ها و توابعی که می نویسی یه کم توضیح بنویس تا پس فردا که رفتی سروقتش n ساعت وقت نگذاری تا بفهمی این تابع قرار بود چه کار کنه

یاد بگیر چطور برنامه رو Debug و Trace کنی (هم تو IDE هم تو Commandline هم روی کاغذ)
تو مسایل بازگشتی باید بتونی ترتیب فراخوانی تابع رو درک کنی

خوب یه نگاه به فراخانی این بنداز ، اون قسمت هایی که مشکل داشتی رو علامت زدم




1)Hanoi(4,a,c,b)---+
|Q:4
|Hanoi(3,a,b,c)----+
| |Q:3
| |Hanoi(2,a,c,b)---+
| | |Q:2
| | |Hanoi(1,a,b,c)---+
| | | |a-->b
| | |Q2:2
| | |a-->c
| | |Q3:2
| | |Hanoi(1,b,c,a)---+
| | | |b-->c
| | |Q3`:2
| |Q2:3
| |a-->b
| |Q3:3
| |Hanoi(2,c,b,a)---+
| | |Q:2
| | |Hanoi(1,c,a,b)---+
| | | |c-->a
| | |Q2:2
| | |c-->b
| | |Q3:2
| | |Hanoi(1,a,b,c)---+
| | | |a-->b
| | |Q3`:2 <=====================IT's PRINT THEN NEXT LINE PRINT
| |Q3`:3 <=====================================IT'S A SECTION
|Q2:4
|a-->c
|Q3:4
|Hanoi(3,b,c,a)----+
| |Q:3
| |Hanoi(2,b,a,c)---+
| | |Q:2
| | |Hanoi(1,b,c,a)---+
| | | |b-->c
| | |Q2:2
| | |b-->a
| | |Q3:2
| | |Hanoi(1,c,a,b)---+
| | | |c-->a
| | |Q3`:2
| |Q2:3
| |b-->c
| |Q3:3
| |Hanoi(2,a,c,b)---+
| | |Q:2
| | |Hanoi(1,a,b,c)---+
| | | |a-->b
| | |Q2:2
| | |a-->c
| | |Q3:2
| | |Hanoi(1,b,c,a)---+
| | | |b-->c
| | |Q3`:2 <=========================IT PRINT THEN NEXT LINE PRINT
| |Q3`:3 <==========================================IT PRINT THEN NEXT LINE PRINT
|Q3`:4 <================================================== ======IT's B SECTION

راستی تو کدت دوبار Q3 نوشتی من ایجا اون Q3 آخری رو با Q3` نشون دادم

[E G A L E]

ممنون دوست من خیلی راه حل شما مفید بود و کاملا یاد گرفتم و فهمیدم چی میگذره.

و اون پیشنهاد شما خیلی خوب بود و چیزهای زیادی از شما یاد گرفتم.

موفق باشید.

[ebrahim1988]

دوباره این تکه رو با دقت بخون بهت گفتم اگر مفهوم ریاضی شو درک کنی کار تمومه



نه برنامه وقتی n=1 بشه برمیگرده به شرطی که گذاشتی دقت کن






if(q==1)


{


cout<<w<<" >>>>> "<<r<<endl;


return;


}





این همون ترمز است که نمی گذاره برنامه تو حلقه بی نهایت فراخوانی بیفته




خوب بریم سروقت کدت


اولا چندتا نکته


نامگذاری متغیرهات رو بهتر کن (بنظرت کدوم اینها معنی دار تر هستند)






void Hanoi(int nDisc,char src,char dst,char aux)







void mile(int q,int w,int r,int s)






برای همچین برنامه ای بهتر است برای نام گذاری میله ها از 'a' 'b' 'c' استفاده کنی چون جواب واضح تری بهت میده(این نظر شخصی خودمه)








Hanoi(n,'a','c','b');


mile(n,1,3,2);







برای برنامه ها و توابعی که می نویسی یه کم توضیح بنویس تا پس فردا که رفتی سروقتش n ساعت وقت نگذاری تا بفهمی این تابع قرار بود چه کار کنه




یاد بگیر چطور برنامه رو Debug و Trace کنی (هم تو IDE هم تو Commandline هم روی کاغذ)


تو مسایل بازگشتی باید بتونی ترتیب فراخوانی تابع رو درک کنی




خوب یه نگاه به فراخانی این بنداز ، اون قسمت هایی که مشکل داشتی رو علامت زدم







1)Hanoi(4,a,c,b)---+


|Q:4


|Hanoi(3,a,b,c)----+


| |Q:3


| |Hanoi(2,a,c,b)---+


| | |Q:2


| | |Hanoi(1,a,b,c)---+


| | | |a-->b


| | |Q2:2


| | |a-->c


| | |Q3:2


| | |Hanoi(1,b,c,a)---+


| | | |b-->c


| | |Q3`:2


| |Q2:3


| |a-->b


| |Q3:3


| |Hanoi(2,c,b,a)---+


| | |Q:2


| | |Hanoi(1,c,a,b)---+


| | | |c-->a


| | |Q2:2


| | |c-->b


| | |Q3:2


| | |Hanoi(1,a,b,c)---+


| | | |a-->b


| | |Q3`:2 <=====================IT's PRINT THEN NEXT LINE PRINT


| |Q3`:3 <=====================================IT'S A SECTION


|Q2:4


|a-->c


|Q3:4


|Hanoi(3,b,c,a)----+


| |Q:3


| |Hanoi(2,b,a,c)---+


| | |Q:2


| | |Hanoi(1,b,c,a)---+


| | | |b-->c


| | |Q2:2


| | |b-->a


| | |Q3:2


| | |Hanoi(1,c,a,b)---+


| | | |c-->a


| | |Q3`:2


| |Q2:3


| |b-->c


| |Q3:3


| |Hanoi(2,a,c,b)---+


| | |Q:2


| | |Hanoi(1,a,b,c)---+


| | | |a-->b


| | |Q2:2


| | |a-->c


| | |Q3:2


| | |Hanoi(1,b,c,a)---+


| | | |b-->c


| | |Q3`:2 <=========================IT PRINT THEN NEXT LINE PRINT


| |Q3`:3 <==========================================IT PRINT THEN NEXT LINE PRINT


|Q3`:4 <================================================== ======IT's B SECTION






راستی تو کدت دوبار Q3 نوشتی من ایجا اون Q3 آخری رو با Q3` نشون دادم

















خودمونیما، ولی کار شما خیلی درسته ها
واقعا آفرین به این همه فکر مردم بودن و حوصله داشتن
بخدا خیلی ازتون خوشم اومد
آفرین!!!!!!!!!!!!!!!!!!