recursion الگوریتمی است که از آن برای حل مسایلی که نیاز است به اجزا پایینی و ریزتر یک مساله مراجعه کرد استفاده می شود. به عبارت دیگر الگوریتم بازگشتی، فرآیندی است که در پاسخ اجرا، خودش را فراخوانی می کند. از جمله مزایای استفاده از recursion کمینه کردن مقدار خط کدهایی است که قرار است نوشته شود ولی در عین حال منابع زیادی برای محاسبات را به خود اختصاص می دهد. در ادامه یه توضیح انواع recursion و مثال های متفاوت از پیاده سازی و حل مسایل آن با استفاده از پایتون می پردازیم.
فاکتوریل
فاکتوریل به ضرب اعداد طبیعی غیر منفی در هم می گویند که کاربرد گسترده ای در آنالیز ریاضی، احتمالات و جبر داره و البته همراه با قدمت طولانی.
تابع فاکتوریل عبارت است از :
با توجه به تابع بالا، به طور مثال فاکتوریل عدد 5 برابر خواهد بود، با حاصل ضرب مقادیر 1، 2، 3، 4 و 5 (حاصل : 120). و فاکتوریل صفر برابر 1 می شود.
و اما اگر بخواهیم با recursion به محاسبه مقدار فاکتوریل 5 بپردازیم خواهیم داشت :
همونطور که در عکس بالا مشخصه برای محاسبه فاکتوریل 5 با recursion، باید فاکتوریل مقادیر کوچکتر از آن به ترتیب در هر مرحله محاسبه شود واین دقیقا همون خاصیت برگشت پذیری و اجرا دوباره recursion هستش. روش پایتونی برای محاسبه فاکتوریل برابر خواهد بود با :
|
1 2 3 4 5 6 7 |
def factorial(n): if n==0: return 1 else: return n*factorial(n-1) print(factorial(5)) |
که در صورتی که مقدار ورودی تابع صفر باشد عدد یک بازگردانده می شود و در غیر این صورت تا زمان رسیدن به 0 از مقدار ورودی n، به اندازه یک واحد (n-1) کم می شود و دوباره تابع اجرا می شود. که اگر مرحله به مرحله اجرا کنیم مراحل زیر را خواهیم داشت.
استفاده از while
همچنین می تونید با while همین کد رو اجرا کنید :
|
1 2 3 4 5 6 |
def while_factorial(n): while n >= 1: return n * factorial(n - 1) return 1 print(while_factorial(5)) |
ذخیره نتایج فاکتوریل و استفاده در محاسبات بعدی
با بالا رفتن n، محاسبه فاکتوریل زمانبرتر خواهد شد که می توانیم موارد را چون همه یکبار محاسبه می شوند ذخیره کنیم تا میزان محاسبات را در دفعات بعد کمتر کنیم. برای اینکار از یک دیکشنری استفاده می کنیم و در صورتی که n قبلا محاسبه شده باشد در مقدار value دیکشنری آن را استخراج می کنیم و نتیجه رو در n های بالاتر استفاده کنیم.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
def factorial(n, cache={}): if n < 1: return 1 elif n in cache: return cache[n] else: print(f'calculating {n}!') result = n * factorial(n-1) cache[n] = result return result print('Result of 3!:', factorial(3)) print('============================') print('Result of 5!:', factorial(5)) |
|
1 2 3 4 5 6 7 8 |
calculating 3! calculating 2! calculating 1! Result of 3!: 6 ============================ calculating 5! calculating 4! Result of 5!: 120 |
مشاهده می کنیم که دیگه در محاسبه فاکتوریل 5 فاکتوریل 1 و 2 و 3 دیگه محسابه نمی شوند چون قبلا در دیکشنری ذخیره شدند.
استفاده از lru_cache
به طور پیش فرض در python برای cache کردن متودی وجود داره که می تونید به صورت decorator ازش در محاسبات استفاده کنید. به طور نمونه برای مثال factorial به صورت زیر خواهیم داشت:
|
1 2 3 4 5 6 |
from functools import lru_cache @lru_cache(2**3) def factorial(n): print(f'n={n}') return 1 if n<2 else n * factorial(n-1) |
بهتره ورودی و تعداد cache مورد نظر شما در خروجی به صورت 2 به توان n باشه. همونطور که در خروجی میبینید وقتی به تعداد 8 در تعداد بازگشت و ذخیره 8 مقدار فاکتوریل اول می رسیم فقط مقدار بعدی یعنی 9 محاسبه می شود دقیقا مشابه قسمت قبل…
