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 danh mục đ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ì vậy 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é.

Bài viết bao gồm:

  • Đệ quy là gì?
  • Đệ quy tuyến tính
  • Đệ quy nhị phân
  • Đệ quy hổ tương
  • Khử đệ quy

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ì vậy 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à công thức chia để trị (chia nhỏ từng phần ra rồi phối hợp lại sẽ đơn giản hơn).

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à(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ì còn nếu 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.

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 =

;

for

($ι =

1

; $ι <= $ɳ; $ι++){ $tong += $ι; }

return

$tong; }

Code language:

PHP

(

php

)

Còn với giải thuật đệ quy thì sáng tạo 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($ɳ

-1

); }

echo

tinhtong(

100

);

Code language:

PHP

(

php

)

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 điểm 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 hết thì ta viết như sau: 1 – 1 – 2 – 3 – 5  – 8  – 13 – 21.

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:

function

Fibo

($ɳ)

{

if

($ɳ <=

2

){

return

1

; }

else

{

return

(Fibo($ɳ -

2

) + Fibo($ɳ -

1

)); } }

echo

Fibo(

100

);

Code language:

PHP

(

php

)

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

($ɳ)

{

if

($ɳ <

6

){

return

$ɳ; }

else

{ $tong =

;

for

($ι =

1

; $ι < $ɳ; $ι++){ $tong += pheptinh($ɳ - $ι); }

return

$tong; } }

echo

pheptinh(

6

);

Code language:

PHP

(

php

)

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 Note.

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 theo cấu tạo của 2 hàm này tôi có bài giải như sau:

function

($ɳ)

{

if

($ɳ <

5

){

return

$ɳ; }

else

{

return

ᑗ($ɳ -

1

) + ₲($ɳ -

2

); } }

function

($ɳ)

{

if

($ɳ <=

8

){

return

$ɳ -

3

; }

else

{

return

ᑗ($ɳ -

1

) + ₲($ɳ -

2

); } }

echo

₲(

12

);

Code language:

PHP

(

php

)

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ì vậy 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 công cuộc 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ẽ tìm tòi một thuật toán khác liên quan đến sắp đặt, này là thuật toán sắp đặt nổi bọt.

Xem qua khóa học lập trình website 6 tháng, bảo đảm 100% công việc đầu ra!

Nguồn: https://freetuts.net/giai-thuat-de-quy-trong-php-12.html

Share this:


Tham khảo thêm nội dung thuộc chuyên đề: Kiến thức lập trình
Xem Thêm  TẠO BẢNG NHƯ CHỌN (Azure Synapse Analytics) - Máy chủ SQL - máy chủ sql tạo bảng chọn

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