10/10/2018, 09:35
Cho em ví dụ về đệ quy
Có ai cho một ví dụ về đệ quy và khử đệ quy không, đơn giản thôi nhe. Và cho em thực tiển đệ quy để làm gì ạ . Có cách nào tránh xài đệ quy không ạ
Bài liên quan
Bất cứ bài toán nào giải quyết dc = iteration (em gọi bậy là xử lý tuần tự) thì đều có thể xử lý bằng đệ quy, và ngược lại.
Tùy vào loại bài toán mà hiện thực = đệ quy hay tuần tự sẽ ngắn hơn / chạy nhanh hơn.
Xử lý tuần tự thường dùng để xử lý những tác vụ có số lượng đã biết trc (giai thừa, dãy số,...)
Đệ quy thường dùng để xử lý các bài toán với tập hợp dữ liệu dạng cây, vd cây thư mục, cây cấu trúc trang web.
Lấy cây thư mục làm vd: một thư mục (~node) có thể chứa những thư mục (node) khác, hoặc chứa files (item). Thư mục cấp 0 thường dc gọi là root.
Do dạng cây thường phức tạp + số lượng không biết trc, nhưng cấu trúc mỗi node là như nhau, muốn xóa một node phải xóa tất cả các items và node con -> rất tốt cho đệ quy.
VD bài toán xóa file = tuần tự:
- Tạo một mảng động lưu tất cả các thư mục, DirectoriesArray[0]='/root';
- Quét toàn bộ mảng DirectoriesArray (chiều dài động), đọc giá trị -> nếu là folder thì đưa vào mảng, là file thì xóa.
- Quét ngược DirectoriesArray -> xóa tất cả các thư mục.
Xóa file = đệ quy:
- Đọc thư mục
- Nếu là file thì xóa
- Nếu là thư mục thì quay lại bước 1
- Xóa thư mục.
Demo code PHP:
function rmdirr($dir) {
if(@rmdir($dir))
return;
if($handle=opendir($dir)) {
while(false!==($file=readdir($handle))) {
if($file=="." or $file=="..") {
continue;
}
if(is_dir("$dir/$file"))
rmdirr("$dir/$file");
else
unlink("$dir/$file");
}
closedir($handle);
rmdir($dir);
}
}
Nhược điểm: Tốn bộ nhớ.
Chưa học kĩ, biết sao nói dzậy thoai
- Đọc thư mục
- Nếu là file thì xóa
- Nếu là thư mục thì quay lại bước 1
- Xóa thư mục.
http://en.wikipedia.org/wiki/Recursion
http://en.wikipedia.org/wiki/Recursi...mputer_science)
//function rmdir_all($dir) {
$dirlist=array($dir);
for($i=0; $i<count($dirlist); $i++) {// count($dirlist) sẽ tự tăng lên khi thêm 1 thư mục vào
//...Readir -> $file
$item_path=$dirlist***91;$i***93;.'/'.$file;
if(is_file($item_path))
unlink($item_path);
else
$dirlist***91;***93;=$item_path; // thêm thư mục vào $dirlist
}// end for
for($i=count($dirlist)-1; $i>=0; $i++) // phải chạy ngc để xóa những thư mục con trước
rmdir($dirlist***91;$i***93;;
// end function rmdir_all
Bài spam trên là em bịa ra thoai, có sai thì cũng thông cảm
Trong code em thấy có hàm nào đọc thư mục đâu .
Cái đó là em demo thoai, nếu muốn chạy dc thì bác phải tự code chứ