بازگشت و گام بازگشت.

[deopen]

سلام... من در حال یادگیری زبان قدرتمند cpp هستم و در مورد بازگشت به مشکل برخوردم.
همونطور که میدونین هر مساله بازگشتی رو میشه بصورت حلقه ای هم نوشت و از overheading یا سربار زمان اجرا هم جلوگیری میشه. پس مزیت بازگشت نسبت به حلقه چیست من تا الان با بازگشت و گام بازگشت سروکار نداشتم.
این مساله اولین مساله ای هست که من هم با بازگشت هم با حلقه نوشتمش :

تابع فاکتوریل :



#include<iostream>
using std::cout;
using std::cin;
using std::endl;
unsigned long factorial(unsigned long);
unsigned long factorialR(unsigned long);
int main() {
cout<<"factorial(loop) ==> "<<factorial(5)<<endl;
cout<<"factorial(return) ==> "<<factorialR(5)<<endl;
cin.get();
}
unsigned long factorial(unsigned long num=0) {
int result=1;
for (int i=num;i>=2;i--)
result*=i;
return result;
}
unsigned long factorialR(unsigned long num=0) {
if (num<=1)
return 1;
else
return num * factorialR(num-1);
}


خوب حالا مزیت بازگشت نسبت به حلقه چیه؟؟!!

[NotAtMyDesk]

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

[deopen]

همین ؟!! اگه تنها مزیتش همینه من تکرار رو ترجیح میدم !!!

[RF.Ariyapoor]

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

دوست عزیز به نظر من هم دقیقا الگوریتم های بازگشتی همین خصوصیات رو دارن


همین ؟!! اگه تنها مزیتش همینه من تکرار رو ترجیح میدم !!!یه جا میرسه که اگه نخوای بازگشتی الگوریتمتو بنویسی اینقدر برنامت پیچیده و بلند میشه که حتما میری سراغ الگوریتم بازگشتی . حالا تو این مثال فاکتوریل از شانس شما اندازه بازگشتی و غیر بازگشتی تغریبا یکی شده ولی بعضی جاها تو برنامه های پیچیده تر حجم کد رو خلی پایین تر میاره

برنامه هایی رو تجربه کردم که اگه با بازگشتی نوشته نمیشدن چندین برابر میشدن

در کل هر روشی رو باید دید کجا بهتره که آدم به کار ببنده

[deopen]

اینارو خوندم , اما من اهمیت نمیدم که بازگشت کدهامو کوتاه و قابل فهم کنه ! من وقتی به یک برنامه ی بازگشتی نگاه میکنم میبینم که هر دفعه تابع فراخوانی میشه , یک کپی از متغیر هاشم ایجاد میشه! این یعنی مصرف حافظه ی زیاد و بیخو د و این نتیجه ای جز ایجاد overhead نداره! در حالی که در حلقه متغیری ایجاد نمیشه بلکه همون متغیرها مدام در حال تغییر هستند . به من کد نشون بدین.


برنامه هایی رو تجربه کردم که اگه با بازگشتی نوشته نمیشدن چندین برابر میشدن


یک برنامه همینطوری که خودت گفتی بهم نشون بده.
من کاملا تازه کارم به دو ماه نمیرسه که cpp رو شروع کردم نیاز به توجیح دارم منو توجیح کنید . کدی نشونم بدین که خلاف گفته هامو ثابت کنه !

[Nima_NF]

همیشه مسائل به همین راحتی و کوتاهی نیستند که بتوان آن ها را با حلقه نوشت، دقت کنید که در اکثر کامپایلر ها اگر تابع بازگشتی شما به اندازه تعداد مشخصی تکرار می شود، بهینه ساز آن را با یک حلقه تکرار در هنگام کامپایل عوض می کند. (مثال فاکتوریل فقط به عنوان ساده ترین نمونه مطرح می شود)
پس اگر شما هم می توانید این کار را انجام دهید، بهتر هست با حلقه جایگزین کنید.

بازگشتی بیشتر در جایی استفاده می شود که معمولا ما از انتهای آن و یا تعداد حلقه هایمان مطلع نیستیم. مثلا در پردازش درخت ها از ریشه به برگ ها و یا امثال آن در هوش مصنوعی که با لیست پیوندی کار داریم، با یک قدم جلو رفتن می توان فهمید مرحله بعدی وجود دارد یا خیر و به چه شکلی ( کلا ممکن است هزاران حلقه تو در تو وجود داشته باشد ولی ما در ابتدا از آن اطلاع نداریم). در اینجا بازگشتی بهترین راه است، مثلا در الگوریتم درخت BSP داریم:



bool node::TestPoint(point& pt )
{
switch( node.part_plane.Classify_Point( pt ) )
{
case front:
return front.TestPoint( pt );

case back:
return back.TestPoint( pt );

case coplanar:
// Let's drop down the back tree
return back.TestPoint( pt );
}
}

[deopen]

بازگشتی بیشتر در جایی استفاده می شود که معمولا ما از انتهای آن و یا تعداد حلقه هایمان مطلع نیستیم.

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

[Salar Ashgi]

همین ؟!! اگه تنها مزیتش همینه من تکرار رو ترجیح میدم !!!


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

ممکنه تبدیل نسخه بازگشتی اونها به حلقه هفته ها و یا حتی ماه ها طول بکشد !!!

شما الان برنامه فاکتوریل رو دیدی ، و فکر میکنی که همه مسائل به این سادگی قابل پیاده

سازی اند !!!!

مثلا الگوریتم هایی مثل : برجهای هانوی ، هشت وزیر ، Merge Sort ، Quick Sort و ....

نسخه غیر بازگشتی شان واقعا نیاز به مدتی تفکر دارد و همینطوری نمیشه جواب داد !!!

الگوریتم های بازگشتی درست است که نسبت به حلقه قابل درک و پیاده سازی شان

راحتتر است ، ولی بدلیل استفاده زیاد از حافظه Stack ، از سرعت مطلوبی برخوردار نیستند

و در اثر استفاده زیاد با خطای Stack Over Flow (سر ریز شدن استک) مواجه خواهیم شد !!

موفق و پیروز باشید !!!!