تابع بازگشتی چیست و چگونه آن را در زبان PHP پیاده‌سازی کنیم؟

Recursive Function (تابع بازگشتی) الگوریتمی در توسعهٔ نرم‌افزار است که بر آن اساس داخل یک تابعِ خاص دستور/دستوراتی وجود دارد که همان تابع را فراخوانی می‌کند و روی همین حساب لقب بازگشتی به آن داده شده است چرا که تابع مذکور دائماً خود را فراخوانی می‌کند تا زمانی که شرط خاصی برآورده شود.

پیاده‌سازی فاکتوریل در زبان پی‌اچ‌پی
مثالی کلاسیک در زمینهٔ‌ توابع بازگشتی فاکتوریل است به طوری که این مفهوم ریاضیاتی حاصل‌ضرب تمامی اعداد مثبت کوچک‌تر از یک عدد است که به صورت !n نشان داده می‌شود که در اینجا n یک عدد طبیعی است به طوری که برای مثال داریم:

5! = 5 × 4 × 3 × 2 × 1 = 120

در واقع، برای محاسبهٔ‌ فاکتوریل عدد ۵ آن‌قدر اعداد را طبق فرمول فوق از چپ به راست در یکدیگر ضرب می‌کنیم تا دیگر عددی باقی نماند. برای درک بهتر موضوع، فاکتوریل فوق را می‌توانیم به صورت زیر ساده‌سازی کنیم:

5 × 4 = 20
20 × 3 = 60
60 × 2 = 120
120 × 1 = 120

در واقع،‌ می‌بینیم که عمل ضرب به صورت تکراری (بازگشتی) انجام می‌شود تا به جواب نهایی برسیم. حال اگر بخواهیم در زبان پی‌اچ‌پی تابعی بازگشتی بنویسیم که فاکتوریل را برای‌مان محاسبه کند، خواهیم داشت:

function factorial($number) { 
    // Base case
    if ($number == 0) { 
        return 1; 
    } else { 
        // Recursive Case
        return ($number * factorial($number - 1)); 
    } 
}

echo factorial(5); // return 120

در تفسیر کد فوق باید گفت که ابتدا فانکشنی تعریف کرده‌ایم تحت عنوان ()fantorial که یک پارامتر ورودی تحت عنوان number$ می‌گیرد که باید عددی صحیح باشد. داخل این فانکشن یک شرط گذاشته‌ایم مبنی بر اینکه اگر مقدار متغیر number$ برابر با ۰ بود، خروجی ۱ ریترن شود و در غیر این صورت مقدار متغیر number$ در (factorial($number - 1 یا به عبارتی خودِ‌ این فانکشن ضرب شود اما این در حالی است که یک واحد از مقدار متغیر number$ کم شده است. به عبارتی داریم:

factorial(5) 
   factorial(4) 
      factorial(3) 
         factorial(2) 
            factorial(1) 
               return 1 
            return 2*1 = 2 
         return 3*2 = 6 
      return 4*6 = 24 
   return 5*24 = 120

اگر بخواهیم سازوکار الگوریتم فوق را به صورت شهودی‌تر ببینیم، می‌توانیم فانکشن فوق را به صورت زیر ریفکتور کنیم:

function factorial($number) {
    // Base case
    if ($number == 0) {
      echo "Base case: (\$number  = 0) which returns 1<br>";
      return 1;
    }
    // Recursive Case
    $result = ($number * factorial($number - 1));
    echo "Result of $number * factorial(" . ($number - 1) . ") = $result<br>";
    return $result;
  }
   
  echo "The factorial of 5 is: " . factorial(5);

که به عنوان خروجی خواهیم داشت:

Base case: ($number = 0) which returns 1
Result of 1 * factorial(0) = 1
Result of 2 * factorial(1) = 2
Result of 3 * factorial(2) = 6
Result of 4 * factorial(3) = 24
Result of 5 * factorial(4) = 120
The factorial of 5 is: 120

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

$menu = [
    'signin',
    'singup',
    'pages' => [
        'about',
        'contact',
    ],
    'modules' => [
        'forum',
        'tutorials'
    ],
    'logout',
];

همان‌طور که ملاحظه می‌شود، آرایه‌ای داریم تحت عنوان menu$ که شامل دو نوع اِلِمان مختلف است. دستهٔ اول آن‌هایی هستند که زیرشاخه ندارد (همچون singnin و logout) و دستهٔ دوم هم آن‌هایی هستند که خودشان آرایه‌اند (مثل pages و modules) که بدین ترتیب با یک آرایهٔ چندبُعدی سروکار خواهیم داشت. حال فاکنشنی تحت عنوان ()menuGenerator می‌نویسیم که وظیفه دارد تا یک پارامتر ورودی گرفته و آن را به یک منوی چندلایهٔ اچ‌تی‌ام‌ال مبدل سازد:

function menuGenerator($menuItems)
{
    $htmlWrapper;
    foreach($menuItems as $category => $item) {
        $htmlWrapper .= "<li>" . (is_array($item) ? $category . menuGenerator($item) : $item) . "</li>";
    }
    return "<ul>$htmlWrapper</ul>";
}

echo menuGenerator($menu);

اگر این بلوک کد را در فایلی ذخیره کرده و آرایه‌ای که قبلاً تعریف کردیم را به عنوان پارامتر ورودی به آن پاس دهیم، با خروجی زیر مواجه خواهیم شد:

-signin
-singup
-pages
--about
--contact
-modules
--forum
--tutorials
-logout

در تفسر تابع بازگشتی فوق باید گفت که این تابع یک پارامتر ورودی به نام menuItems$ می‌گیرد که باید از جنس آرایه باشد. داخل این فانکشن متغیری تعریف کرده‌ایم تحت عنوان htmlWrapper$ که مسئول ذخیره‌سازی خروجی اچ‌تی‌ام‌ال منوی مد نظر است. سپس با استفاده از یک حلقه menuItems$ را به اندیس‌ها و مقادیر متناظرشان تفکیک می‌کنیم که این کار به ترتیب با استفاده از متغیرهای category$ و item$ عملی شده است.

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

function menuGenerator($menuItems)
{
    foreach($menuItems as $category => $item) {
        echo $category . '<br>';
    }
}

menuGenerator($menu);

اکنون به عنوان خروجی خواهیم داشت:

0
1
pages
modules
2

می‌بینیم که در اِلِمان‌هایی مثل signin که زیرشاخه ندارند اندیس ۰ است ولو این که در آرایه درج نشده باشد اما آن‌هایی که خود آرایه هستند، مثل pages، به عنوان اندیس در نظر گرفته شده‌اند. 

حال با بازگرداندن تابع به حالت قبل، مجدد به تفسر کدها می‌پردازیم. داخل حلقه پس از نام متغیر htmlWrapper$ از علائم =. استفاده نموده‌ایم که بدین معنا است در هر بار چرخش حلقه، مقادیر جدید به مقادیر قبلی این متغیر اصطلاحاً Concat (ضمیمه) شوند. مقداری هم که برای این متغیر در نظر گرفته‌ایم تگ‌های آغازین و پایانی <li></li> است که با استفاده از یک دستور شرطی، مابین آن‌ها را پُر کرده‌ایم (جهت آشنایی با این نوع ساختار دستورات شرطی، به آموزش آشنایی با اپراتور Null Coalesce در PHP نسخهٔ ۷ مراجعه نمایید.)

در واقع، با استفاده از این دستور شرطی و فانکشن ()is_array گفته‌ایم که اگر تایپِ متغیر item$ آرایه بود، (category . menuGenerator($item$ چاپ شود و در غیر این صورت مقدار مرتبط با item$ داخل تگ‌های لیست قرار گیرد و در نهایت هم متغیر htmlWrapper$ را داخل تگ‌های <ul></ul> قرار داده و خروجی را ریترن کرده‌ایم.

آنچه در اینجا بسیار حائز اهمیت است، درک نحوهٔ کارکرد دستور (category . menuGenerator($item$ می‌باشد زیرا همان‌طور که ملاحظه می‌شود می‌بینیم که فانکشنِ ()menuGenerator را داخل خودِ این فانکشن کال (فراخوانی) کرده‌ایم و این دقیقاً مفهوم تابع بازگشتی را می‌رساند. 

در حقیقت، در این بشخ از فانکشن مذکور گفته‌ایم که اگر متغیر item$ یک آرایه بود اندیس اِلِمان مذکور، که در اینجا داخل متغیر category$ قرار دارد، چاپ شود به طوری که در مثال فوق اندیس‌های pages و modules چاپ می‌شوند سپس این مقادیر با استفاده از علامت . با (menuGenerator($item کانکت شوند؛ به عبارتی، از آنجا که item$ حاوی یک آرایه است، مجدد به عنوان پارامتر ورودی به فانکشن ()menuGenerator پاس داده می‌شود و در این نقطه از اجرای برنامه، این فانکشن مجدد خودش را صدا می‌زند (صدا زدن خودِ‌ فانکشن توسط خودش آن‌قدر ادامه می‌یابد تا متغیر item$ دیگر آرایه نباشد.)

چنانچه بخواهیم فانکشن ریکرسیو فوق را به شکل دیگری بنویسیم، خواهیم داشت:

function menuGenerator($menuItems)
{
    $htmlWrapper;
    foreach($menuItems as $category => $item) {
        if (is_array($item)) {
            $htmlWrapper .= "<li>" . $category . menuGenerator($item) . "</li>";
        }
        $htmlWrapper .= "<li>" . $item . "</li>";
    }
    return "<ul>$htmlWrapper</ul>";
}

در حقیقت،‌ داخل این حلقه با استفاده از دستور if آرایه بودن item$ را چک کرده‌ایم بدین ترتیب که اگر آرایه بود، دستورات داخل شرط اجرا می‌شوند که مشابه کد قبلی است و چنانچه آرایه نبود، مقدار item$ به متغیر htmlWrapper$ اختصاص می‌یابد. با این تفاسیر، چنانچه کد فوق را اجرا کنیم، با خروجی زیر مواجه خواهیم شد:

-signin
-singup
-pages
--about
--contact
Array 
-modules
--forum
--tutorials
Array
-logout

خروجی بلوک فوق تا حد زیادی مشابه فانکشن قبلی است با این تفاوت که دو بار استرینگ Array نیز در خلال سایر آیتم‌ها چاپ شده است که برای رفع این مشکل، کدهای فوق را به صورت زیر تغییر می‌دهیم:

function menuGenerator($menuItems)
{
    $htmlWrapper;
    foreach($menuItems as $category => $item) {
        if (is_array($item)) {
            $htmlWrapper .= "<li>" . $category . menuGenerator($item) . "</li>";
            continue;
        }
        $htmlWrapper .= "<li>" . $item . "</li>";
    }
    return "<ul>$htmlWrapper</ul>";
}

با خروجی گرفتن مجدد خواهیم داشت:

-signin
-singup
-pages
--about
--contact
-modules
--forum
--tutorials
-logout

در واقع،‌ تنها تغییری که صورت گرفت افزودن کیورد continue داخل بلوک شرط بود. کاری که این کیورد انجام می‌دهد این است که روند اجرای برنامه را به ابتدای حلقه بازمی‌گرداند و ادامهٔ کدهای اجرا نخواهند شد. پیش از این وقتی که این دستور را درج نکرده بودیم، نوع متغیر item$ که یک Array است در بخش "<li>" . $item . "</li>"  همچون مواردی که این متغیر آرایه نیست چاپ می‌شود اما پس از درج continue حلقه دیگر ادامه پیدا نمی‌کند.

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

- Recursive Function چیست و چگونه یک تابع بازگشتی با استفاده از JS پیاده‌سازی کنیم؟
- آشنایی با مفهوم Recursive Function و نحوۀ پیاده‌سازی آن در زبان برنامه‌نویسی پایتون
- Recursive Function چیست و چگونه آن را در زبان جاوا پیاده‌سازی کنیم؟

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