-----
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: