Đệ quy là gì? Cách sử dụng giải thuật đệ quy trong php

Đệ quy là tên của một giải thuật rất quan trọng trong lập trình. Hiểu nôm na một đối tượng được gọi là đệ quy nếu nó được định nghĩa qua chính nó hoặc cùng dạng với nó với kích thước nhỏ hơn.

Giải thuật đệ quy

Nếu cách giải quyết một bài toán A được thực hiện thông qua bài toán A` cùng dạng với A. Khi đó bài toán được giải theo giải thuật đệ quy.

Chú ý:

• Tuy A và A` cùng dạng nhưng khối lượng xử lý A nhỏ hơn A`.
• Giải thuật đệ quy luôn có điểm neo hay còn gọi là điều kiện dừng

Cơ bản bạn đều bạn cứ nắm như vậy khi đi vào ví dụ tôi sẽ phân tích để bạn thấy rõ hơn tính chất của giải thuật này.

Ví dụ về đệ quy trong php

Ví dụ #1. Tính giai thừa bằng đệ quy

Để tôi nhắc lại cho bạn Giai thừa của một số n được định nghĩa.

• 0! = 1
• (n + 1)! = n! × (n + 1) với n > 0

Ví dụ: 5! = 1 × 2 × 3 × 4 × 5 = 120

Qua định nghĩa giai thừa một số ta nhân thấy rằng để tính n! thì quy thành n(n-1)!. Và tất nhiên n! và (n-1)! có cùng dạng nên hoàn toàn có thể áp dụng đệ quy để thực hiện bài toán này.

<?php
function factorial($n){
    if($n == 0) return 1;
    return $n*factorial($n - 1);
}

echo factorial(5);
?>

factorial: Giai thừa

Sau khi chạy chương trình ta có được kết quả

120

Như bạn nhìn thấy trong hàm tôi đã định nghĩa điều kiện dừng

if($n == 0) return 1;

Ví dụ 2: Tính giá trị của dãy số Fibonacci thứ n

Công thức toán học của dãy số Fibonacci: F(n)

• 1, nếu n = 1;
• 2, nếu n = 1;
• F(n - 1) + F(n - 2), nếu n > 2

Ta có dãy Fibonacci với n = 10

Qua dãy trên ta thấy F(3) = 2, F(5) = 5, F(10) = 55

Vậy bây giờ chúng ta cần thiết lập một hàm để tìm ra giá trị F(n) với n là một số nguyên dương bất kỳ.

Qua công thức toán học ta nhận thấy điểm neo để tính ra kết quả trực tiếp là F(1) = 1 và F(2) = 1. Với trường hợp n > 2 chúng ta áp dụng công thức quy nạp F(n) = F(n - 1) + F(n - 2);

<?php
function Fibonaccy($n){
    if($n == 1 || $n == 2) return 1;
    return Fibonaccy($n - 1) + Fibonaccy($n - 2);
}

Muốn tìm giá trị F(20) ta gọi hàm như sau:

<?php 
echo Fibonaccy(20);
?>

Kết quả

6765

Kết luận:

Qua bài này tôi đã giới thiệu đến bạn thuận toán Đệ quy và những ví dụ điển hình về nó. Trong hệ thống website chúng ta thường sử dụng đệ quy để xuất dữ liệu danh mục đa cấp trong web tin tức, web bán hàng tôi sẽ viết một bài khác hướng dẫn bạn sau.

Còn bây giờ bạn hãy ghi chép lại thuật toán này và tư duy lại những như cài đặt lại những ví dụ tôi chia sẻ bên trên để nắm chắc bài học.

*** Bạn muốn học Php Mysql để đi làm nhưng cảm thấy bối rối, bế tắc không biết bắt đầu từ đâu? Hãy khám phá combo backend “PHP Master” và “Laravel Pro” tại unitop.vn , đây là chương trình giúp hàng ngàn người có công việc từ 8-30tr/tháng.

Xin chào, sớm hẹn gặp lại!