AlgoVerse

فاکتوریل بازگشتی

n! = n · (n−1)! ساده‌ترین مثال بازگشت: فراخوانی‌ها تا حالت پایه روی پشته جمع می‌شوند و بعد در برگشت ضرب‌ها انجام می‌شود.

n! = n · (n−1) · … · 1 را می‌شود بازگشتی نوشت: n! = n · (n−1)! و 0! = 1! = 1. هر الگوریتم بازگشتی دو بخش دارد:

ادامه‌ی توضیح ↓
ورودی:
n=5خروجی PDF

5! = 120؛ پنج فراخوانی روی پشته می‌روند و در برگشت ضرب می‌شوند.

  1. def factorial(n):
  2. if n <= 1:
  3. return 1
  4. rest = factorial(n - 1)
  5. return n * rest

ناوردا: هر فراخوانی FACTORIAL(k) دقیقاً k! را برمی‌گرداند (استقرا روی k).

شروع اجرا

n5
rest—

درخت فراخوانی‌های بازگشتی

5

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

متغیرهای محلی

n5

نارنجی = در همین گام عوض شد

Call stack

  1. factorial()خط 1
گام ۱ از ۱۹
خط سیاه = multiply · خط نارنجی = گام کلیدیbase: 0/1 · multiply: 0/4
    توضیح

    ایده

    n! = n · (n−1) · … · 1 را می‌شود بازگشتی نوشت: n! = n · (n−1)! و 0! = 1! = 1. هر الگوریتم بازگشتی دو بخش دارد:

    • حالت پایه که بدون بازگشت جواب می‌دهد؛
    • گام بازگشتی که مسئله را به نمونه‌ی کوچک‌تری از خودش تبدیل می‌کند.

    پشته‌ی فراخوانی

    فراخوانی‌ها تا رسیدن به حالت پایه روی پشته جمع می‌شوند (n فریم)، بعد یکی‌یکی برمی‌گردند و ضرب‌ها در برگشت انجام می‌شوند. برای همین حافظه O(n) است، در حالی که نسخه‌ی حلقه‌ای O(1) حافظه دارد.

    در trace به چه چیزی نگاه کنی

    • پنل پشته‌ی فراخوانی را ببین: چند فریم factorial با n‌های متفاوت هم‌زمان زنده‌اند.