Ngu ngơ học làm web (81) - Kỹ thuật đệ quy 1

Tiếp theo của: Ngu ngơ học làm web (80) - Bài tập xử lý tập tin 2
-----

Phần 81.       Kĩ thuật đệ quy 1


Đây là clip số 87:


Đệ quy (recursive): là sự lặp lại chính nó.

Hàm đệ quy là hàm gọi lại chính nó, lồng nhau liên tục, cho tới khi gặp điều kiện dừng.

function myFunction ($param1, $param2) {
    if ($param1 == $param2) { // điều kiện dừng hàm
      // trả về giá trị - kết thúc hàm
    } else {
      // gọi lại hàm myFunction ($param1, $param2)
    }
  }

Ví dụ, viết hàm tính n!

Với cách viết thông thường:

function giaiThua($n) {
    $result = 1;
    if ($n == 0 || $n == 1) {
      return $result;
    } else {
      for ($i = 2; $i <= $n; $i++) {
        $result = $result * $i;
      }
      return $result;
    }
  }

Viết lại theo kiểu đệ quy:

  function giaiThua($n) {
    $result = 1;
    if ($n == 0 || $n == 1) {
      return $result;
    } else {
      $result = $n * giaiThua($n - 1);
    }
    return $result;
  }

Hàm tính tổng từ 0 đến n, viết theo kiểu đệ quy:

  function tinhTong($n) {
    $result = 0;
    if ($n == 0) {
      return 0;
    } else {
      $result = $n + tinhTong($n -1);
    }
    return $result;
  }

Đây là clip số 88:


Sử dụng hàm đệ quy để tạo menu đa cấp.

Cho một menu đa cấp, lưu dưới dạng mảng như sau:

  $menu = array();
  $menu[] = array('id' => 1, 'name' => 'Home', 'parent' => 0);
  $menu[] = array('id' => 2, 'name' => 'About', 'parent' => 0);
  $menu[] = array('id' => 3, 'name' => 'News', 'parent' => 0);
  $menu[] = array('id' => 4, 'name' => 'Products', 'parent' => 0);
  $menu[] = array('id' => 5, 'name' => 'Contact', 'parent' => 0);
  $menu[] = array('id' => 6, 'name' => 'Tin trong nước', 'parent' => 3);
  $menu[] = array('id' => 7, 'name' => 'Tin quốc tế', 'parent' => 3);
  $menu[] = array('id' => 8, 'name' => 'Công nghệ', 'parent' => 6);
  $menu[] = array('id' => 9, 'name' => 'Giáo dục', 'parent' => 6);
  $menu[] = array('id' => 10, 'name' => 'Y tế', 'parent' => 6);
  $menu[] = array('id' => 11, 'name' => 'Education', 'parent' => 7);
  $menu[] = array('id' => 12, 'name' => 'Breaking news', 'parent' => 7);
  $menu[] = array('id' => 13, 'name' => 'Software', 'parent' => 4);

Mảng $menu gồm 13 phần tử, mỗi phần tử chứa ba thông tin, một là “id”, hai là “name” và ba là “id của menu mức cha nó”.

Việc tiếp theo là thêm thông tin về cấp của menu vào mỗi phần tử của mảng, để được kết quả như sau:

  $menu1 = array();
  $menu1[] = array('id' => 1, 'name' => 'Home', 'parents' => 0, 'level' => 1);
  $menu1[] = array('id' => 2, 'name' => 'About', 'parents' => 0, 'level' => 1);
  $menu1[] = array('id' => 3, 'name' => 'News', 'parents' => 0, 'level' => 1);
  $menu1[] = array('id' => 4, 'name' => 'Products', 'parents' => 0, 'level' => 1);
  $menu1[] = array('id' => 5, 'name' => 'Contact', 'parents' => 0, 'level' => 1);
  $menu1[] = array('id' => 6, 'name' => 'Tin trong nước', 'parents' => 3, 'level' => 2);
  $menu1[] = array('id' => 7, 'name' => 'Tin quốc tế', 'parents' => 3, 'level' => 2);
  $menu1[] = array('id' => 8, 'name' => 'Công nghệ', 'parents' => 6, 'level' => 3);
  $menu1[] = array('id' => 9, 'name' => 'Giáo dục', 'parents' => 6, 'level' => 3);
  $menu1[] = array('id' => 10, 'name' => 'Y tế', 'parents' => 6, 'level' => 3);
  $menu1[] = array('id' => 11, 'name' => 'Education', 'parents' => 7, 'level' => 3);
  $menu1[] = array('id' => 12, 'name' => 'Breaking news', 'parents' => 7, 'level' => 3);
  $menu1[] = array('id' => 13, 'name' => 'Software', 'parents' => 4, 'level' => 2);

Sau đó, sắp xếp lại mảng để các phần từ có mối liên hệ cha-con thì đặt cạnh nhau:

  $menu1 = array();
  $menu1[] = array('id' => 1, 'name' => 'Home', 'parent' => 0, 'level' => 1);
  $menu1[] = array('id' => 2, 'name' => 'About', 'parent' => 0, 'level' => 1);
  $menu1[] = array('id' => 3, 'name' => 'News', 'parent' => 0, 'level' => 1);
  $menu1[] = array('id' => 6, 'name' => 'Tin trong nước', 'parent' => 3, 'level' => 2);
  $menu1[] = array('id' => 8, 'name' => 'Công nghệ', 'parent' => 6, 'level' => 3);
  $menu1[] = array('id' => 9, 'name' => 'Giáo dục', 'parent' => 6, 'level' => 3);
  $menu1[] = array('id' => 10, 'name' => 'Y tế', 'parent' => 6, 'level' => 3);
  $menu1[] = array('id' => 7, 'name' => 'Tin quốc tế', 'parent' => 3, 'level' => 2);
  $menu1[] = array('id' => 11, 'name' => 'Education', 'parent' => 7, 'level' => 3);
  $menu1[] = array('id' => 12, 'name' => 'Breaking news', 'parent' => 7, 'level' => 3);
  $menu1[] = array('id' => 4, 'name' => 'Products', 'parent' => 0, 'level' => 1);
  $menu1[] = array('id' => 13, 'name' => 'Software', 'parent' => 4, 'level' => 2);
  $menu1[] = array('id' => 5, 'name' => 'Contact', 'parent' => 0, 'level' => 1);

Đây là clip số 89:


Đoạn mã thực hiện yêu cầu ở trên (không dùng kĩ thuật đệ quy):

  foreach ($menu as $key => $value) {
    if ($value['parent'] == 0) {
      $value['level'] = 1;
      $menu1[] = $value;
      unset($menu[$key]);

      $parent = $value['id'];
      foreach ($menu as $key1 => $value1) {
        if ($value1['parent'] == $parent) {
          $value1['level'] = $value['level'] + 1;
          $menu1[] = $value1;
          unset($menu[$key1]);

          $parent1 = $value1['id'];
          foreach ($menu as $key2 => $value2) {
            if ($value2['parent'] == $parent1) {
              $value2['level'] = $value1['level'] + 1;
              $menu1[] = $value2;
              unset($menu[$key2]);
            }
          }
        }
      }
    }
  }

// xuất menu
  foreach ($menu1 as $key => $value) {
    if ($value['level'] == 1) {
      echo '<div style="border: 1px solid #ccc;">+' . $value['name'] . '</div>';
    } else {
      $padding = ($value['level'] - 1) * 20;
      $padding = 'padding-left:' . $padding . 'px';
      echo '<div style="border: 1px solid #ccc;'. $padding . '">-' . $value['name'] . '</div>';
    }
  }

Viết lại đoạn mã ở trên (có dùng kĩ thuật đệ quy):

function deQuyLevel($array, $parent, $level, &$newArray) {
    // điều kiện dừng
    if (count($array) > 0) {
      foreach ($array as $key => $value) {
        if ($value['parent'] == $parent) {
          $value['level'] = $level;
          $newArray[] = $value;
          unset($array[$key]);
          $newParent = $value['id'];
          deQuyLevel($array, $newParent, $level + 1, $newArray);
        }
      }
    }
  }
  $menu1 = array();

  deQuyLevel($menu, 0, 1, $menu1);
-----------
Cập nhật [16/9/2020]
-----------
Xem thêm: