توابع بازگشتی در سی‌پلاس‌پلاس

در این مطلب، با یک مفهوم اساسی برنامه‌نویسی آشنا می‌شویم: توابع بازگشتی، این توابع برای حل مسائلی که به تکرار یک فرایند نیاز دارند و یا مسائلی که به راحتی به بخش‌های کوچکتر تقسیم می‌شوند کاربری هستند. اما قبل شروع، باید یک نکته در رابطه با توابع را بررسی کنیم.

در مقاله قبلی، تابعی نوشتیم که بیشترین مقدار در یک آرایه را پیدا می‌کرد. اگرچه این تابع با ورودی‌های معتبر به‌خوبی کار می‌کرد، اما در برخورد با آرایه‌های خالی دچار مشکل می‌شد.

وقتی یک آرایه خالی به عنوان آرایه ورودی ارسال می‌شود، تابع همچنان تلاش می‌کند تا به اولین عنصر (arr[0]) دسترسی پیدا کند، و چون این عنصر در آرایه ما وجود ندارد، تلاش برای دسترسی به آن منجر به انجام رفتارهای غیر منتظره از برنامه ما شود. ممکن است برنامه به مکانی در حافظه دسترسی پیدا کند که به برنامه یا سرویس دیگری تعلق دارد و در نتیجه، مقادیر ناخواسته و نامربوط به برنامه ما را بخواند.

زبان ++C، برای ایجاد یک آرایه خالی (int arr[] = {};) هیچ حافظه‌ای اشغال نمی‌کند اما آرایه همچنان به یک آدرس در حافظه اشاره می‌کند که فضایی در آن برای ما اختصاص داده نشده.

دسترسی به arr[0] خانه‌ای از حافظه را می‌خواند که متعلق به آرایه ما نبوده و اصطلاحا خارج از محدوده مربوط به آن (Out of bound) قرار دارد. بسیاری از مواقع این خانه‌ها شامل مقادیری هستند که پروسه‌های دیگر در کامپیوتر در آن مکان قرار داده‌اند.

#include <iostream>

using namespace std;

int max(int[], int);

int main() {
  int arr[] = {  };
  cout << max(arr, 0) << endl;
}

int max(int arr[], int len) {
  int max = arr[0];
  for (int i = 1; i < len; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

412567

راه‌حل: اعتبارسنجی ورودی

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

int max(int arr[], int len) {
  if (len != 0) {
    int max = arr[0];
    for (int i = 1; i < len; i++) {
      if (arr[i] > max) {
        max = arr[i];
      }
    }
    return max;
  } else {
    return -1;
  }
}

اما، این روش انتخاب مرتبی نیست، چون منطق اصلی را به داخل عبارت if منتقل می‌کند که منجر به تو در تو شدن بیشتر و پیچیدگی کد می‌شود.

راه‌حل بهتر این است که در صورتی که آرایه خالی باشد، بلافاصله -1 برگردانیم و جلوی اجرای کد اصلی را بگیریم. return نه تنها مقداری را به فراخواننده برمی‌گرداند، بلکه شبیه به break در حلقه‌ها عمل می‌کند و فوراً اجرای تابع را متوقف می‌کند.

این روش کد را ساده‌تر و مرتب‌تر می‌کند، زیرا تودرتویی حاصل از اضافه کردن بلوک if را حذف کرده و اطمینان می‌دهد که تابع فقط برای ورودی‌های معتبر اجرا می‌شود.

int max(int arr[], int len) {
  if (len == 0)
    return -1;
  int max = arr[0];
  for (int i = 1; i < len; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

در اینجا، تابع به محض تشخیص شرط نامعتبر (len == 0) خاتمه می‌یابد و تضمین می‌کند که بقیه کد فقط برای ورودی‌های معتبر اجرا شود.

حالا که این نکته در مورد توابع و return را بررسی کردیم، به موضوع اصلی خود یعنی توابع بازگشتی (Recursion) برمی‌گردیم.

به توابعی بازگشتی می‌گوییم که خودشان را اجرا می‌کنند و ارجاع و یا یک call به خودشان دارند. این توابع در شرایطی که مساله قابل تقسیم به بخش‌های کوچک‌تر مشابه به هم هست، کاربردی هستند.

برای مثال تصور کنید نیاز داریم برنامه‌ای بنویسیم که یک مستطیل را با استفاده از کاراکتر * ترسیم کند. مستطیل را می‌توان به صورت چند ردیف توصیف کرد که هر کدام شامل کاراکترهای * هستند.

برای حل این مسئله با استفاده از توابع بازگشتی:

1. ابتدا یک ردیف چاپ می‌کنیم.
2. سپس همان تابع را دوباره فراخوانی می‌کنیم و تعداد ردیف‌ها را یک عدد کاهش می‌دهیم (به عنوان ورودی rows-1 را ارسال می‌کنیم).
3. زمانی که تعداد ردیف‌ها به صفر رسید، ادامه اجرا تابع را متوقف می‌کنیم.

برای پیاده‌سازی این مسئله در کد، ابتدا تابعی تعریف می‌کنیم که دو پارامتر می‌گیرد: rows (تعداد ردیف‌هایی که باید چاپ شود) و cols (تعداد ستون‌ها در هر ردیف). ابتدا کد چاپ کردن یک خط ستاره را می‌نویسیم. از یک حلقه for استفاده می‌کنیم تا تعداد مورد نیاز (یعنی cols) ستاره را در یک خط چاپ کنیم. هر تکرار حلقه یک کاراکتر "*" تولید می‌کند و پس از پایان حلقه، یک خط جدید (\n) چاپ می‌کنیم تا به ردیف بعدی برویم. سپس فراخوانی بازگشتی را اضافه می‌کنیم. پس از چاپ خط، تابع را به صورت بازگشتی فراخوانی می‌کنیم اما مقدار rows را یک واحد کاهش می‌دهیم. این کار تضمین می‌کند که در فراخوانی‌های بعدی، تابع می‌داند ردیف‌های کمتری برای چاپ کردن باقی مانده است. در نهایت، برای جلوگیری از تکرار نامتناهی این روند، یک شرط if به عنوان شرط توقف اضافه می‌کنیم. این شرط بررسی می‌کند که آیا تعداد rows برابر 0 است یا خیر، و اگر این‌گونه باشد، با استفاده از return تابع را زودتر متوقف کرده و به فرایند بازگشتی پایان می‌دهد. این شرط که تابع را متوقف می‌کند به عنوان base case شناخته می‌شود.

#include <iostream>

using namespace std;

void drawRectangle(int cols, int rows);

int main() {
    drawRectangle(3, 4);
}

void drawRectangle(int cols, int rows) {
    if (rows == 0) return;
    for (int i = 0; i < cols; i++) {
        cout << "*";
    }
    cout << endl;
    drawRectangle(cols, rows - 1);
}

مثال بعدی که به نوشتن آن می‌پردازیم، یک تابع بازگشتی خواهد بود که فاکتوریل یک عدد را حساب می‌کند.

فاکتوریل یک عدد که با نماد علامت تعجب (n!) نمایش داده می‌شود حاصل ضرب تمام اعداد صحیح(بدون اعشار) کوچکتر از آن عدد است، مثلا فاکتوریل ۵ معادل 5 × 4 × 3 × 2 × 1 که برابر با 120 است خواهد بود.

چرا توابع بازگشتی؟

فاکتوریل ذاتا یک مساله بازگشتی‌است چون هر فاکتوریل از جواب فاکتوریل قبلی آن قابل محاسبه است. برای مثال:

• 5! = 5×4!
• 4! = 4×3!
• 3! = 3×2!
• 2! = 2×1!
• نهایتا فاکتوریل 1! = 1 تعریف شده که بعدا به عنوان شرط خروج از حلقه بازگشتی یا base case از آن استفاده می‌کنم.

ابتدا یک تابع به اسم factorial تعریف می‌کنیم. این تابع یک پارامتر n به عنوان ورودی دریافت می‌کند که از نوع int خواهد بود و عددی‌است که قرار است فاکتوریل آن را حساب کنیم. تابع باید دو حالت را پوشش دهد، یکی حالتی که n معادل ۱ شده باشد (base case) که در این حالت، تابع باید مقدار ثابت ۱ را برگرداند و چرخه اجرای بازگشتی را که حالا به n = 1  رسیده متوقف کند.
و دیگری حالتی‌است که n عدد دیگری‌است که تابع باید n × factorial(n − 1) را بازگرداند. که یعنی تابع فاکتوریل n ضرب در عدد قبلی خودش را حساب می‌کند، این چرخه ادامه پیدا می‌کند تا به شرط پایه یا base case برسیم. وقتی این اتفاق بیفتد، فراخوانی‌های بازگشتی متوقف شده و تمام مقادیر در هم ضرب می‌شوند تا نتیجه نهایی فاکتوریل را پیدا کنند. مثلا برای 5! تابع اول 4! و بعد 3! و بعد 2! و نهایتا 1! را محاسبه می‌کند که زنجیره تکرار را قطع می‌کند و همه تابع ها به تابع قبلی‌شان باز می‌گردند تا نتیجه نهایی 5! = 5 × 4 × 3 × 2 × 1 = 120 را محاسبه کنند.

#include <iostream>

using namespace std;

int factorial(int n);

int main() {
    cout << factorial(5) << endl;
}

int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}

120

برای factorial(5) فرایند به صورت زیر طی خواهد شد:

1. factorial(5) → 5 * factorial(4)
2. factorial(4) → 4 * factorial(3)
3. factorial(3) → 3 * factorial(2)
4. factorial(2) → 2 * factorial(1)
5. factorial(1) → 1 (Base case)

بعد از این که مشخص کردیم فاکتوریل ۱ معادل یک است، می‌توانیم آن را در معادله قبل جای‌گذاری کنیم تا فاکتوریل ۲ یعنی ۲ ضرب در یک را به دست آوریم. حال که فاکتوریل ۲ را داریم می‌توانیم آن را در جمله سوم جایگزاری کنیم. توابع بازگشتی با چنین منطقی می‌توانند محاسبات خود را انجام دهند.

اگر ما یک دستور cout برای پرینت کردن فراخوانی‌های تابع factorial تعریف کنیم، تا مراحلی که این تابع برای پیدا کردن جواب طی می‌کند را ببینیم، خروجی به شکل زیر خواهد بود:

#include <iostream>

using namespace std;

int factorial(int n);

int main() {
    cout << factorial(5) << endl;
}

int factorial(int n) {
    if (n == 1) {
        cout << "factorial(1)      " << 1 << endl;
        return 1;
    }
    int r = n * factorial(n - 1);
    cout << "factorial(" << n << ")      " << r << endl;
    return r;
}

factorial(1)      1
factorial(2)      2
factorial(3)      6
factorial(4)      24
factorial(5)      120
120

یک بار مثال‌ها را امتحان کنید و خود را برای قسمت بعدی دوره که در آن راجع به اسکوپ‌ها، حافظه استک و مشکلات توابع بازگشتی (recursive functions) صحبت خواهیم کرد، آماده کنید.