کاربرد پشته در تابع بازگشتی

[sahra222]

باسلام
بچه ها من یه سوال داشتم که خیلی ام روش کارکردم ولی جوابی نگرفتم
ببینید این سوال من درمورد توابع بازگشتی و پشته است.
من میدونم هروقت از تابع بازگشتی استفاده میشه یا اینطور بگم هر موقع تابعی خودش رو فراخوونی میکنه این فراخونیها تو پشته ذخیره میشن
ولی این برای جواب دادن به سوالهایی که تو ذهنمه کافی نیست من تو پوش کردن پشته مشکلی ندارم مشکله من از عمل پاپ شروع میشه
کی عمل پاپ صورت میگیره
با چه دستوری پشته میفهمه باید پاپ کنه دیگه پوش کردن بسهههههه
من نمیفهمم میخام یکی برام توضیح بده:افسرده:
نمیدونم منظورمو چطور برسونم
من اینجا دوتا تابع نوشتم
خروجیاشو نیگاه کنید ببینید متفاوته قبل از اینکه برنامه رو تریسش کنم فک میکردم خروجی هر 2 تابع میشه این
-1-2-4-8-16
ولی میبینید که این نشد
میخام بدونم بعد از رفتن این فراخونیا تو پشته چه بلایی سرش میاد که جواب میشه این
این دستور ریترن چی سر تابع میاره که جوابش میشه این؟؟
خدا کنه منظورمو فهمیده باشید
ممنونم میشم جواب بدین
منتظر ه منتظرم.



#include <iostream.h>
int test(int b)
{
if(b>1) return(test(b/2));
cout<<'-'<<b;
}

int main()
{int q;
cin>>q;
test(16);
return 0;
}
*************
khoroji
*************
-1
*************
#####################################halate dovom
#include <iostream.h>
int test(int b)
{
if(b>1) test(b/2);
cout<<'-'<<b;
}

int main()
{int q;
cin>>q;
test(16);
return 0;
}
*************
khoroji
*************
-1-2-4-8-16
*************

[saeedr22]

این واسه من هم یه سواله

[tdkhakpur]

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


call tset --> b = 16 --> cout <<"-"<<'16';
b>1 --> call test(8) -> cout <<"-"<<'8';
b>1 --> call test(4) -> cout <<"-"<<'4';
b>1 --> call test(2) -> cout <<"-"<<'2' ;
b==1 --> cout <<"-"<<'1';

تابع بازگشتی نتیجه را از آخر به اول چاپ میکند

[Yasersadegh]

خوب دوستان من توضيحات دوستمون tdkhakpur رو كامل مي كنم!!
دوست عزيز شما هر دو حالتي كه نوشتيد دارن يه كار رو انجام ميدن با يه تفاوت كوچيك كه اونم همون ريترنيه كه نوشتيد!!:چشمک:
حالا


من اینجا دوتا تابع نوشتم
خروجیاشو نیگاه کنید ببینید متفاوته قبل از اینکه برنامه رو تریسش کنم فک میکردم خروجی هر 2 تابع میشه این
-1-2-4-8-16
ولی میبینید که این نشد
در واقع وقتي كه كنترل برنامه به داخل تابع test مياد، اول شرط بررسي مي شه اگر درست باشه در هر دو حالت دوباره تابع test اجرا ميشه ولي اگه شرط غلط باشه خروجي چاپ ميشه!!:چشمک:
حالا بعد از اتمام فراخواني ها
در حالت اول دستور ريترن اجرا ميشه كه پاسخ برگشتي را به مرحله قبلي بر مي گردونه كه ديگه اجازه نمي ده دستور Cout اجرا بشه بنابراين تنها يه -1 در آخرين فراخواني test چاپ ميشه
در حالت دوم بعد از اجراي شرط و دستور test خروجي نيز چاپ مي شود



این دستور ریترن چی سر تابع میاره که جوابش میشه این؟؟
نكته: در توابعي كه از دستور return استفاده شود با رسيدن به اين دستور كنترل برنامه از تابع خارج مي شود و باقي دستورات اجرا نمي شود.

اميدوارم كه تونسته باشم به خوبي منظور رو برسونم.:لبخندساده:

[sahra222]

باسلام و تشکر از همه
توضیحی که آقای yasersadegh دادن درمورد ریترن خیلی موضوعارو روشن کرد برام....اینو من یه جای جزوم نوشته بودم ولی هیچوقت بهش توجه نمیکردم ....بازم از دوست خوبمون ممنونم.



#include <iostream.h>
int rec(int p,int q)
{int R;
if(q<=0) return 1;
R=rec(p,q/2);
R=R*R;
if (q%2==0)
return R;
else
return R*p;
}

int main()
{
cin>>1;
cout<<rec(5,3);
return 0;
}




جوابش میشه 125
این برنامه واسه کنکور دولتی 80
پشته حاصل از این کد برنامه این شکلیه یعنی فراخونیا اینجوری تو پشته قرار میگیرن


3-int rec(5,0)---->return 1;
2-int rec(5,1)---->R=rec(5,0);
1-int rec(5,3)---->R=rec(5,1);

حالا عمل پوش با اولین ریترن اجرا میشه درسته؟>؟؟؟؟؟؟؟///


__________________________________________
مرحله اول
3-int rec(5,0)---->return 1;
__________________________________________
مرحله دوم
2-int rec(5,1)---->R=rec(5,0)=1;
R=R*R=1
q%2=1------->return R*p------>1*5=5;
__________________________________________
مرحله سوم
1-int rec(5,3)---->R=rec(5,1)=5;
R=R*R=25
q%2=1------->return R*p------>25*5=125;
__________________________________________


حالا همون برنامه ولی با تغییر...............................


#include <iostream.h>
int rec(int p,int q)
{int R;
if(q<=0) return 1;
return(rec(p,q/2));
R=R*R;
if (q%2==0)
return R;
else
return R*p;
}

int main()
{
cin>>1;
cout<<rec(5,3);
return 0;
}


پشته حاصل از این کد برنامه این شکلیه یعنی فراخونیا اینجوری تو پشته قرار میگیرن


3-int rec(5,0)---->return 1;
2-int rec(5,1)---->return(rec(5,0));
1-int rec(5,3)---->return(rec(5,1));



طبق گفته شما دیگه دستوراته بعده ریترن اجرا نمیشه و درخروجی 1 نمایش داده میشه


3-int rec(5,0)---->return 1;
2-int rec(5,1)---->return(rec(5,0));----->return(1)
1-int rec(5,3)---->return(rec(5,1));----->return(1)

[sahra222]

یه سوال دیگه درمورد تابع بازگشتی ؟

اگر این تابع به اینصورت فراخوانی بشه:
Test(64)


void test(int & b )
{ if (b>1)
{
b=b/2;
test(b);
}
cout<<b;
}


فراخوانیها به این صورت است:


Test(64)-à Test(32)-à Test(16)-à Test(8)-à Test(4)-à Test(2)-à Test(1)



ولی 7تا یک چاپ میشه اونم چون متغیرb سراسری تعریف شده وآخرین مقدار bیعنی یک به همه فراخوانیها منتقل میشود...یعنی چی این جمله؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟

[Yasersadegh]

فراخوانیها به این صورت است:


Test(64)-à Test(32)-à Test(16)-à Test(8)-à Test(4)-à Test(2)-à Test(1)

ولی 7تا یک چاپ میشه اونم چون متغیرb سراسری تعریف شده وآخرین مقدار bیعنی یک به همه فراخوانیها منتقل میشود...یعنی چی این جمله؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
ببينيد دوست عزيز
اگر شما در ورودي تابع تون از علامت & استفاده نمي كرديد جواب همون چيزي مي شد كه انتظارشو داشتيد يعني وقتي كه از اين علامت & استفاده نمي كنيد هر كدام از فراخواني هاي تابع Test متغير اختصاصي خود را دارد يعني به تعداد فراخواني ها متغير b در حافظه به شكل پشته توليد مي شوند كه هر تابع متغير خود را پوش مي كند و چاپ مي كند!:لبخندساده:
اما
وقتي كه از علامت & استفاده مي كنيد تنها يك متغير b در حافظه وجود دارد كه هر بار كه تابع test را فراخواني مي كنيد تنها آدرس اون به تابع ارسال ميشه يعني مقدار همون يه متغير هر بار عوض ميشه كه در نهايت مقدارش برابر با 1 ميشه و حالا همه توابع مقدار همون متغير را چاپ مي كنند كه نتيجه همون ميشه كه 7 تا يك چاپ ميشه!!:لبخندساده:
موفق باشي:چشمک: