مبانی کامپیوتر و الگوریتم؛ از حل مسئله تا پروژهٔ عملی

بازگشت یعنی تعریف پاسخ یک مسئله با کمک پاسخ همان نوع مسئله روی ورودی کوچک‌تر. در درس تابع، مسئله را به چند کار جدا شکستیم؛ اینجا یکی از آن کارها دوباره همان تابع را صدا می‌زند. تصور کنید برای شمردن پوشه‌ها، شمار پوشهٔ فعلی را با شمار زیرپوشه‌ها ترکیب می‌کنید. این توصیف فقط وقتی برنامهٔ معناداری می‌شود که برای پوشهٔ بدون زیرپوشه پاسخ روشن داشته باشیم و مسیر پیمایش هم بی‌پایان نچرخد. هدف این درس تشخیص همین دو تعهد است، نه کوتاه‌کردن کد به هر قیمت.

شرط پایه و گام کاهشی، دو سؤال مستقل‌اند

شرط پایه حالتی است که پاسخ آن بدون فراخوانی تازه معلوم است. گام بازگشتی باید ورودی را به آن حالت نزدیک کند. برای فاکتوریل، حاصل ضرب عددهای یک تا n را می‌خواهیم و قرارداد ریاضی صفر فاکتوریل را یک می‌گیرد. پس پاسخ صفر مستقیم است و برای n مثبت می‌توان n را در پاسخ n−1 ضرب کرد. این تعریف برای منفی‌ها برنامهٔ درستی نمی‌سازد؛ پیش از اجرا دامنه را مشخص می‌کنیم. در این مثال، تنها عدد صحیح صفر تا هجده پذیرفته می‌شود تا خروجی در محدودهٔ عدد صحیح امن JavaScript بماند.

شبه‌کد زیر برابری شرط را از نسبت‌دادن مقدار جدا می‌کند. RETURN اجرای همان فراخوانی را تمام می‌کند؛ نتیجه به فراخواننده برمی‌گردد و الزاماً پایان کل برنامه نیست. اگر n مثبت باشد، ضرب تا برگشت پاسخِ مسئلهٔ کوچک‌تر منتظر می‌ماند. بنابراین «رسیدن به صفر» فقط نیمهٔ مسیر اجراست؛ نیمهٔ دیگر بازشدن فراخوانی‌های منتظر و ساخت پاسخ نهایی است. این تفاوت را هنگام رسم ردگیری به‌وضوح نشان دهید.

FACTORIAL(n)
    REQUIRE n is an integer and 0 <= n <= 18
    IF n = 0 THEN RETURN 1
    RETURN n * FACTORIAL(n - 1)

مثال اول؛ فاکتوریل ۴ در مسیر رفت و برگشت

اجرای ۴ ابتدا به ۳، سپس ۲، سپس ۱ و سرانجام صفر می‌رسد. در آن لحظه هنوز جواب ۴ آماده نیست. صفر یک برمی‌گرداند؛ فراخوانیِ ۱ حاصل یک را می‌سازد، فراخوانیِ ۲ حاصل دو، فراخوانیِ ۳ حاصل شش و فراخوانیِ ۴ حاصل بیست‌وچهار را تحویل می‌دهد. متغیر محلی هر فراخوانی متعلق به همان اجرای تابع است؛ مقدار k در قاب ۴ با مقدار k در قاب ۲ یک خانهٔ متغیر مشترک نیست.

Going down:  F(4) -> F(3) -> F(2) -> F(1) -> F(0)
Coming back: F(0)=1; F(1)=1; F(2)=2; F(3)=6; F(4)=24
Deepest point: 5 active visit calls, 4 waiting multiplications

فایل 10-factorial.mjs را مستقل با Node.js ۲۴ اجرا کنید. دو پیاده‌سازی پاسخ یکسانی دارند، اما شیوهٔ نگهداری کارِ باقی‌مانده متفاوت است. نگهبان checkN قبل از ورود به تابع داخلی، خطای نوع و محدوده را رد می‌کند. پنج ورودی نامعتبر نیز عمداً آزمایش شده‌اند. در نسخهٔ حلقه‌ای، آغاز حاصل از یک انتخاب هویتی ضرب است؛ آغاز از صفر همهٔ پاسخ‌های مثبت را صفر می‌کند. آزمایش همهٔ عددهای این دامنه، تطابق این دو پیاده‌سازی را بررسی می‌کند.

import assert from 'node:assert/strict';

function checkN(n) {
  if (!Number.isInteger(n) || n < 0 || n > 18) {
    throw new RangeError('n must be an integer in 0..18');
  }
}
function factorialRecursive(n) {
  checkN(n);
  function visit(k) {
    if (k === 0) return 1;
    return k * visit(k - 1);
  }
  return visit(n);
}
function factorialLoop(n) {
  checkN(n);
  let result = 1;
  for (let k = 2; k <= n; k += 1) result *= k;
  return result;
}
for (let n = 0; n <= 18; n += 1) {
  assert.equal(factorialRecursive(n), factorialLoop(n));
  assert.ok(Number.isSafeInteger(factorialRecursive(n)));
}
for (const input of [-1, 1.5, 19, '4', NaN]) {
  assert.throws(() => factorialRecursive(input), RangeError);
}
console.log(factorialRecursive(0));
console.log(factorialRecursive(4));
console.log(factorialLoop(18));

خروجی سه خط به‌ترتیب 1، 24 و 6402373705728000 است. سقف هجده یک محدودیت قراردادی برای این مثال است؛ نباید از آن نتیجه گرفت که نوزده فاکتوریل از نظر ریاضی تعریف ندارد. Number.isSafeInteger دربارهٔ نمایش عدد در محیط اجرا حرف می‌زند. برای دامنهٔ بزرگ‌تر باید نمایش عدد و سیاست هزینه را دوباره انتخاب کرد. از سوی دیگر، قبول یک عدد بسیار بزرگ و امید به خاتمهٔ فراخوانی‌ها، حتی با نوع عدد مناسب، روش مناسبی برای برنامهٔ تعاملی نیست.

پشتهٔ فراخوانی؛ کارهای نیمه‌تمام کجا می‌مانند؟

پشته را می‌توان مجموعه‌ای از قاب‌های اجرای فعال دید که آخرین قاب افزوده‌شده، زودتر پاسخ می‌دهد. قاب معمولاً اطلاعات لازم برای ادامهٔ همان فراخوانی را نگه می‌دارد. در فاکتوریل بازگشتی، بعد از برگشت تابع داخلی هنوز یک ضرب باقی مانده است؛ پس قاب قبلی باید زنده بماند. در مدل متعارف، عمق این مثال با n رشد می‌کند. اندازهٔ دقیق هر قاب و بیشترین عمق مجاز به موتور و شرایط اجرا وابسته است؛ عدد ثابت و قابل اتکایی برای همهٔ مرورگرها و Node.js اعلام نمی‌کنیم.

خطای Maximum call stack size exceeded می‌تواند از نبود شرط پایه یا از عمق بیش از ظرفیت محیط بیاید. این دو علت یکسان نیستند: الگوریتمی ممکن است از نظر منطقی خاتمه داشته باشد ولی پیش از رسیدن به پاسخ، ظرفیت پشته را تمام کند. راه‌حل همیشه زیادکردن ظرفیت نیست؛ گاهی حلقه یا پشتهٔ دادهٔ صریح مناسب‌تر است. همچنین بهینه‌سازی فراخوانی انتهایی را برای همهٔ محیط‌های JavaScript تضمین نکنید. تصمیم عملی را بر رفتار محیط هدف و آزمایش ورودی‌های مجاز بنا کنید.

مثال دوم؛ اقلیدس بازگشتی و دلیل خاتمه

در درس هفتم، بزرگ‌ترین مقسوم‌علیه مشترک را با حلقه ساختیم. همان رابطه را می‌توان بازگشتی نوشت: اگر مؤلفهٔ دوم صفر باشد، اولی پاسخ است؛ در غیر این صورت، مسئله به زوجِ مؤلفهٔ دوم و باقیماندهٔ تقسیم تبدیل می‌شود. برای ۴۸ و ۱۸ زوج‌ها به‌ترتیب (۴۸،۱۸)، (۱۸،۱۲)، (۱۲،۶) و (۶،۰) هستند. از گام دارای مقسوم‌علیه مثبت، باقیمانده همواره کوچک‌تر از آن است. پس یک اندازهٔ صحیح غیرمنفی داریم که به‌سوی صفر پایین می‌آید.

import assert from 'node:assert/strict';

function gcdRecursive(a, b) {
  if (![a, b].every(value => Number.isSafeInteger(value) && value >= 0)) {
    throw new RangeError('Expected nonnegative safe integers');
  }
  if (a === 0 && b === 0) throw new RangeError('gcd(0, 0) is excluded');
  function visit(x, y) {
    if (y === 0) return x;
    return visit(y, x % y);
  }
  return visit(a, b);
}
assert.equal(gcdRecursive(48, 18), 6);
assert.equal(gcdRecursive(18, 48), 6);
assert.equal(gcdRecursive(0, 18), 18);
assert.equal(gcdRecursive(18, 0), 18);
assert.equal(gcdRecursive(17, 13), 1);
assert.throws(() => gcdRecursive(0, 0), RangeError);
assert.throws(() => gcdRecursive(-1, 2), RangeError);
assert.throws(() => gcdRecursive(3.5, 2), RangeError);
console.log(gcdRecursive(48, 18));
console.log(gcdRecursive(0, 18));

این فایل مستقل، ابتدا 6 و سپس 18 چاپ می‌کند. ورودی‌های صفر و هجده پذیرفته‌اند، اما زوج صفر و صفر مطابق قرارداد همین دوره رد می‌شود. این تصمیم باید با نسخهٔ حلقه‌ای درس هفتم یکسان بماند. تابع داخلی فقط زمانی عمل باقیمانده را اجرا می‌کند که y صفر نباشد؛ جابه‌جاکردن این ترتیب می‌تواند قبل از رسیدن به شرط پایه، مقدار نامعتبر بسازد. برای بازنویسی بازگشتی، قرارداد را همراه کد منتقل کنید، نه فقط سطر تکرار را.

بازگشت را چه وقت انتخاب کنیم؟

ساختارهای تو در تو مانند درخت پوشه، عبارت‌های حسابی یا تصمیم‌های شاخه‌ای معمولاً توصیف بازگشتی طبیعی دارند. برای جمع‌زدن یک فهرست تخت، حلقه اغلب روشن‌تر است. پیش از انتخاب، از خود بپرسید مسئلهٔ کوچک‌تر چیست، چند بار تکرار می‌شود و برای ادامه چه چیزی باید نگه داشته شود. بازگشت به‌خودی‌خود زمان را بهتر نمی‌کند؛ حتی ممکن است زیرمسئله‌های یکسان را بارها محاسبه کند. در این درس عمداً مثال کندِ رشدنمایی را روی ورودی بزرگ اجرا نمی‌کنیم.

برای دیباگ، هر فراخوانی را با ورودی و نتیجه روی کاغذ بنویسید و بیش از دو یا سه گامِ رفت را بدون نمایش برگشت رها نکنید. اگر خروجی نادرست است، ابتدا پاسخ شرط پایه را بررسی کنید؛ اگر پاسخ نمی‌رسد، کاهش اندازهٔ ورودی را وارسی کنید. در محیط اجرا می‌توانید breakpoint را روی شرط پایه بگذارید و پشته را ببینید. مدخل‌های #function و #return برای نحو کمک می‌کنند، اما توضیح علت خاتمه باید مستقل از نحو زبان قابل بیان باشد.

سه نمونه‌سؤال با پاسخ تشریحی

سؤال 1: فاکتوریل بازگشتی ۴ چند بار visit را اجرا می‌کند؟ تفاوت تعداد فراخوانی و تعداد ضرب چیست؟

پاسخ: فراخوانی‌ها برای ۴، ۳، ۲، ۱ و صفر رخ می‌دهند؛ پس پنج فراخوانی داریم. در صفر، عدد یک بی‌ضرب برمی‌گردد و چهار ضرب در مسیر بازگشت انجام می‌شود. شمارش فقط چهار دستور returnِ ضرب‌دار، تعداد قاب‌های زنده در عمیق‌ترین نقطه را نشان نمی‌دهد. برای n در همین تعریف، n+1 فراخوانی و n ضرب داریم؛ نگهبان ورودی یک بار بیرون تابع داخلی اجرا می‌شود.

سؤال 2: اگر در اقلیدس، visit(y, x % y) را با visit(y, x) جایگزین کنیم، برای ورودی ۴۸ و ۱۸ چه می‌شود؟

پاسخ: زوج‌ها بین (۴۸،۱۸) و (۱۸،۴۸) رفت‌وبرگشت می‌کنند و هیچ‌گاه مؤلفهٔ دوم صفر نمی‌شود. شرط پایه در متن تابع وجود دارد، اما ورودی به آن نزدیک نمی‌شود. بنابراین وجود شرط پایه به‌تنهایی اثبات خاتمه نیست. باقیمانده برای y مثبت، غیرمنفی و کوچک‌تر از y است؛ همین کم‌شدن، بخش گمشدهٔ استدلال نسخهٔ خراب است. نسخهٔ خراب را برای دیدن خطا اجرا نکنید؛ دو گام ردگیری برای نشان‌دادن مشکل کافی است.

سؤال 3: آیا حذف متغیر result از نسخهٔ بازگشتی به معنی مصرف حافظهٔ کمتر است؟ نسخهٔ حلقه‌ای را چگونه ارزیابی می‌کنید؟

پاسخ: خیر؛ هر فراخوانی بازگشتی فاکتوریل باید مقدار k و محل ادامهٔ ضرب را تا برگشت نگه دارد. با مدل رایج پشته، فضای کمکی آن متناسب با n است. نسخهٔ حلقه‌ای یک حاصل و شمارنده نگه می‌دارد و فضای کمکی ثابت دارد. هر دو نسخه در مدل ضرب با اندازهٔ ثابت، زمان خطی دارند. این مقایسه دربارهٔ خانوادهٔ ورودی‌هاست؛ سقف ۱۸ برای دقت اجرای Number در مثال گذاشته شده است، نه برای تعریف نظری فاکتوریل.

معیار تحویل: دو فایل را اجرا کنید، ردگیری فاکتوریل ۴ و اقلیدس ۴۸/۱۸ را بدون اجرا توضیح دهید و یک ورودی نامجاز برای هر قرارداد بنویسید. سپس نسخهٔ حلقه‌ای و بازگشتی را از نظر نتیجه، خاتمه و فضای کمکی مقایسه کنید. اگر فقط خروجیِ مثال را حفظ کرده‌اید، تمرین را با عددهای دیگری تکرار کنید. برای بحث کامل مدل هزینه و فرق اندازهٔ ورودی با مقدار عدد، درس پیش‌نیاز هزینهٔ اجرای کد را بخوانید: https://www.darsavand.com/resources/javascript-runtime-cost-complexity

منابع بررسی و مطالعهٔ بیشتر

Princeton — Recursion: https://introcs.cs.princeton.edu/java/23recursion/
MDN — Too much recursion: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Errors/Too_much_recursion
MDN — Number.isSafeInteger: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/isSafeInteger
تألیف مستقل، مثال‌ها و پاسخ‌ها: تحریریه درس‌آوند. منابع برای بررسی مفهوم و رفتار محیط معرفی شده‌اند؛ متن و تمرین‌ها ترجمهٔ جزوهٔ خارجی نیستند.

فایل مثال‌ها، راهنمای فارسی اجرا و عیب‌یابی، پروژهٔ گزارش نمره‌ها و آزمون جمع‌بندی تألیفی با پاسخ تشریحی، رایگان در صفحهٔ بستهٔ تمرین همین دوره ارائه می‌شود:
https://www.darsavand.com/resources/computer-algorithms-practice-kit
تألیف و مثال‌های اختصاصی: تحریریه درس‌آوند.