Recursion
رکوراسیون در درک من یک پیاده سازی بسیار واضح از تقسیم و هماهنگی است.
رکورد بسیار مفید است، زمانی که ساده تر است مشکل خود را به مشکلات کوچکتر و مشکلات کوچکتر به مشکلات کوچکتر تقسیم کنید برای مقابله با آن ها به طور جداگانه.
بر اساس این درک، من فکر نمی کنم که بازگشت به عنوان یک روش مناسب برای مشکل فیبوناچی است، با توجه به این که برخی از خطرات بالقوه با این ابزار (مانند سرریز پشته) وجود دارد. Recursion می تواند ابزار بسیار قدرتمند برای تولید راه حل های ظریف باشد، اما با قدرت بزرگ مسئولیت بزرگی به عهده می گیرد.
پس از گفتن، من توصیه نمی کنم از بازگشت برای توالی فیبوناچی (یا فاکتوریل) استفاده کنم. اگرچه بسیار مفید است از این پیاده سازی آگاه باشید، من فقط به عنوان آخرین راه حل استفاده از آن را توصیه می کنم، اگر به وضوح در شرایط سخت (در طی یک مصاحبه برنامه نویسی، مثلا) بیان شده است.
با وجود اینکه این کار می کند، من نمی خواهم آن را یک راه حل کامل می نامید. ما میتوانیم بهتر از این انجام دهیم. بیایید ببینیم چه اتفاقی می افتد با تماس با تابع فیبر بازگشتی با یک استدلال 4:
1. فیبر نوری (4) به فیبرتی (3) + فیبوت (2)
2 حل می شود. فیبر نوری (3) فیبر نوری (2) + فیبوت (1)
3 را حل میکند. فیبوت (2) حلقه به 1
4. فیبوت (1) به 1 برمی گردد
5. (1) + fib (0)) … (فیبوناچی (0) حل می شود به 0
fib (4) = فیب (3) + fib (2) = (فیب (2) + fib (1) 19659013] ما در اینجا 1 و 2 نقطه علاقه مند هستیم. همانطور که می توانید دوبار با همان پارامتر خود بایستید. این می تواند و باید اجتناب شود.
پیچیدگی زمان برای این پیاده سازی O (2 ^ n) بسیار بالا است
چگونه می توانیم آن را بهینه سازی کنیم؟
Memoization
Memoization یک روش بهینه سازی است ما همیشه می توانیم استفاده کنیم اگر ما می دانیم که الگوریتم ما یک تابع مشابه را با پارامتر های مشابه چندین بار فراخوانی می کند. به جای اجرای چنین تابع، ما می توانیم نتیجه ی اجرای قبلی را "به یاد داشته باشیم"، اجازه می دهد تا نگاهی به پیاده سازی بسیار اساسی داشته باشیم:
ما از کش متغیر استفاده می کنیم تا به نتیجه ی عملکرد تابع بپردازیم و اگر پارامتر برای اجرای تابع آینده در حال حاضر در حافظه پنهان است و سپس این مقدار را به دست می آوریم.
این پیاده سازی به ما اطمینان می دهد که برای هر تابع تعداد فیبر تنها یکبار اجرا می شود. پیچیدگی زمان برای این پیاده سازی O (n) است که بسیار بهتر از بازگشت مجدد سنتی است. همانطور که در "حلقه و آرایه" پیاده سازی شده است، این نسخه اضافه می کند سربار حافظه برای ذخیره سازی حافظه پنهان ما با پیچیدگی O (n)
