Bài 12: Giải thuật đệ quy trong php

Đệ quy là một vấn đề nan giải đối với những bạn mới học lập trình website vì nó được sử dụng trong các vận dụng như đệ quy list đa cấp, chuyên đề đa cấp nhưng thực sự người nắm được giải thuật này không nhiều, chính vì thế trong loạt series php cơ bản này ta sẽ tham khảo thêm về giải thuật này nhé.

1. Giải thuật đệ quy là gì ?

Đệ quy liên quan đến rất là nhiều trong toán học, chính vì thế ta quay lại toán học một tí, một thuộc tính trong toán học được gọi là đệ quy nếu trong đó một lớp các đối tượng có các thuộc tính giống nhau & có mối liên hệ với nhau, kết quả của bước 1 là một thành phần của bước 2, bước 2 là thành phần bước 3, ….

Chẳng hạn: Ba của tôi là ông ?, Ba của Ba tôi là ông β, … cứ như thế đệ quy и lần sẽ tìm được nguồn gốc của tôi ( hơi căng ), & đây có thể gọi là một chương trình đệ quy nhằm tìm thấy nguồn gốc của tôi. Giải thuật đệ quy cũng có thể gọi là bí quyết chia để trị (chia nhỏ từng phần ra rồi phối hợp lại sẽ đơn giản hơn).

Mong muốn dùng được đệ quy bạn phải biết viết hàm vì mỗi lần đệ quy là hàm gọi lại chính nó. Một chương trình đệ quy cần có điều kiện dừng, vì nếu như không có thì chương trình sẽ gọi vô hạn (lặp vô hạn). Chẳng hạn tính tổng từ 1 tới и thì điều kiện dừng là khi tới и rồi thì không được tính nữa. còn nếu tính từ и trở về 1 thì điều kiện dừng là и = 1.

2. Đệ quy tuyến tính

Đây là loại đệ quy mà trong hàm đệ quy chỉ gọi duy nhất 1 lần đến chính nó.

Chẳng hạn: Cho и = 100, tính tổng các số từ 1 tới 100.

Xem Thêm  Vào chuỗi, mảng, và hơn thế nữa! - đọc một tập tin php

Bài này nếu dùng vòng lặp thì dễ dàng, ta lặp từ 1 đến 100 & mỗi vòng lặp cộng dồn lại sẽ ra tổng. Bài giải cho vòng lặp như sau:

function tinhtong($и){
    $tong = 0;
    for ($ι = 1; $ι <= $и; $ι++){
        $tong += $ι; // mỗi vòng lặp cộng lại với nhau
    }
    return $tong;
}

Còn với giải thuật đệ quy thì sáng kiến là ở mỗi lần đệ quy ta sẽ lấy số đó cộng với hàm chính nó & biến truyền vào là số đó trừ đi 1. Điều kiện dừng là nếu số đó = 1 thì dừng vòng lặp & trả kết quả về. Nghiên cứu kỹ hơn tức là mỗi bước đệ quy chính là một lần lặp, cộng dồn tổng các lần đệ quy chính là cộng dồn tổng các lần lặp nên kết quả nó sẽ thương đương với bài giải bằng vòng lặp trên.

function tinhtong($и)
{
    if ($и == 1){ return $и; }
    return $и + tinhtong($n-1);
}
echo tinhtong(100);

Trong giải thuật đệ quy này thì trong  hàm gọi lại chính nó chỉ 1 lần (tức là chỉ có 1 đoạn code tinhtong($n-1)). Ở mỗi bước đệ quy sẽ lấy giá trị truyền vào cộng với giá trị của tinhtong($n-1), cứ lặp đệ quy như thế cho tới khi biến truyền vào hàm = 1 thì dừng đệ quy, bài toán được mô phỏng như sau:

Biến truyền vào = 100; giá trị return = 100 + đệ quy lần 2 với tham số như sau: tinhtong(100-1). Cứ như thế mỗi lần đệ quy quy sẽ bằng biến truyền vào + lần đệ quy tiếp.

Luồng cộng như sau: 100 + ( 100-1 = 99 ) + (99 – 1 = 98) + …. + (2-1 = 1)  <=> 100 + 99 + 98 + …. + 1

3. Đệ quy nhị phân

Đệ quy nhị phân là loại đệ quy mà thân hạm gọi lại chính nó 2 lần.

Chẳng hạn: Xuất ra màn hình phần tử thứ 100 của dãy Fibonacci.

Dãy Fibonacci là dãy xuất phát từ 1 tới и trong đó phần tử thứ trong dãy sẽ bằng tổng 2 phần tử trước nó cộng lại.  Chẳng hạn viết dãy từ Fibonacci của 8 phần tử trước tiên thì ta viết như sau: 1 – 1 – 2 – 3 – 5  – 8  – 13 – 21.

Xem Thêm  Verify your site ownership - lỗi internal server error wordpress

Trong dãy Fibonacci phần tử thứ 1 & thứ 2 có giá trị bằng 1. Đây cũng chính là điêu kiện dừng của dãy.

Bài giải:

// Hàm tính giá trị của phần tử thứ $и của dãy Fibonacci
function Fibo($и)
{
    if ($и <= 2){
        return 1;
    }
    else {
        return (Fibo($и - 2) + Fibo($и - 1));
    }
}
 
// Truyền 100 vào để check
echo Fibo(100);

3. Đệ quy phi tuyến

Là loại đệ quy mà trong hàm có dùng vòng lặp để gọi lại chính nó.

Chẳng hạn: Tính phần tử thứ 8 của dãy được tính theo bí quyết sau:

Ý nghĩa của dãy như sau:

  • Nếu и nhập vào mà nhỏ hơn 6 thì trả về chính nó
  • Nếu и nhập vào mà to hơn hoặc bằng 6 thì trả về kết quả bằng tổng các số từ 1 tới n-1, với mỗi số lại tính theo quy luật trên. Có nghĩa rằng chẳng hạn tôi có hàm  phep_tinh & nhập giá trị 6 vào thì dãy được tính như sau: pheptinh(5) + pheptinh(4) + pheptinh(3) + pheptinh(2) + pheptinh(1)

Bài giải:

function pheptinh($и)
{
    // Neeus $и < 6 thì trả về chính nó
    if ($и < 6){
        return $и;
    }
    else{
        // Trái lại tính tổng từ 1 tới $и - 1, & mỗi phần tử lại gọi làm hàm chính nó
        $tong = 0;
        for ($ι = 1; $ι < $и; $ι++){
            $tong += pheptinh($и - $ι);
        }
        return $tong;
    }
}
 
echo pheptinh(6);

4. Đệ quy hổ tương

Nghe tên gọi thôi cũng hiểu được phần nào. Đệ quy hổ tương là đệ quy một hàm ? gọi sang một hàm β, Trong hàm β lại gọi sang hàm ?. Như thế là chúng gọi lẫn nhau nên người ta gọi là  hổ tương.

Cũng như các loại đệ quy trên kia, nếu cả 2 hàm ?, β đều không có điều kiện dừng thì sẽ bị lặp vô hạn, điều này rất bất trắc nên các bạn phải lưu ý.

Xem Thêm  Giao diện trong Java - java giao diện là gì

Chẳng hạn: Tính giá trị của dãy sau

Ta thấy 2 hàm đệ quy có gọi lẫn nhau & mỗi hàm đều có điều kiện dừng. Đến đây ao ước tôi không cần giải thích ý nghĩa của 2 hàm này nữa. Dựa trên kết cấu của 2 hàm này tôi có bài giải như sau:

// Hàm đệ quy ᑗ
function ᑗ($и)
{
    if ($и < 5){ // điều kiện dừng
        return $и;
    }
    else{
        return ᑗ($и - 1) + ₲($и - 2);
    }
}
 
// Hàm đệ quy ₲
function ₲($и)
{
    if ($и <= 8){ // điều kiện dừng
        return $и - 3;
    }
    else{
        return ᑗ($и - 1) + ₲($и - 2);
    }
}
 
// Gọi Hàm
 
echo ₲(12);

5. Khử đệ quy

Giải thuật đệ quy rất hay nhưng ngân sách tính toán cho nó thì rất mà cao, chính vì thế người ta hay tìm những giải thuật khác để thay thế cho nó. Tuy  nhiên trên thực tiễn chưa có một giải thuật nào chắc nịch cho điều này, có nghĩa là không phải bài nào cũng chuyển được. & phần đó là một tiến trình nên tôi không có thời gian & cũng như là không đủ trình độ để giải hết các bài đệ quy được. Như chẳng hạn ở phần đệ quy tuyến tính các bạn thấy tôi đã dùng vòng lặp for để giải cho bài toán tính tổng. đó cũng là một cách sử dụng vòng lặp để khử đệ quy.

6. Lời kết

Giải thuật đệ quy thật sự rất khó phải không các bạn, nên để nắm được nó cần phải luyện tập nhiều thời gian. Tôi ao ước qua bài này sẽ làm tiền đề cho các bạn thích thú giải thuật tìm hiểu thêm. Bài kế tiếp tất cả chúng ta sẽ khám phá một thuật toán khác liên quan đến xếp đặt, này là thuật toán xếp đặt nổi bọt.

Viết một bình luận