PHP Recursive function

PHP তে Recursive function কি?

function যখন নিজেই নিজেকে কল করে বা যখন function নিজের মধ্যেই নিজেকে কল করে , PHP অথবা যেকোনো Programming Language এর পরিভাষায় একে বলা হয় Recursive Function বা Recursion. নিচের উদাহরণ দেখুন

:

<?php
function recursion($a)
{
    if ($a <=10) {
        echo "$a\n";
        recursion($a + 1);
    }
}
recursion(5);  //Result: 5,6,7,8,9,10
?>

ব্যাখ্যা : লক্ষ্য করুন recursion function টি একটি condition true না হওয়া পর্যন্ত নিজেই নিজেকে কল করছে।

Note: তবে recursive function সব সময় একটা condition এর মধ্যে আটকানো থাকতে হয়, অন্যথা function টি infinite বা অন্যন্ত সময় পর্যন্ত run করতে থাকবে, এবং compile error দেখাবে।

Zend Certified PHP Engineering (ZCPE) Course

চলুন এবার একটা recursive function তৈরী করি যেটা আমাদেরকে একটা পূর্ণাঙ্গ সংখ্যার factorial বের করে দিবে।
একটি সংখ্যার ফ্যাক্টরিয়াল(factorial) হলো সংখ্যাটির সমান বা তার থেকে ছোটো সকল ধণাত্মক পূর্ণসংখ্যার গূণফল, n এর ফ্যাক্টরিয়ালকে “n!” দ্বারা প্রকাশ করা হয়, যেমন- n!=n*(n-1)*(n-2)*(n-3)….1*2*3

উদাহরণস্বরূপ:5!=5*4*3*2*1=120

<?php
// recursive function
// to calculate factorial
function calcFactorial($num) {
    // define variable to hold product
    static $product = 1;
    // recurse until $num becomes 1
    if ($num > 1) {
        $product = $product * $num;
        $num--;
        calcFactorial($num);
    }
return $product;
}
// result: "Factorial of 5 is 120"
echo "Factorial of 5 is " . calcFactorial(5);
?>

PHP তে Recursive Function আমরা কোথায় ব্যবহার করতে পারি ?

PHP-তে Recursive function গুলি, অন্যান্য অনেক programming languages এর মতো, বিভিন্ন problem solving করতে ব্যবহৃত হয় যা smaller, similar subproblems গুলিতে বিভক্ত করা যেতে পারে। এগুলি এমন পরিস্থিতিতে বিশেষভাবে কার্যকর যেখানে একটি নির্দিষ্ট শর্ত পূরণ না হওয়া পর্যন্ত একটি ফাংশন বারবার একটি কাজ সম্পাদন করতে নিজেকে কল করতে পারে। এখানে কিছু common scenarios এবং area রয়েছে যেখানে PHP-তে recursive functions ব্যবহার করা যেতে পারে:

১. File and Directory Operations:

file systems এবং directory গুলির সাথে কাজ করার সময়, আপনি directory structures traverse করতে, ফাইল গুলি তালিকাভুক্ত করতে এবং ডিরেক্টরিগুলির মধ্যে ফাইল বা ডিরেক্টরিগুলিতে বিভিন্ন অপারেশন সম্পাদন করতে recursive functions ব্যবহার করতে পারেন।

ধরা যাক আপনি এমন একটি PHP script তৈরি করতে চাচ্ছেন যা একটি নির্দিষ্ট file extension (যেমন, “.txt”) একটি directory এবং এর subdirectories গুলির মধ্যে সমস্ত ফাইল খুঁজে বের করবে ৷ আপনি এই কাজটি সম্পন্ন করতে একটি recursive function ব্যবহার করতে পারেন। এখানে একটি বাস্তব উদাহরণ দেওয়া হলো:

<?php
function searchFiles($directory, $extension) {
    $files = [];

    // Open the directory
    $handle = opendir($directory);

    // Loop through the directory contents
    while (false !== ($file = readdir($handle))) {
        if ($file != "." && $file != "..") {
            $filePath = $directory . '/' . $file;

            // If it's a directory, recursively search it
            if (is_dir($filePath)) {
                $subdirectoryFiles = searchFiles($filePath, $extension);
                $files = array_merge($files, $subdirectoryFiles);
            } else {
                // Check if the file has the desired extension
                if (pathinfo($file, PATHINFO_EXTENSION) == $extension) {
                    $files[] = $filePath;
                }
            }
        }
    }

    // Close the directory handle
    closedir($handle);

    return $files;
}

$directory = 'D:\software';
$extension = 'txt';

$foundFiles = searchFiles($directory, $extension);

// Now, $foundFiles contains an array of all ".txt" files within the directory and its subdirectories.

print_r($foundFiles);

এই উদাহরণে:

• ১. searchFiles ফাংশন একটি directory এবং এর subdirectory এর মধ্যে একটি নির্দিষ্ট extension সহ ফাইলগুলি অনুসন্ধান করার জন্য ডিফাইন করা হয়।
• ২. এটি directory টি opening এর মাধ্যমে এবং readdir ব্যবহার করে এর কন্টেন্টস এর মধ্যে iterating করে।
• ৩. ডিরেক্টরির প্রতিটি item এর জন্য, এটি নিজেই একটি ডিরেক্টরি কিনা তা চেক করে। যদি এটি directory হয়, এটি সেই সাবডিরেক্টরির মধ্যে ফাইলগুলি অনুসন্ধান করার জন্য searchFiles ফাংশনটিকে recursively কল করে।
• ৪. যদি এটি একটি directory না হয়, তাহলে এটি পরীক্ষা করে যে ফাইলটিতে কাঙ্খিত এক্সটেনশন আছে কিনা (এই ক্ষেত্রে, “.txt”), এবং যদি তাই হয়, এটি $files অ্যারেতে ফাইলের path যোগ করে।
• ৫. ডিরেক্টরির সমস্ত item প্রসেস করার পরে, ফাংশনটি directory এবং এর subdirectory এর মধ্যে পাওয়া নির্দিষ্ট এক্সটেনশন সহ সমস্ত ফাইলের পাথ ধারণকারী একটি অ্যারে রিটার্ন করে।

এই বাস্তব উদাহরণটি থেকে আমরা দেখতে পাই যে কীভাবে ফাইল এবং ডিরেক্টরির অপারেশন্স এর জন্য recursive functions গুলি directory structures গুলিকে traverse করতে এবং সাবডিরেক্টরিগুলি সহ তাদের মধ্যে ফাইলগুলিকে তালিকাভুক্ত করতে ব্যবহার করা যেতে পারে।

২. Mathematical Calculations:

Recursive functions গুলি সিকোয়েন্স বা সিরিজ জড়িত mathematical calculations এর জন্য ব্যবহার করা যেতে পারে, যেমন Fibonacci sequence বা factorial calculations ইত্যাদি।

যেহেতু আমরা ইতিপূর্বে Factorial নিয়ে আলোচনা করেছি। চলুন এবার আমরা Fibonacci Series করি:

প্রথমে জেনে নেওয়া যাক Fibonacci series কি?

Fibonacci series হল সংখ্যার একটি mathematical sequence যা 0 এবং 1 দিয়ে শুরু হয়, যেখানে sequence এর প্রতিটি পরবর্তী সংখ্যাটি পূর্ববর্তী দুটি সংখ্যার যোগফল। অন্য কথায়, সিরিজের প্রতিটি সংখ্যা তার আগে দুটি সংখ্যা যোগ করার ফলাফল। sequence টি সাধারণত নিম্নরূপ শুরু হয়:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

এখানে দেখানো হলো কিভাবে Fibonacci Series তৈরি হয়:

• প্রথম দুটি সংখ্যা দিয়ে শুরু করুন: 0 এবং 1
• তৃতীয় সংখ্যাটি পেতে, প্রথম দুটি সংখ্যা যোগ করুন: 0 + 1 = 1
• চতুর্থ সংখ্যা খুঁজে পেতে, দ্বিতীয় এবং তৃতীয় সংখ্যা যোগ করুন: 1 + 1 = 2
• এই প্রক্রিয়াটি চালিয়ে যান, সর্বদা ক্রমানুসারে পরবর্তী সংখ্যা তৈরি করতে পূর্ববর্তী দুটি সংখ্যা যোগ করুন।

function fibonacci($n) {
    if ($n <= 0) {
        return 0;
    } elseif ($n == 1) {
        return 1;
    } else {
        return fibonacci($n - 1) + fibonacci($n - 2);
    }
}

// Generate and print the first 10 Fibonacci numbers
for ($i = 0; $i < 10; $i++) {
    echo fibonacci($i) . " ";
}

Output

0 1 1 2 3 5 8 13 21 34

৩. Tree Data Structures:

tree এর মতো ডেটা স্ট্রাকচার (যেমন, binary trees, JSON objects) নিয়ে কাজ করার সময়, রিকার্সিভ ফাংশনগুলি প্রায়ই এই স্ট্রাকচারগুলিকে traverse করতে, search করতে বা modify করতে ব্যবহৃত হয়।

একটি menu এবং sub-menu structure সিস্টেম tree data structures ব্যবহারের একটি চমৎকার উদাহরণ হতে পারে। এই উদাহরণে, আমরা tree data structures এবং recursion ব্যবহার করে sub-menus সহ একটি menu system তৈরি বাস্তবায়ন করব।

<?php 
// Suppress warnings
error_reporting(E_ERROR | E_PARSE);

// Flat array of menu items with parent IDs
$menuItems = [
    ['id' => 1, 'label' => 'Home', 'url' => '/'],
    ['id' => 2, 'label' => 'Products', 'url' => '/products', 'parent_id' => null],
    ['id' => 3, 'label' => 'Product 1', 'url' => '/products/1', 'parent_id' => 2],
    ['id' => 4, 'label' => 'Product 2', 'url' => '/products/2', 'parent_id' => 2],
    ['id' => 5, 'label' => 'Detail 1.1', 'url' => '/products/1/detail/1', 'parent_id' => 3],
    ['id' => 6, 'label' => 'Detail 1.2', 'url' => '/products/1/detail/2', 'parent_id' => 3],
    ['id' => 7, 'label' => 'Sub-detail 1.2.1', 'url' => '/products/1/detail/2/subdetail/1', 'parent_id' => 6],
    ['id' => 8, 'label' => 'Sub-detail 1.2.2', 'url' => '/products/1/detail/2/subdetail/2', 'parent_id' => 6],
    ['id' => 9, 'label' => 'About', 'url' => '/about', 'parent_id' => null],
    ['id' => 10, 'label' => 'Contact', 'url' => '/contact', 'parent_id' => null],
];

// Function to convert flat array to hierarchical menu
function buildMenu($items, $parentId = null) {
    $menu = [];
    foreach ($items as $item) {
        if ($item['parent_id'] == $parentId) {
            $submenu = buildMenu($items, $item['id']);
            if (!empty($submenu)) {
                $item['submenu'] = $submenu;
            }
            $menu[] = $item;
        }
    }
    return $menu;
}

// Call the function to build the hierarchical menu
$hierarchicalMenu = buildMenu($menuItems, null);

// Function to generate HTML for the menu
function generateMenuHtml($menuItems) {
    echo '<ul>';
    foreach ($menuItems as $menuItem) {
        echo '<li>';
        echo '<a href="' . $menuItem['url'] . '">' . $menuItem['label'] . '</a>';
        
        // Recursively generate sub-menus if they exist
        if (!empty($menuItem['submenu'])) {
            generateMenuHtml($menuItem['submenu']);
        }
        
        echo '</li>';
    }
    echo '</ul>';
}

// Generate and display the menu
generateMenuHtml($hierarchicalMenu);

এই উদাহরণে:

• আমরা মেনু আইটেমগুলির একটি flat array ব্যবহার করি যেখানে প্রতিটি আইটেমের একটি id, label, url এবং parent_id রয়েছে।
• buildMenu ফাংশন recursively parent_id field দ্বারা নির্দিষ্ট করা parent-child relationships এর উপর ভিত্তি করে একটি hierarchical menu structure তৈরি করে।
• generateMenuHtml ফাংশনটি hierarchical menu structure এর জন্য HTML তৈরি করতে ব্যবহৃত হয়।
• ফলস্বরূপ মেনু hierarchically organized হয় এবং সহজেই তৈরি এবং প্রদর্শিত হতে পারে।

এবার চলুন একটা Employee Database এর employee দের তাদের রিপোর্টিং বস এর উপর ভিত্তি করে একটি ট্রি সাজাই।

<?php
$employees = array(
  array('id' => '1002','lastName' => 'Murphy','firstName' => 'Diane','reportsTo' => NULL,'jobTitle' => 'President'),
  array('id' => '1056','lastName' => 'Patterson','firstName' => 'Mary','reportsTo' => '1002','jobTitle' => 'VP Sales'),
  array('id' => '1076','lastName' => 'Firrelli','firstName' => 'Jeff','reportsTo' => '1002','jobTitle' => 'VP Marketing'),
  array('id' => '1088','lastName' => 'Patterson','firstName' => 'William','reportsTo' => '1056','jobTitle' => 'Sales Manager (APAC)'),
  array('id' => '1102','lastName' => 'Bondur','firstName' => 'Gerard','reportsTo' => '1056','jobTitle' => 'Sale Manager (EMEA)'),
  array('id' => '1501','lastName' => 'Bott','firstName' => 'Larry','reportsTo' => '1102','jobTitle' => 'Sales Rep'),
  array('id' => '1504','lastName' => 'Jones','firstName' => 'Barry','reportsTo' => '1102','jobTitle' => 'Sales Rep'),
  array('id' => '1611','lastName' => 'Fixter','firstName' => 'Andy','reportsTo' => '1088','jobTitle' => 'Sales Rep'),
  array('id' => '1612','lastName' => 'Marsh','firstName' => 'Peter','reportsTo' => '1088','jobTitle' => 'Sales Rep'),
  array('id' => '1619','lastName' => 'King','firstName' => 'Tom','reportsTo' => '1088','jobTitle' => 'Sales Rep'),
  array('id' => '1621','lastName' => 'Nishi','firstName' => 'Mami','reportsTo' => '1056','jobTitle' => 'Sales Rep'),
  array('id' => '1625','lastName' => 'Kato','firstName' => 'Yoshimi','reportsTo' => '1621','jobTitle' => 'Sales Rep'),
);

// Function to build a nested list structure
function buildNestedList($employees, $managerId = null) {
  $html = '<ul>';
  foreach ($employees as $employee) {
      if ($employee['reportsTo'] == $managerId) {
          $html .= '<li>' . $employee['lastName'] . ', ' . $employee['firstName'].'('.$employee['jobTitle'].')';
          $subordinates = buildNestedList($employees, $employee['id']);
          if (!empty($subordinates)) {
              $html .= $subordinates;
          }
          $html .= '</li>';
      }
  }
  $html .= '</ul>';
  return $html;
}

// Build the nested list starting from the top-level manager (President)
$orgList = buildNestedList($employees);

// Print the nested list
echo $orgList;
?>

এই কোডটি একটি buildTree function ফাংশনকে সংজ্ঞায়িত করে যা রিপোর্টের সাথে সম্পর্কগুলির উপর ভিত্তি করে recursively tree structure তৈরি করে। এটি top-level manager (President) দিয়ে শুরু হয় এবং প্রতিটি level এ subordinates যোগ করে। printTree function টি tree structure কে একটি hierarchical format এ প্রিন্ট করতে ব্যবহৃত হয়।

৪. Sorting and Searching:

Recursive algorithms যেমন QuickSort এবং binary search এ recursive functions ব্যবহার করে প্রয়োগ করা যেতে পারে।

QuickSort দিয়ে উদাহরণ:

QuickSort হল একটি popular এবং efficient sorting algorithm যা array থেকে একটি “pivot” element নির্বাচন করে এবং অন্যান্য element গুলিকে দুটি sub-arrays তে partitioning অর্থাৎ বিভাজন করে কাজ করে, সেগুলি pivot এর চেয়ে ছোট বা বড় কিনা তা অনুসারে। পুরো অ্যারে সাজানো না হওয়া পর্যন্ত প্রক্রিয়াটি সাব-অ্যারেতে recursively প্রয়োগ করা হয়।

পিএইচপি-তে একটি recursive function ব্যবহার করে বাস্তবায়িত QuickSort অ্যালগরিদমের বাস্তব উদাহরণ এখানে। ধরা যাক আপনার কাছে এমন একটি সংখ্যা রয়েছে যা আপনি ascending order এ সাজাতে চান:

<?php
function quickSort($arr)
{
    $length = count($arr);
    
    // Base case: If the array has 0 or 1 elements, it's already sorted
    if ($length <= 1) {
        return $arr;
    }
    
    // Choose a pivot element (for simplicity, we'll just use the first element)
    $pivot = $arr[0];
    
    // Initialize arrays to hold elements less than and greater than the pivot
    $left = $right = [];
    
    // Partition the array into two sub-arrays
    for ($i = 1; $i < $length; $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    
    // Recursively sort the sub-arrays and combine them with the pivot
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

// Example usage:
$unsortedArray = [3, 6, 8, 10, 1, 2, 1];
$sortedArray = quickSort($unsortedArray);
print_r($sortedArray);

$unsortedNames = ["Alice", "Bob", "Eve", "David", "Carol"];
$sortedNames = quickSort($unsortedNames);

foreach ($sortedNames as $name) {
    echo $name . "\n";
}

এই উদাহরণে, QuickSort function ইনপুট হিসাবে একটি array নেয় এবং QuickSort অ্যালগরিদম ব্যবহার করে recursively sort করে। base case অ্যারেতে 0 বা 1 element আছে কিনা তা চেক করে, যে ক্ষেত্রে এটি সাজানো বলে বিবেচিত হয়। অন্যথায়, এটি একটি pivot element সিলেক্ট করে, array টিকে pivot এর চেয়ে ছোট এবং বড় element গুলিতে partitions অর্থাৎ বিভাজন করে এবং সাব-অ্যারেগুলিকে recursively sorts করে। ফাইনাল্লি , এটি sorted sub-array এবং pivot কে একত্রিত করে fully sorted array তৈরি করে।

আপনি যখন এই কোডটি $unsortedArray দিয়ে রান করবেন, তখন এটি element গুলিকে ascending order এ বাছাই করবে এবং print_r($sortedArray) ফাঙ্কশন টি একটি sorted array তে প্রদর্শন করবে।

binary search দিয়ে উদাহরণ:

binary search হল একটি search algorithm যা একটি sorted collection এর মধ্যে একটি target element খুঁজে পেতে ব্যবহৃত হয়, যেমন একটি array বা list। এটি একটি দক্ষ অ্যালগরিদম যা বারবার search space কে অর্ধেক ভাগ করে কাজ করে যতক্ষণ না target element টি পাওয়া যায় বা এটি নির্ধারণ করা হয় যে element টি collection এ উপস্থিত নেই।

Binary Search অত্যন্ত দক্ষ কারণ এটি প্রতিটি ধাপে অবশিষ্ট element গুলির অর্ধেককে সরিয়ে দেয়।

Binary search সাধারণত এমন পরিস্থিতিতে ব্যবহার করা হয় যেখানে একটি sorted collection থেকে দ্রুত ডেটা বের করে আনা প্রয়োজন, যেমন একটি sorted list আইটেমগুলির জন্য অনুসন্ধান করা, index কৃত কলামগুলির সাথে ডাটাবেসে elements গুলির জন্য অনুসন্ধান করা, বা একটি ফোনবুকে নির্দিষ্ট value গুলি সন্ধান করা। যাইহোক, এটি লক্ষ্য করা গুরুত্বপূর্ণ যে binary search এর জন্য collection টিকে ascending (বা descending) ক্রমে সাজানো প্রয়োজন যাতে এটি সঠিকভাবে কাজ করে।

এখানে binary search সাধারণত কিভাবে কাজ করে তা আলোচনা করা হলো:

• সম্পূর্ণ sorted collection দিয়ে শুরু করে।
• current search space এর middle element কে ক্যালকুলেট করে।
• target element এর সাথে middle element টির তুলনা করে:
  • যদি তারা match করে, search সফল হয়, এবং target element এর index এ ফিরে আসে।
  • যদি middle element টি target element চেয়ে বড় হয়, current search space এর বাম অর্ধেকের search process টি repeat করে ।
  • যদি middle element টি target এর চেয়ে ছোট হয়, current search space ডান অর্ধেকের search process টি repeat করে।
• টার্গেট এলিমেন্ট না পাওয়া পর্যন্ত বা সার্চ স্পেস খালি না হওয়া পর্যন্ত ধাপ 2 এবং 3 রিপিট করতে থাকে

PHP -তে recursive function ব্যবহার করে binary search এর একটি বাস্তব উদাহরণ হল একটি sorted dictionary বা word list একটি নির্দিষ্ট word অনুসন্ধান করা। ধরা যাক আপনার কাছে word গুলোর একটি ডিক্শনারি আছে, এবং আপনি নির্ধারণ করতে চান যে একটি প্রদত্ত word এতে বিদ্যমান কিনা।

এই ধরণের সিনারিওর জন্য binary search এর একটি উদাহরণ এখানে দেওয়া হলো:

<?php
function binarySearchRecursive($dictionary, $target, $left, $right)
{
    // Base case: If the left index is greater than the right index, the word is not in the dictionary
    if ($left > $right) {
        return false;
    }

    // Calculate the middle index
    $mid = floor(($left + $right) / 2);

    // If the middle word is the target, return true
    if ($dictionary[$mid] === $target) {
        return true;
    }

    // If the target word is less than the middle word, search the left half
    if (strcmp($dictionary[$mid], $target) > 0) {
        return binarySearchRecursive($dictionary, $target, $left, $mid - 1);
    }

    // If the target word is greater than the middle word, search the right half
    return binarySearchRecursive($dictionary, $target, $mid + 1, $right);
}

// Example usage:
$dictionary = [
    "apple", "banana", "cherry", "grape", "lemon", "lime", "orange", "strawberry"
];
$targetWord = "cherry";

// Perform a binary search
$result = binarySearchRecursive($dictionary, $targetWord, 0, count($dictionary) - 1);

if ($result) {
    echo "The word '$targetWord' was found in the dictionary.";
} else {
    echo "The word '$targetWord' was not found in the dictionary.";
}

এই উদাহরণে, binarySearchRecursive ফাংশন একটি sorted array $dictionary, একটি টার্গেট শব্দ $target এবং বর্তমান সার্চ ইন্টারভালের left এবং right indix গুলি নেয়। এটি strcmp ব্যবহার করে target word এর সাথে middle word এর compare করে একটি binary search করে।

base case চেক করে যে left index টি right index এর চেয়ে বড় কিনা, এটি নির্দেশ করে যে শব্দটি dictionary তে নেই। যদি middle word টি target এর সাথে মেলে তবে এটি true রিটার্ন করে। অন্যথায়, এটি শব্দের alphabetical order অনুসারে dictionary এর left বা right অর্ধেক recursively search করে।

আপনি যখন এই কোডটি $dictionary array এবং $targetWord দিয়ে রান করবেন, তখন এটি হয় প্রদর্শন করবে যে টার্গেট শব্দটি dictionary তে পাওয়া গেছে বা এটি খুঁজে পাওয়া যায়নি।

৫. Data Processing and Transformation:

XML বা JSON documents এর মতো hierarchical বা nested data structures কে রূপান্তর এবং প্রসেস করতে রিকার্সিভ ফাংশন ব্যবহার করা যেতে পারে।

উদাহরণ ১:

আসুন JSON ডেটার সাথে ডেটা processing এবং transformation এর জন্য recursive functions ব্যবহার করার একটি বাস্তব উদাহরণ বিবেচনা করি।

সমস্যা: ধরুন আপনি একটি ওয়েবসাইটের জন্য একটি content management system তৈরি করবেন, এর জন্য আপনাকে একটি site map তৈরি করতে হবে যা আপনার ওয়েবসাইটের সমস্ত পেজ গুলিকে একটি hierarchical structure এ লিস্টেড করবে৷ আপনার ওয়েবসাইটের content একটি nested JSON ফরম্যাটে সংরক্ষিত আছে, যেখানে প্রতিটি পেজের সাবপেজ থাকতে পারে।

সমাধান: আপনি JSON ডেটা traverse করতে এবং একটি site map তৈরি করতে একটি recursive function ব্যবহার করতে পারেন।

<?php

// Sample JSON data representing website structure
$websiteData = [
    "page" => "Home",
    "subpages" => [
        [
            "page" => "About",
            "subpages" => [
                [
                    "page" => "Team",
                    "subpages" => []
                ],
                [
                    "page" => "History",
                    "subpages" => []
                ]
            ]
        ],
        [
            "page" => "Services",
            "subpages" => [
                [
                    "page" => "Web Design",
                    "subpages" => []
                ],
                [
                    "page" => "SEO",
                    "subpages" => []
                ]
            ]
        ]
    ]
];

// Recursive function to generate a site map
function generateSiteMap($pageData, $depth = 0) {
    $indentation = str_repeat("  ", $depth);
    echo $indentation . $pageData["page"] . "\n";

    foreach ($pageData["subpages"] as $subpage) {
        generateSiteMap($subpage, $depth + 1);
    }
}

// Call the recursive function to generate the site map
generateSiteMap($websiteData);
?>

এই PHP code টি generateSiteMap নামের recursive function ডিফাইন করা হয়েছে যা নেস্টেড JSON ডেটা প্রসেস করে এবং ওয়েবসাইটের hierarchical structure কে রিপ্রেজেন্ট করার জন্য সঠিক ইন্ডেন্টেশন সহ একটি সাইট ম্যাপ তৈরি করে।

উদাহরণ ২:

PHP-তে ডেটা প্রসেসিং এবং ট্রান্সফর্মেশনের জন্য recursive functions ব্যবহার করার আরও advanced একটি উদাহরণ:

সমস্যা: কল্পনা করুন আপনি একটি ই-কমার্স প্ল্যাটফর্ম তৈরি করছেন, এবং আপনাকে একটি শপিং কার্টের total price calculate করতে হবে যাতে products এবং sub-carts (nested shopping carts) উভয়ই রয়েছে। প্রতিটি প্রোডাক্টের একটি মূল্য রয়েছে এবং প্রতিটি sub-cart এর নিজস্ব items এবং sub-cart রয়েছে।

সমাধান: আপনি nested shopping cart ডেটা traverse করতে এবং total price calculate করতে একটি recursive function ব্যবহার করতে পারেন।

<?php

// Sample shopping cart data
$shoppingCart = [
    [
        "type" => "product",
        "name" => "Product A",
        "price" => 10.99
    ],
    [
        "type" => "product",
        "name" => "Product B",
        "price" => 15.99
    ],
    [
        "type" => "cart",
        "name" => "Sub-Cart 1",
        "items" => [
            [
                "type" => "product",
                "name" => "Product C",
                "price" => 5.99
            ],
            [
                "type" => "product",
                "name" => "Product D",
                "price" => 8.99
            ],
        ]
    ],
    [
        "type" => "cart",
        "name" => "Sub-Cart 2",
        "items" => [
            [
                "type" => "product",
                "name" => "Product E",
                "price" => 12.99
            ],
        ]
    ],
];

// Recursive function to calculate the total price
function calculateTotalPrice($cart) {
    $total = 0;

    foreach ($cart as $item) {
        if ($item["type"] === "product") {
            $total += $item["price"];
        } elseif ($item["type"] === "cart" && isset($item["items"])) {
            // Recursively calculate the total price of sub-carts
            $total += calculateTotalPrice($item["items"]);
        }
    }

    return $total;
}

// Calculate the total price of the shopping cart
$totalPrice = calculateTotalPrice($shoppingCart);
echo "Total Price: $" . number_format($totalPrice, 2);
?>

এই উদাহরণে, calculateTotalPrice function recursively শপিং কার্ট ডেটা প্রসেস করে, products এবং sub-carts উভয়ই হ্যান্ডেল করে। এটি প্রতিটি প্রোডাক্টের total price এবং sub-carts এর total price recursively ক্যালকুলেট করে recursively সংগ্রহ করে। এটি data processing এবং transformation এর জন্য recursive functions গুলির একটি advanced use case.

উদাহরণ ৩:

সমস্যা: ধরুন আপনি একটি content management system নিয়ে কাজ করছেন, এবং আপনাকে একটি ফীচার বাস্তবায়ন করতে হবে যা একটি দীর্ঘ আর্টিকেলের জন্য table of contents (TOC) তৈরি করতে হবে। আর্টিকেলটির sections, subsections এবং sub-subsections সহ একটি hierarchical structure হিসাবে সংরক্ষণ করা হয়। আপনি একটি TOC তৈরি করতে চান যা এই hierarchy কে প্রতিফলিত করে এবং আর্টিকেলের প্রতিটি সেক্শনে লিঙ্ক তৈরি করে।

সমাধান: আপনি একটি recursive function ব্যবহার করে hierarchical article ডেটা traverse করতে পারেন এবং উপযুক্ত ইন্ডেন্টেশন এবং লিঙ্ক সহ কন্টেন্টের একটি TOC তৈরি করতে পারেন।

<?php

// Sample hierarchical article data
$articleData = [
    [
        "title" => "Introduction",
        "content" => "This is the introduction section.",
        "subsections" => [
            [
                "title" => "Purpose",
                "content" => "The purpose of this article is...",
                "subsections" => []
            ],
            [
                "title" => "Scope",
                "content" => "The scope of this article includes...",
                "subsections" => []
            ]
        ]
    ],
    [
        "title" => "Main Section",
        "content" => "This is the main section of the article.",
        "subsections" => [
            [
                "title" => "Subsection 1",
                "content" => "Content of subsection 1.",
                "subsections" => []
            ],
            [
                "title" => "Subsection 2",
                "content" => "Content of subsection 2.",
                "subsections" => []
            ]
        ]
    ]
];

// Recursive function to generate the table of contents
function generateTableOfContents($sections, $depth = 0) {
    $toc = "";

    foreach ($sections as $section) {
        $indentation = str_repeat("  ", $depth);
        $link = "#" . strtolower(str_replace(" ", "-", $section["title"]));
        $toc .= $indentation . "<a href=\"$link\">" . $section["title"] . "</a>\n";

        if (!empty($section["subsections"])) {
            $toc .= generateTableOfContents($section["subsections"], $depth + 1);
        }
    }

    return $toc;
}

// Generate the table of contents
$toc = generateTableOfContents($articleData);

// Output the table of contents
echo "<h2>Table of Contents</h2>\n";
echo "<ul>\n";
echo $toc;
echo "</ul>\n";
?>

এই উদাহরণে, generateTableOfContents ফাংশনটি recursively hierarchical article data প্রসেস করে এবং উপযুক্ত ইন্ডেন্টেশন এবং আর্টিকেলের প্রতিটি সেক্শনে লিঙ্ক সহ কন্টেন্টের একটি table of contents (TOC) তৈরি করে। এটি ডেটা প্রসেসিং এবং ট্রান্সফর্মেশনের জন্য recursive functions গুলির একটি আরও advanced ব্যবহারের ক্ষেত্রে, বিশেষ করে দীর্ঘ আর্টিকেল গুলির জন্য dynamic TOC তৈরির জন্য দরকারী।

৬. Graph Algorithms:

Graph traversal algorithms, যেমন depth-first search (DFS) বা breadth-first search (BFS) এ , Recursive Function প্রয়োগ করা যেতে পারে।

প্রথমে জেনে নেওয়া যাক depth-first search (DFS) কি?

Depth-First Search (DFS) হল একটি graph traversal algorithm যা graph বা tree ডেটা স্ট্রাকচারের মাধ্যমে search এবং নেভিগেট করতে ব্যবহৃত হয়। এটি root node থেকে শুরু হয় এবং ব্যাকট্র্যাক করার আগে প্রতিটি শাখা বরাবর যতদূর সম্ভব search করে। recursion বা stack data structure ব্যবহার করে DFS প্রয়োগ করা যেতে পারে।

উদাহরণ ১:

চলুন একটি বাস্তব উদাহরণ বিবেচনা করা যাক যেখানে আপনার একটি file system আছে, এবং আপনি DFS ব্যবহার করে directory structure কে recursively একটি নির্দিষ্ট এক্সটেনশন (যেমন, “.txt”) সহ সমস্ত ফাইল খুঁজে পেতে চান৷

<?php

// Function to perform DFS on the file system
function searchFilesDFS($directory, $extension) {
    $result = [];

    // Open the directory
    $files = scandir($directory);

    foreach ($files as $file) {
        if ($file !== '.' && $file !== '..') {
            $path = $directory . '/' . $file;

            if (is_dir($path)) {
                // If it's a directory, recursively search inside
                $result = array_merge($result, searchFilesDFS($path, $extension));
            } else {
                // If it's a file, check the extension
                if (pathinfo($file, PATHINFO_EXTENSION) === $extension) {
                    $result[] = $path;
                }
            }
        }
    }

    return $result;
}

// Specify the root directory and the target file extension
$rootDirectory = 'D:\software'; //Please write here your own directory path
$targetExtension = 'txt';

// Call the DFS function to search for files
$foundFiles = searchFilesDFS($rootDirectory, $targetExtension);

// Display the found files
if (!empty($foundFiles)) {
    echo "Found files with the '.$targetExtension' extension:\n";
    foreach ($foundFiles as $file) {
        echo $file . "\n";
    }
} else {
    echo "No files with the '.$targetExtension' extension found.";
}
?>

এই উদাহরণে, searchFilesDFS function ফাংশনটি রুট ডিরেক্টরি থেকে শুরু করে ফাইল সিস্টেমকে recursively traverse করে। এটি প্রতিটি ডিরেক্টরি এবং ফাইল অন্বেষণ করে, তাদের এক্সটেনশনগুলি পরীক্ষা করে এবং নির্দিষ্ট এক্সটেনশনের সাথে ফাইলগুলির পাথ সংগ্রহ করে। এটি একটি directory structure এ নির্দিষ্ট ফাইলগুলি অনুসন্ধান করতে DFS-এর একটি বাস্তব ব্যবহার।

উদাহরণ ২:

সমস্যা: ধরুন আপনি route planning এর জন্য একটি ওয়েব অ্যাপ্লিকেশন তৈরি করছেন, এবং আপনি বিভিন্ন interconnected route সহ একটি map দুটি অবস্থানের মধ্যে shortest path টি খুঁজে পেতে চান। আপনার কাছে ম্যাপের প্রতিনিধিত্বকারী একটি গ্রাফ রয়েছে এবং দুটি অবস্থানের মধ্যে shortest route খুঁজে পেতে আপনাকে একটি DFS অ্যালগরিদম প্রয়োগ করতে হবে।

সমাধান: ম্যাপের দুটি অবস্থানের মধ্যে সবচেয়ে shortest path খুঁজে পেতে আপনি একটি DFS অ্যালগরিদম প্রয়োগ করতে পারেন।

<?php

// Sample map represented as an adjacency list graph
$map = [
    "A" => ["B", "C"],
    "B" => ["A", "D", "E"],
    "C" => ["A", "F"],
    "D" => ["B", "G"],
    "E" => ["B", "H"],
    "F" => ["C"],
    "G" => ["D", "H"],
    "H" => ["E", "G"],
];

// Function to find the shortest path using DFS
function findShortestPathDFS($graph, $start, $end, $path = []) {
    $path[] = $start;

    if ($start == $end) {
        return $path;
    }

    $shortestPath = null;

    foreach ($graph[$start] as $neighbor) {
        if (!in_array($neighbor, $path)) {
            $newPath = findShortestPathDFS($graph, $neighbor, $end, $path);
            if ($newPath && (!$shortestPath || count($newPath) < count($shortestPath))) {
                $shortestPath = $newPath;
            }
        }
    }

    return $shortestPath;
}

// Specify the start and end locations
$startLocation = "A";
$endLocation = "H";

// Find the shortest path using DFS
$shortestPath = findShortestPathDFS($map, $startLocation, $endLocation);

// Display the shortest path
if ($shortestPath !== null) {
    echo "Shortest path from $startLocation to $endLocation: ";
    echo implode(" -> ", $shortestPath);
} else {
    echo "No path found from $startLocation to $endLocation.";
}
?>

এই উদাহরণে, findShortestPathDFS ফাংশন একটি গ্রাফ হিসাবে উপস্থাপিত ম্যাপে দুটি অবস্থানের মধ্যে সংক্ষিপ্ততম পথ খুঁজে পেতে একটি depth-first search (DFS) algorithm ব্যবহার করে৷ এটি recursively locations গুলির মধ্যে routes গুলি অন্বেষণ করে এবং পাওয়া shortest path টি রিটার্ন দেয়। এটি একটি map-based application এ route planning এর জন্য DFS-এর use case.

এবার জেনে নেওয়া যাক Breadth-First Search (BFS) কি?

Breadth-First Search (BFS) হল একটি graph traversal algorithm যা গ্রাফ বা ট্রি ডেটা স্ট্রাকচারের মাধ্যমে সার্চ এবং নেভিগেট করতে ব্যবহৃত হয়। Depth-First Search (DFS) এর বিপরীতে, যা ব্যাকট্র্যাক করার আগে একটি শাখা বরাবর যতদূর সম্ভব সার্চ করে, BFS পরবর্তী depth নোডগুলিতে যাওয়ার আগে current depth এর সমস্ত প্রতিবেশী নোডগুলি সার্চ করে। BFS সাধারণত একটি queue data structure ব্যবহার করে প্রয়োগ করা হয়।

উদাহরণ ১:

আসুন একটি বাস্তব উদাহরণ বিবেচনা করি যেখানে আপনি একটি পাতাল রেল ব্যবস্থায় দুটি অবস্থানের মধ্যে সবচেয়ে ছোট পথটি খুঁজে পেতে চান, যেখানে পাতাল রেল স্টেশনগুলি হল নোড এবং পাতাল রেল লাইনগুলি সংযোগকারী স্টেশনগুলি প্রান্ত৷ আপনি দুটি পাতাল রেল স্টেশনের মধ্যে সবচেয়ে ছোট পথ খুঁজে পেতে BFS ব্যবহার করতে পারেন।

<?php

// Sample subway system represented as an adjacency list graph
$subwaySystem = [
    "A" => ["B", "C"],
    "B" => ["A", "D", "E"],
    "C" => ["A", "F"],
    "D" => ["B", "G"],
    "E" => ["B", "H"],
    "F" => ["C"],
    "G" => ["D", "H"],
    "H" => ["E", "G"],
];

// Function to find the shortest path using BFS
function findShortestPathBFS($graph, $start, $end) {
    $queue = new SplQueue();
    $visited = [];
    $path = [];

    $queue->enqueue([$start]);

    while (!$queue->isEmpty()) {
        $currentPath = $queue->dequeue();
        $currentNode = end($currentPath);

        if ($currentNode == $end) {
            return $currentPath;
        }

        if (!isset($visited[$currentNode])) {
            $visited[$currentNode] = true;

            foreach ($graph[$currentNode] as $neighbor) {
                if (!isset($visited[$neighbor])) {
                    $newPath = $currentPath;
                    $newPath[] = $neighbor;
                    $queue->enqueue($newPath);
                }
            }
        }
    }

    return null;
}

// Specify the start and end subway stations
$startStation = "A";
$endStation = "H";

// Find the shortest path using BFS
$shortestPath = findShortestPathBFS($subwaySystem, $startStation, $endStation);

// Display the shortest path
if ($shortestPath !== null) {
    echo "Shortest path from $startStation to $endStation: ";
    echo implode(" -> ", $shortestPath);
} else {
    echo "No path found from $startStation to $endStation.";
}
?>

এই উদাহরণে, findShortestPathBFS ফাংশন একটি গ্রাফ হিসাবে উপস্থাপিত একটি পাতাল রেল সিস্টেমে দুটি সাবওয়ে স্টেশনের মধ্যে সংক্ষিপ্ততম পথ খুঁজে পেতে একটি breadth-first search (BFS) অ্যালগরিদম ব্যবহার করে। এটি সাবওয়ে লাইন এবং স্টেশনগুলি স্তরে স্তরে অন্বেষণ করে, এটি নিশ্চিত করে যে এটি দুটি নির্দিষ্ট স্টেশনের মধ্যে সবচেয়ে ছোট পথ খুঁজে পায়। এটি একটি সাবওয়ে সিস্টেমে রুট পরিকল্পনার জন্য BFS-এর একটি বাস্তব use case.

উদাহরণ ২:

সমস্যা: কল্পনা করুন আপনি একটি simple social network application, তৈরি করতে চাচ্ছেন এবং আপনি দুই ব্যবহারকারীর মধ্যে সবচেয়ে কম সংখ্যক friend connections খুঁজে পেতে চান। আপনার কাছে ব্যবহারকারীদের এবং তাদের friend connections গুলির একটি লিস্ট রয়েছে এবং আপনাকে দুই ব্যবহারকারীর মধ্যে friend connection এর shortest path খুঁজে পেতে BFS প্রয়োগ করতে হবে।

সমাধান: আপনি social network এ দুই ব্যবহারকারীর মধ্যে friend connections এর shortest path খুঁজে পেতে BFS প্রয়োগ করতে পারেন।

<?php

// Sample social network represented as a list of friends
$socialNetwork = [
    "Alice" => ["Bob", "Carol"],
    "Bob" => ["Alice", "David", "Eve"],
    "Carol" => ["Alice", "Eve"],
    "David" => ["Bob", "Grace"],
    "Eve" => ["Bob", "Carol"],
    "Grace" => ["David"],
];

// Function to find the shortest path of friend connections using BFS
function findShortestConnectionPath($graph, $start, $end) {
    $queue = new SplQueue();
    $visited = [];
    $path = [];

    $queue->enqueue([$start]);

    while (!$queue->isEmpty()) {
        $currentPath = $queue->dequeue();
        $currentNode = end($currentPath);

        if ($currentNode == $end) {
            return $currentPath;
        }

        if (!isset($visited[$currentNode])) {
            $visited[$currentNode] = true;

            foreach ($graph[$currentNode] as $friend) {
                if (!isset($visited[$friend])) {
                    $newPath = $currentPath;
                    $newPath[] = $friend;
                    $queue->enqueue($newPath);
                }
            }
        }
    }

    return null;
}

// Specify the start and end users
$startUser = "Alice";
$endUser = "Grace";

// Find the shortest connection path using BFS
$shortestPath = findShortestConnectionPath($socialNetwork, $startUser, $endUser);

// Display the shortest connection path
if ($shortestPath !== null) {
    echo "Shortest connection path between $startUser and $endUser: ";
    echo implode(" -> ", $shortestPath);
} else {
    echo "No connection path found between $startUser and $endUser.";
}
?>

এই উদাহরণে, findShortestConnectionPath ফাংশনটি একটি simple social network এ দুই ব্যবহারকারীর মধ্যে friend connections এর shortest path খুঁজে পেতে একটি breadth-first search (BFS) algorithm ব্যবহার করে। এটি friend connections গুলি স্তরে স্তরে সার্চ করে এবং পাওয়া shortest path টি রিটার্ন দেয়। এটি একটি social network এ friend connections খোঁজার জন্য BFS-এর একটি বাস্তব use case

৭. Problem Solving:

computer science এবং programming -এর অনেক প্রব্লেমই recursive পদ্ধতি ব্যবহার করে সুন্দরভাবে সমাধান করা যেতে পারে, যেমন Tower of Hanoi puzzle, permutations,এবং combinations generation এবং আরও অনেক কিছু।