توابع بازگشتی چطور کار می کنند؟ How does recursion work?
شکوفه دانش |
شنبه, ۲۸ بهمن ۱۳۹۶، ۱۲:۱۲ ق.ظ |
۰ نظر
فرض کنید جمعی از افراد ایستادن و قراره کاری توسط همه شون انجام بشه.
بعد یک نفر از وسط جمع می گه من می تونم قسمت اول کار رو انجام بدم، نفر دیگری می گه من می تونم قسمت دوم کار رو انجام بدم، و به همین ترتیب الی آخر. تا اینکه کار کاملا بینشون تقسیم میشه.
حالا در یک مورد عجیب، فرض کنید همون جمع وجود داشته باشه ولی تمام افراد فقط یک نفر باشن! می دونم که خیلی تصورش عجیبه.
حالا مجددا فرض کنید فرار باشه کاری توسط همه شون انجام بشه. طبعا نفر اول وقتی بگه می تونه اون کار رو انجام بده بقیه همه هم می تونن. بنابراین باید اون یک نفر اون کار رو به نحوی انجام بده که کمکی بکنه به بقیه که با انجام دقیقا همون کار مشابه اون فرد حل مشکل رو یک گام به جلوتر ببرن!
یک مثالش x^n هست در شرایطی که فرض کنیم فقط عمل ضرب برامون میسر باشه و نتونیم توان رسانی کنیم.
حالا یک تابع رو تصور کنید که بگه من می تونم ضرب دو عدد رو برگردونم. پس
func pow(int x, int n){ if(n==2) return x*x;}حالا بیاید ببینیم این تابع اگر کار خودشو دوباره انجام بده چی می تونه تولید کنه
func pow(int x, int n){ if(n==2) return x*x; return pow(x,n/2)*pow(x,n/2);}دقت کنید این همون تابع بالاست، با این تفاوت که صدا کردن خودش با همون کار "منتهی این بار به شکل تقسیم شده تر" بهش واگذار شده.
حالا اگر بهش بدیم: pow(x,4) اول این اجرا میشه: return pow(x,2)*pow(x,2);
بعد این اجرا میشه: return x*x;
بعد این return x*x
بعد هم این return (x*x)*(x*x);
که همون جواب مورد نظر ماست.
اما حالا بیاید بهش بدیم pow(x,3) اول این اجرا میشه: return pow(x,1)*pow(x,1);
که به وضوح از همین اول غلطه! چراکه توان ما فرد بوده و به یک ضرب اضافی دیگر در x هم احتیاج داریم. حتی ایراد کار تنها به همینجا هم خلاصه نمیشه و حتی وقتی که به اجراش ادامه هم می ده به یک دور بی نهایت دچار میشه چونکه 2 تقسیم بر 2 مساوی 1 میشه درحالیکه ما شرط پایانی رو، برابر شدن توان با 2 در نظر گرفتیم. درحالیکه توان های 1 و صفر کوچکترین توان های غیرمنفی هستن. پس تابع رو مجددا بازنویسی می کنیم:
func pow(int x, int n){ if(n<0) return -1; //This function is not going to calculate negative powers. if(n<=1) return x; if(n%2==0) //if n is even return pow(x,n/2)*pow(x,n/2); return pow(x,n/2)*pow(x,n/2)*x;}و حالا این تابع دیگه به درستی کار می کنه.
دقت کنید جمله ی آخر احتیاجی به else نداشتیم چونکه شرط if اگر درست می بود return مقابلش انجام می شد و وقتی انجام نشود به return بعدی می رسد که خود به خود این همین معنای else شدن را دارد با این تفاوت که اندکی از سربار کاری که پردازنده بخواهد انجام بدهد کاسته شده است.
