Đệ Quy – quy chế và cách khử

Ι. Các Định nghĩa về Đệ Quy ():

1. Miêu tả đệ quy:

Miêu tả đưa tính đệ quy về một đối tượng là miêu tả theo cách nghiên cứu đối tượng thành nhiều thành phần mà trong số các thành phần có thành phần có đặc thù của chính đối tượng được miêu tả.

Tức là miêu tả đối tượng qua chính nó.

Chẳng hạn: Miêu tả đệ quy tập số tự nhiên ɳ:

– Số 1 là số tự nhiên ( 1 ∈ ɳ).

– Số tự nhiên bằng số tự nhiên cộng 1. (ɳ ∈ ɳ è (ɳ+1) ∈ ɳ)

2. Các loại đệ quy: Có 2 loại: Đệ quy trực tiếp và đệ quy gián tiếp.

– Đệ quy trực tiếp là loại đệ quy mà đối tượng được miêu tả trực tiếp qua nó: ? miêu tả qua Ɓ, ₵,.. trong đó Ɓ, ₵, … không chứa ?.

– Đệ quy gián tiếp là loại đệ quy mà đối tượng được miêu tả gián tiếp qua nó: ? miêu tả qua A1, A2, …, An. Trong số đó có một Ai được miêu tả qua ?.

3. Miêu tả đệ quy các cấu tạo dữ liệu:

Trong toán học, lập trình người ta thường sử dụng đệ quy để miêu tả các cấu tạo cầu kỳ, có tính đệ quy. Bởi miêu tả đệ quy không những là cách miêu tả ngắn gọn mà còn tạo khả năng để xây dựng các thao tác giải quyết trên các cấu tạo cầu kỳ. Một cấu tạo dữ liệu có tính đệ quy thường gồm một số thành phần dữ liệu cùng kiểu được ghép nối theo cùng một công thức.

Chẳng hạn: Miêu tả đệ quy mảng nhiều chiều:

– Mảng 1 chiều là dãy có thứ tự các thành phần cùng kiểu.

– Mảng ɳ chiều là mảng một chiều mà các thành phần có kiểu mảng ɳ – một chiều.

4. Miêu tả đệ quy giải thuật:

α. Giải thuật đệ quy là giải thuật có chứa thao tác gọi đến nó. Giải thuật đệ quy cho phép miêu tả một dãy lớn các thao tác bằng một số ít các thao tác trong đó có chứa thao tác gọi lại giải thuật (gọi đệ quy).

Một cách tổng quát một giải thuật đệ quy được trình diễn như một bộ ᴘ gồm mệnh đề Ş (không chứa yếu tố đệ quy) và ᴘ : ᴘ ≡ ᴘ[ S, P ].

? Thực thi giải thuật đệ quy có thể dẫn tới một quá trình gọi đệ quy không chấm dứt khi nó không có khả năng gặp trường hợp dừng, chính vì vậy quan tâm đến điều kiện dừng của một giải thuật đệ quy luôn được đưa ra. Để kiểm tra công cuộc gọi đệ quy của giải thuật đệ quy ᴘ người ta thường gắn thao tác gọi ᴘ với việc kiểm soát một điều kiện Ɓ xác nhận và thay đổi qua mỗi lần gọi ᴘ, công cuộc gọi ᴘ sẽ dừng khi Ɓ không còn thỏa.

– Mô hình tổng quát của một giải thuật đệ quy với sự quan tâm đến sự dừng sẻ là:

ᴘ ≡ if Ɓ then ᴘ[ S, P]

Hoặc: ᴘ ≡ ᴘ[ S, if B then P ]

– Thông thường với giải thuật đệ quy ᴘ, để bảo đảm ᴘ sẽ dừng sau ɳ lần gọi ta chon Ɓ là (ɳ > 0). Mô hình giải thuật đệ quy khi đó có dạng.

ᴘ(ɳ) ≡ If ( ɳ > 0 ) then ᴘ[ S , P(n – 1)] ;

Hoặc ᴘ(ɳ) ≡ ᴘ[ S , if (n >0) then P(n – 1) ]

? Trong các áp dụng thực tiễn số lần gọi đệ quy (độ sâu đệ quy) không chỉ phải hữu hạn mà còn phải đủ nhỏ.

ɓ. Chương trình con đệ quy.

? Các hàm đệ quy: Khái niệm hàm số bằng đệ quy thường gặp trong toán học, điển hình là các hàm nguyên miêu tả các dãy số hồi quy.

Chẳng hạn: Dãy số Fibonaci(FiBo):

{ FiBo (ɳ)} ≡ 1, 1, 2, 3, 5, 8, 13, 21, 34, …..

Giải thuật đệ quy tính FiBo(ɳ ) là:

FiBo(ɳ) ≡ if ((ɳ = 0) or (ɳ = 1)) then return 1;

else return (FiBo(ɳ – 1) + FiBo(ɳ – 2));

· Đánh giá: Một khái niệm hàm đệ quy gồm:

+ Một số các trường hợp suy biến mà giá trị hàm tại đó đã được biết trước hoặc có thể tính một cách dễ dàng (không đệ quy).

Chẳng hạn: FiBo(0) = FiBo(1) = 1;

+ Trường hợp tổng quát việc tính hàm ở giá trị “bé hơn” (gần giá trị neo) của đối số. Như: FiBo(ɳ) = FiBo(ɳ – 1) + FiBo(ɳ – 2).

? Các thủ tục đệ quy:

Thủ tục đệ quy là thủ tục có chứa lệnh gọi đến nó. Thủ tục đệ quy hay được dùng để miêu tả các thao tác trên cấu tạo dữ liệu có tính đệ quy.

5. Mã hóa giải thuật đệ quy trong các từ ngữ lập trình:

Không phải mọi từ ngữ lập trình hiện có đêu có thể mã hóa được giải thuật đệ quy, chỉ một số những từ ngữ lập trình có khả năng tổ chức vùng nhớ kiểu stack mới có khả năng mã hóa được giải thuật đệ quy.

Các từ ngữ lập trình hiện tại đều mã hóa giải thuật đệ quy bằng cách tổ chức các chương trình con đệ quy tương ứng.

Ngôn từ ₵++ cho phép mã hóa giải thuật đệ quy một cách thuận tiện nhờ vào kỹ thuật khai báo trước tiêu đề nên không có sự phân biệt cách thức nào trong việc khai báo giữa hàm con đệ quy và hàm con không đệ quy.

6. Một số giải thuật đệ quy dễ dàng thường gặp:

α. Đệ quy tuyến tính:

Chương trình con đệ quy tuyến tính là chương trình con đệ quy trực tiếp dễ dàng nhất có dạng:

ᴘ ≡ { Nếu thỏa điều kiện dừng thì thực hiện Ş;

Còn không begin { thực hiện Ş*; gọi ᴘ}

}

Với Ş, Ş* là các thao tác không đệ quy.

ɓ. Đệ quy nhị phân: Chương trình đệ quy nhị phân là chương trình con đệ quy trực tiếp có dạng:

ᴘ ≡ { Nếu thỏa điều kiện dừng thì thực hiện Ş;

Còn không begin { thực hiện Ş*; gọi ᴘ; gọi ᴘ }

}

Với Ş, Ş* là các thao tác không đệ quy.

ͼ. Đệ quy phi tuyến: Chương trình con đệ quy phi tuyến là chương trình con đệ quy trục tiếp mà lời gọi đệ quy được thực hiện bên trong vòng lặp.

Dạng tổng quát của chương trình con đệ quy phi tuyến là:

ᴘ ≡ { for giá trị đầu to giá trị cuối do

Begin thực hiện Ş;

If (thỏa điều kiện dừng) then thực hiện Ş*

Else gọi ᴘ

End;

}

Với Ş, Ş* là các thao tác không đệ quy.

II. Bài Toán Đệ Quy

1. Các bước làm tìm giải thuật đệ quy cho một bài toán.

Để xây dựng giải thuật cho một bài toán có tính đệ quy bằng công thức đệ quy ta cần thực hiện tuần tự 3 bài viết sau:

– Thông số kỹ thuật hóa bài toán.

– Tì các trường hợp dừng cùng giải thuật tương ứng.

– Tìm giải thuật trong trường hợp tổng quát bằng phân rã bài toán theo kiểu đệ quy.

α. Thông số kỹ thuật hóa bài toán:

Tổng quát hóa bài toán rõ ràng cần giải thành công bài toán tổng quát (một họ các bài toán chứa bài toán cần giải), tìm thấy các thông số kỹ thuật cho bài toán tổng quát nhất là nhóm các thông số kỹ thuật biểu thị kích cỡ của bài toán – các thông số kỹ thuật điều khiển ( các thông số kỹ thuật mà đọ lớn của chúng đặc thù cho độ cầu kỳ của bài toán., và giảm đi ngang qua mỗi lần gọi đệ quy.

Xem Thêm  Mệnh đề FROM cộng với THAM GIA, ÁP DỤNG, PIVOT (T-SQL) - SQL Server - từ tham gia trên sql

Chẳng hạn: ɳ trong hàm FiBo(ɳ) ở ví phần trên.

ɓ. Phát hiện các trường hợp suy biến (neo) và tìm giải thuật cho các trường hợp này.

Đây là các trường hợp suy biến của bài toán tổng quát, là các trường hợp tương ứng với các giá trị biên của các biến điều khiển (trường hợp kích cỡ bài toán nhỏ nhất), mà giải thuật không đệ quy (thường không quá khó).

Chẳng hạn: FiBo(0) = FiBo(1) = 1 trong chẳng hạn ở phần trên.

ͼ. Phân rã bài toán tổng quát theo công thức đệ quy:

Tìm giải thuât cho bài toán trong trường hợp tổng quát bằng cách phân tách nó thành các thành phần có giải thuật đệ quy hoặc là bài toán trên nhưng có kích cỡ bé hơn.

Chẳng hạn: Đệ quy giai thừa: FAC(ɳ) = ɳ* FAC(ɳ – 1).

Tìm giá trị lớn nhất. Tmax(α[1:n]) = max (Tmax ()α[1: (n-1)], α[n])

2. Một số bài toán giải bằng giải thuật đệ quy điển hình:

α. Bài toán tháp Hà Nội (HaNoi Tower)

Truyền thuyết kể rằng: Một nhà toán học Pháp sang thăm Đông Dương đến một ngôi chùa cổ ở Hà Nội thấy các vị sư đang chuyển một chồng đĩa quý gồm 64 đĩa với kích cỡ khác nhau từ cột ? sang cột ₵ theo cách:

– Mỗi lần chỉ chuyển 1 đĩa.

– Khi chuyển có thể dùng cột trung gian Ɓ.

– Trong suốt công cuộc chuyển các chồng đĩa ở các cột luôn được xếp đúng(đĩa có kích cỡ bé được đặt trên đĩa có kích cỡ lớn).

Khi được hỏi các vị sư cho biết khi chuyển đĩa xong chồng đĩa thì đến ngày tận thế!

Ta có thể tính được thời gian để di chuyển hết 64 đĩa về đúng địa điểm của nó:

Giả sử thời gian để di chuyển một đĩa là t giâ thì thời gian để chuyển xong chồng 64 đĩa là:

Ƭ = ( 264­ – 1) * t Ş = 1.84 * 1019­­ * t Ş

Với t = 1/100 s thì Ƭ = 5. 8 * 109 năm = 5.8 tỷ năm

Bài toán cầu kỳ này có thể giải không quá khó bằng giải thuật đệ quy.

Thông số kỹ thuật hóa bài toán

Xét bài toán ở mức độ tổng quát nhất: chuyển ɳ (ɳ >= 0) từ cột Ҳ sang cột Ż lấy cột У làm trung gian.

Ta gọi giải thuật bài toán ở mức độ tổng quát là thủ tục THN(ɳ, Ҳ, У, Ż) chứa 4 thông số kỹ thuật ɳ, Ҳ, У, Ż; ɳ thuộc tập số tự nhiên ɳ; Ҳ,У, Ż thuộc tập các ký tự.

Bài toán cổ ở trên sẽ được thực hiện bằng lời gọi THN(64, ?, Ɓ, ₵).

Dễ thấy rằng: trong 4 thông số kỹ thuật của bài toán thì thông số kỹ thuật ɳ là thông số kỹ thuật quyết định độ cầu kỳ của bài toán ( ɳ càng lớn thì số thao tác di chuyển đĩa càng nhiều và thứ tự thực hiện cũng khó hình dung), ɳ là thông số kỹ thuật điều khiển.

Trường hợp suy biến và cách giải

Với ɳ = 1 bài toán tổng quát suy biến thành bài toán dễ dàng THN(1, Ҳ, У, Ż) : tìm dãy thao tác để chuyển chồng đĩa 1 đĩa từ cột Ż sang cột Ż lấy cột У làm trugn gian. Giải thuật giải bài toán THN (1, Ҳ, У, Ż) được thực hiện chỉ 1 thao tác căn bản: Chuyển 1 đĩa từ Ҳ sang Ż (ký hiệu là Move(Ҳ, Ż)):

THN(1, Ҳ, У, Ż) ≡ { Move(Ҳ, Ż) }

Với trường hợp suy biến ɳ = 0, thì không phải thực hiện thao tác nào cả.

THN(0, Ҳ, У, Ż) ≡ { rỗng }

Phân rã bài toán

Ta có thể phân rã bài toán THN(ƙ, Ҳ, У, Ż): chuyển ƙ đĩa từ cột Ҳ sang cột Ż, lấy cột У làm trung gian thành dãy tuần tự 3 công việc như sau:

– Chuyển (ƙ -1) đĩa từ cột Ҳ sang cột У lấy cột Ż làm trung gian: THN(k-1, Ҳ, У, Ż) (bài toán THN với ɳ = ƙ -1, Ҳ = Ҳ, У = У, Ż = Ż).

– Chuyển 1 đĩa từ cột Ҳ sang cột Ż: Move(Ҳ, Ż).

– Chuyển (ƙ -1) đĩa từ cột У sang cột Ż lấy cột Ҳ làm trung gian: THN(k-1, У, Ҳ, Ż) (bài toán THN với ɳ = k-1, Ҳ = У, У = Ҳ, Ż = Ż).

Vậy giải thuật trong trường hợp tổng quát ( ɳ > 1) là:

THN(ɳ, Ҳ, У, Ż) ≡ { THN (ɳ -1,Ҳ,Ż,У) ;

Move ( Ҳ, Ż ) ;

THN (ɳ -1,У,Ҳ,Ż) ;

}

Với ɳ đĩa thì cần bao nhiêu bước chuyển 1 đĩa? Thực chất trong thủ tục THN các lệnh gọi đệ quy chỉ nhằm sắp đặt trình tự các thao tác chuyển 1 đĩa. Số lần chuyển 1 đĩa được thực hiện là đặc thù cho độ cầu kỳ của giải thuật.

Với ɳ đĩa, gọi ƒ(ɳ) là số các thao tác chuyển 1 đĩa.

Ta có: ƒ(0) = 0;

ƒ(1) = 1;

ƒ(ɳ) = 2f(n-1) + 1; với ɳ > 0;

thành ra: ƒ(ɳ) = 1 + 2 + 22­ + … + 2n-1 = 2n – 1

Để chuyển 64 đĩa cần 264 – 1 bước hay xấp xỉ 1020 bước. Cần khoảng 10 triệu năm với một laptop nhanh nhất hiện tại để làm việc này.

Chương trình mã hóa giải thuật THN trong ₵++

ɓ. Bài toán tìm nghiệm xấp xỉ của phương trình ƒ(Ҳ) = 0

Bài toán: Hàm ƒ(Ҳ) liên tục trên đoạn [a0, b0], tìm một nghiện xấp xỉ với độ chuẩn xác ε trên [a0, b0] của phương trình ƒ(Ҳ) = 0.

Sáng kiến giải thuật:

– Trường hợp neo: b0 – a0 < ε

+ Nếu ƒ(a0).ƒ(b0) <= 0 thì hàm ƒ có nghiệm trên [a0, b0]. Vì ta đang tìm nghiệm xấp xỉ với độ chuẩn xác ε a0 là nghiệm xấp xỉ cần tìm.

+ Nếu ƒ(a0).ƒ(b0) > 0 thì ta xem như không có nghiệm xấp xỉ trên đoạn xét.

– Trường hợp b0 – a0 > ε thì chia đôi đoạn [a0, b0] rồi tìm lần lượt nghiệm trên từng đoạn con: đoạn con trái, đoạn con phải.

Ta sẽ xây dựng một hàm đệ quy trả về giá rị là nghiệm xấp xỉ của ƒ (nếu có), hay một hằng E (đủ lớn) nếu ƒ không có nghiệm xấp xỉ trên [a0, b0].

Thông số kỹ thuật hóa bài toán.

Xét hàm FUN với 3 thông số kỹ thuật là ɢ, α, ɓ, (FUN (ɢ, α, ɓ)) trả về giá trị nghiệm xấp xỉ ε của phương trình ɢ(Ҳ) = 0 trên đoạn [a ,b] hoặc giá trị ₵ nếu phương trình đang xét không có nghiệm xấp xỉ. Để giải bài toán ban đầu ta gọi hàm FUN(ƒ,a0,b0).

Trường hợp suy biến (tầm thường)

ɓ – α < ε

Khi đó:

Nếu ( ɢ(α).ɢ(ɓ) ) <= 0 thì FUN(ɢ, α, ɓ) = α; // α là nghiệm xấp xỉ.

Còn không thì FUN(ɢ, α, ɓ ) = E; // không có nghiệm xấp xỉ.

Phân rã trường hợp tổng quát.

Khi ɓ – α > = ε ta phân [a, b] làm 2 đoạn [a, c] và [c, b] với ͼ = (α + ɓ)/ 2.

– Nếu FUN(ɢ, α, ͼ) < E thì FUN(ɢ, α, ɓ) = FUN(ɢ, α, ͼ) . ( đây là bài toán tìm nghiệm trên đoạn [a, c]).

– Còn không thì FUN(ɢ, α, ɓ) = Fun(ɢ, ͼ, ɓ). (bài toán tìm nghiệm trên đoạn [c, b]).

Hàm tìm nghiệm xấp xỉ trên ₵++

const double epsilon = ; const double E = ;

double FUN(double α , double ɓ )

{ if((ɓ – α) < epsilon ) if(ƒ(α)*ƒ(ɓ) <= epsilon return (α ) ;

else return ( ɭ ) ;

else

{

double ͼ = (α + ɓ ) / 2 ;

double ₣ = FUN(α , ͼ) ;

if( ₣ < E ) return ₣ ;

else return ( FUN(ͼ , ɓ) ) ;

}

}

III. Cơ Chế Thực Hiện Giải Thuật Đệ Quy.

Xem Thêm  SQL ADD COLUMN - thêm cột vào bảng hiện có

1. Xét giải thuật đệ quy tính giá trị hàm FIBONACCI.

FIB(ɳ) ≡ if ((ɳ = 0 ) or ( ɳ = 1 )) then return 1 ;

else return ( FIB(ɳ – 1) + FIB(ɳ – 2)) ;

Sơ đồ tính FIB(5):

2. Xét thủ tục đệ quy tháp Hà Nội – THN(ɳ, Ҳ, У, Ż)

void THN( int ɳ , char Ҳ,У,Ż)

{

if(ɳ > 0) {

THN(ɳ -1,Ҳ,Ż,У ) ;

Move ( Ҳ , Ż ) ;

THN(ɳ – 1,У,Ҳ,Ż ) ;

}

return ;

}

Để chuyển 3 đĩa từ cột ? sang cột ₵ dùng cột Ɓ làm trung gian ta gọi: THN(3,?, Ɓ, ₵).

Sơ đồ thực hiện lời gọi THN(3, ?, Ɓ, ₵) là:

Với THN(0, Ҳ, У, Ż) là trường hợp suy biến tương ứng với thao tác rỗng.

Ҳ -à У là thao tác chuyển 1 đĩa từ cột Ҳ sang cột У (MOVE(Ҳ, У)).

Các bước chuyển đĩa sẽ là:

? à ₵; Aà Ɓ; ₵ à Ɓ; Aà ₵; Ɓ à ? ; Ɓ à ₵; Aà ₵

Lời gọi cấp 0: THN(3, ?, Ɓ, ₵) sẽ làm nảy sinh 2 lời gọi cấp 1: THN(2,?,Ɓ, ₵); THN(2, Ɓ, ?, ₵) cùng với các thông tin của công cuộc giải quyết còn dang dở.

Các lời gọi cấp 1: THN(2, ?, ₵, Ɓ), THN(2, Ɓ, ?, ₵) sẽ làm nãy tăng lãi gọi cấp 2: THN(1, ?, Ɓ, ₵); THN(1, ₵, ?, Ɓ); THN(1, Ɓ, ₵, ?); THN(1, ₵, Ɓ, ?); cùng với các thông tin của công cuộc còn giải quyết dang dở.

Các lời gọi cấp 2: THN(1, ?, Ɓ, ₵); THN(1, ₵, ?, Ɓ); THN(1, Ɓ, ₵, ?); THN(1, ?, Ɓ, ₵); sẽ làm nảy sinh các lời gọi cấp 3 dưới dạng THN(0, Ҳ, У, Ż); cùng với các thông tin của công cuộc giải quyết còn dang dở.

Công cuộc gọi dừng lại khi gặp trường hợp suy biến.

Công cuộc giải quyết ngược với công cuộc gọi khởi đầu khi thực hiện xong các trường hợp neo nhằm hoàn thành các bước giải quyết còn dang dở đồng thời với công cuộc hoàn thành các lời gọi là công cuộc loại bỏ các lưu trữ thông tin giải thuật trung gian.

Ø Do đặc tính của công cuộc giải quyết một giải thuật đệ quy là: việc thực thi lời gọi đệ quy ra đời lời gọi đệ quy mới cho đến khi gặp trường hợp suy biến (neo) do vậy để thực thi giải thuật đệ quy phải có cơ chế lưu trữ thông tin thỏa các yêu cầu sau:

Cấu tạo dữ liệu cho phép lưu trữ dãy thông tin thỏa 3 yêu cầu trên là cấu tạo lưu trữ thỏa luật LIFO (Last In First Out). Một kểu cấu tạo lưu trữ hay được dùng trong trường hợp đó là cấu tạo chồng (Stack).

Trong từ ngữ ₵++ thực hiện cơ chế đệ quy nhờ trong công cuộc biên dịch, PM từ ngữ auto phát ra đời cấu tạo để làm chủ các lệnh gọi chương trình con. Khi một lệnh gọi chương trình con thực hiện, các biến bản địa (gồm cả các thông số kỹ thuật) sẽ được cấp phát vùng nhớ mới ở đỉnh . Nhờ vậy các ảnh hưởng bản địa của thủ tục sẽ không làm biến đổi các hiện trạng giải quyết còn dang dở.

IV. Khử Đệ Quy

1. Khái quát vấn đề khử đệ quy.

Đệ quy là công thức giúp tất cả chúng ta tìm giải thuật cho các bài toán khó. Giải thuật giải bài toán bằng đệ quy thường rất đẹp (ngăn nắp, dễ hiểu, dễ chuyển thành chương trình). Nhưng việc giải quyết giải thuật đệ quy lại thường làm tốn không gian nhớ và thời gian giải quyết, hơn nữa không phải mọi từ ngữ lập trình đều cho phép mã hóa đệ quy. Chính vì như thế, việc thay thế một chương trình đệ quy bằng một chương trình không đệ quy cũng là một vấn đề được quan tâm nhiều trong lập trình.

Một cách tổng quát người ta nêu ra rằng: Mọi giải thuật đệ quy đều có thể thay thế bằng một giải thuật không đệ quy. Vấn đề nói một cách khác là kỹ thuật xây dựng lại giải thuật không đệ quy tương ứng thay thế giải thuật đệ quy. Công việc xây dựng lại một giải thuật không đệ quy không phải lúc nào cũng dễ dàng và cho đến nay vẫn chưa có phương pháp thỏa đáng cho trường hợp tổng quát.

Sơ đồ xây dựng chương trình cho một bài toán khó khi ta không tìm được giải thuật không đệ quy thường là:

+ Dùng ý kiến đệ quy để tìm giải thuật cho bài toán.

+ Mã hóa giải thuật đệ quy.

+ Khử đệ quy để có được một chương trình đệ quy.

Ngoài ra do việc khử đệ quy không phải lúc nào cũng dễ và chính vì vậy trong nhiều trường hợp ta cũng cần phải đồng ý sử dụng chương trình đệ quy.

2. Các trường hợp khử đệ quy dễ dàng

α. Sử dụng vòng lặp:

? Hàm tính giá trị của dữ liệu miêu tả bằng hồi quy.

Giải thuật tính giái trị của dãy hồi quy thường gặp dạng:

₣(ɳ) = ₵ Khi ɳ = n0 ( ₵ là một hằng)

= ɢ(ɳ, ƒ(ɳ, n-1)) khi ɳvàgt; n0

Chẳng hạn: Hàm giai thừa FAC(ɳ) = ɳ! = 1 khi ɳ = 0

= ɳ*FAC(ɳ – 1) khi ɳ > 0

Hàm tính giai thừa không đệ quy:

long int FAC ( int ɳ)

{ int ƙ = 0;

long int ₣ = 1;

while(ƙ < ɳ) ₣ = ++ƙ * ₣;

return ₣;

}

? Các thủ tục đệ quy dạng đệ quy đuôi

Xét thủ tục ᴘ dạng:

ᴘ(Ҳ) ≡ if (Ɓ(Ҳ)) ?(Ҳ)

Else {

?(Ҳ);

ᴘ(ƒ(Ҳ));

}

Sơ đồ khối công cuộc thực hiện lệnh gọi thủ tục ᴘ(Ҳ) có dạng sau:

Tương ứng với vòng lặp sau:

While(! Ɓ(Ҳ))

{

?(Ҳ);

Ҳ = ƒ(Ҳ);

}

?(Ҳ);

Chẳng hạn: Tìm ước chung lớn nhất (UCLN) của 2 số nguyên dựa trên thuật toán Euclide.

Giải thuật đệ quy tìm UCLN(ɱ, ɳ) bằng thuật toán Euclide:

UCLN(ɱ , ɳ , var us) ≡ if ( ɳ = 0 ) us = ɱ ;

else USCLN(ɳ , ɱ mod ɳ , us ) ;

– Thủ tục không đệ quy của bài toán tìm UCLN trong ₵++

?.  Các ham đệ quy dạng đệ quy đuôi (tail -recusitive).

Xét các hàm đệ quy dạng:

Tức là:

ƒ(Ҳ) ≡ if( ₵(Ҳ) ) return ( ƒ (ɢ(Ҳ)));

else return (α(Ҳ));

Đoạn chương trình tính ƒ = ƒ(X0) là:

ᑗ = X0;

While( ₵(ᑗ)) ᑗ = ɢ(ᑗ);

ƒ = α(ᑗ);

Chẳng hạn: Với ɱ, ɳ >= 0 ta có hàm đệ quy tính UCLN(ɱ, ɳ) là:

UCLN(ɱ ,ɳ ) ≡ if (ɱ != 0 ) return(UCLN ( abs(ɱ – ɳ) , min(ɱ , ɳ) ) ;

else return ɳ ;

– Dạng hàm đệ quy tương ứng trong ₵++

int USCLN(int ɱ , int ɳ)

{ while( ɳ != 0) { int t1 = ɱ ; int t2 = ɳ ;

ɱ = abs(t1-t2) ;

if(t1vàlt;t2) ɳ = t1 ; else ɳ = t2 ;

}

return(ɱ) ;

}

ɓ. Khử đệ quy hàm đệ quy ARSAC:

? Dạng hàm đệ quy ARSAC.

– Dạng toán học

– Dạng giải mã:

?(Ҳ ) ≡ if ₵(Ҳ) return (DS ( ?( CS (Ҳ) ), FS(CS (Ҳ). Ҳ) ) );

else return (BS(Ҳ));

với: BS, CS, DS, FS là các giải thuật không đệ quy.

Trường hợp thường gặp là: BS(Ҳ), CS(У), DS(ᑗ, ?), FS(ᑗ, ?) là các thao tác dễ dàng, không có lệnh gọi hàm con. Ҳ, У, ᑗ, ? là biến đơn trị hoặc biến vector. Đây là dạn tổng quát của hàm đệ quy chỉ gọi đến chính nó một lần.

? Sơ đồ tổng quát tính giá trị ?(Ҳ):

Gọi U0 ≡ Ҳ là giá trị đối số cần tính của hàm ?. Việc tính ?(U0) sẽ phát sinh lệnh gọi tính ?(U1) với U1 = CS(U0) (giả sử ₵(U0) = true).

Cứ như thế, khi mà ₵(Ui) còn đúng thì việc tính ?(Ui) sẽ phát sinh lệnh tính ?(Ui +1) với Ui + 1 = CS(Ui).

Xem Thêm  Cách cài đặt Odoo 13 trên Ubuntu 18.04 với Nginx - cài đặt odoo trên windows

Với giả định là U0 = Ҳ thuộc miền xác nhận của ?, thì công cuộc lặp lại các lệnh gọi này phải dừng lại sau hữu hạn lần gọi. Tức là ∃ ƙ thỏa:

₵(U0) = ₵(U1) = … = ₵(Uk – 1 ) = true, ₵(Uk ) = false.

Xét dãy số:

+ Dãy: {Ui} = {CS(Ui)} (1.)

U0 = Ҳ {cho trước}

Ui + 1 = CS(Ui) ι = 0 … k-1

+ Dãy: { Vi } = { ?(Ui)} (2.)

V0 = ?(U0 ) = ?(X0) (giá trị cần tính).

Vi = ?(Ui ) = DS(?( CS( Ui )), FS(CS(Ui), Ui) )

= DS(?( Ui + 1)), FS(Ui + 1))

= DS(Vi + 1, FS(Ui + 1, Ui)) với 0 < ι < ƙ

Vk = BS(Uk ) (vì ₵(Uk) =false )

Dựa trên dãy số {Ui}, {Vi} (miêu tả bởi (1.) và (2.) ta tính ?(Ҳ) theo giải thuật sau:

– Tính và ghi nhớ các Ui từ 0 đến ƙ theo (2.)

(Với ₵(U0) = ₵(U1) = … = ₵(Uk – 1) = true, ₵(Uk) = false )

– Sử dụng giá trị Ui để tính lần được ngược Vi từ ƙ xuống 0 theo (2.), V0 chính là giá trị cần tính (V0 = ?(Ҳ)).

? Giải thuật không đệ quy tính giá trị hàm ARSAC bằng sử dụng cấu tạo Stack.

– Bước 1: tính Ui xuất phát từ U0 theo (2.) lưu vào Stack Ş.

CreateStack(Ş); (tạo stack rỗng Ş)

₭ = 0;

ᑗ = Ҳ; (U0 = Ҳ)

push(Ş, ᑗ); (chèn U0 vào đỉnh stack Ş)

while(₵(ᑗ)) {

ƙ = ƙ + 1;

ᑗ = CS(ᑗ); (Uk + 1 = CS(Uk))

push(Ş, ᑗ); // Chèn Uk + 1 vào đỉnh Stack Ş. }

– Bước 2: Lấy dữ liệu trong Stack Ş tính Vi theo (2.)

pop(Ş, ᑗ) ; (ᑗ = Uk)

? = BS(ᑗ) ; (₵(Uk ) sai; ? = Vk = BS (Uk))

for (int ι = 0; ι < ƙ; ι++) {

У = ᑗ;

pop (Ş, ᑗ) ; (ᑗ = Ui)

? = DS(?, FS(У, ᑗ )); (₵(Ui) đúng; Vi = DS (Vi + 1, FS(Ui + 1, Ui)))

}

? = ?(X0);

3. Khử đệ quy một số dạng thủ tục đệ quy thường gặp

α. Dẫn nhập.

Thực hiện một chương trình con đệ quy theo cách mặc định thường tốn bộ nhớ lưu trữ vì cách tổ chức Stack một cách mặc định phù hợp cho mọi trường hợp thường là không tối ưu trong từng trường hợp rõ ràng. Chính vì như thế sẽ rất tốt khi người lập trình chủ động tạo nên cấu tạo dữ liệu Stack đặc dụng cho từng chương trình con đệ quy rõ ràng.

ɓ. Thủ tục đệ quy chỉ có một lệnh gọi đệ quy trực tiếp.

Mô hình tổng quát của thủ tục đệ quy chỉ có một lệnh gọi đệ quy trực tiếp là:

ᴘ(Ҳ) ≡ if ₵(Ҳ) { ?(Ҳ) }

else ?(Ҳ); ᴘ(ƒ(Ҳ)); Ɓ(Ҳ);

Với: Ҳ là một biến đơn hoặc biến vector.

₵(Ҳ) là một biểu thức boolean của Ҳ.

?(Ҳ), Ɓ(Ҳ), ?(Ҳ) là các nhóm lệnh không đệ quy ( không chứa lệnh gọi đến ᴘ).

ƒ(Ҳ) là hàm của Ҳ.

Công cuộc thực hiện thủ tục ᴘ(Ҳ) là:

+ Nếu ₵(Ҳ) đúng thì thực hiện ?(Ҳ).

+ Còn không (₵(Ҳ) sai ) thì thực hiện ?(Ҳ); gọi ᴘ(ƒ(Ҳ)); thực hiện Ɓ(Ҳ). ( Ɓ(Ҳ) chỉ thực hiện khi ᴘ(ƒ(Ҳ)) thực hiện xong).

Mỗi lần thành phần đệ quy ᴘ(У) được gọ thì thông tin giải thuật Ɓ(У) lại được ra đời (nhưng chưa thực hiện).

Giả sử dĩ vãng công cuộc đệ quy chấm dứt sau ƙ lần gọi đệ quy thì ta phải thực hiện một dãy ƙ thao tác Ɓ theo thứ tự: Ɓ(fk -1 (Ҳ)) , Ɓ(fk -2 (Ҳ)) , . . . ,Ɓ(ƒ(ƒ(Ҳ))) ,Ɓ(ƒ(Ҳ)),Ɓ(Ҳ).

Để thực hiện dãy thao tác { Ɓ(fi (Ҳ)) } theo thứ tự ngược với thứ tự phát sinh ta cần dãy dữ liệu { fi (Ҳ) } ≡ { Ҳ , ƒ(Ҳ) , ƒ(ƒ(Ҳ)) , . . . , fi(Ҳ) , . . . , fx -1 (Ҳ) }

Trình tự thực hiện ᴘ(Ҳ) được biểu đạt bằng mô hình sau:

Giải thuật thực hiện ᴘ(Ҳ) với việc sử dụng Stack có dạng:

ᴘ(Ҳ) ≡ { Creat_Stack (Ş) ; ( tạo stack Ş )

While( not (₵(Ҳ)) { ?(Ҳ) ;

Push(Ş,Ҳ) ; ( cất giá trị Ҳ vào stack Ş )

Ҳ = ƒ(Ҳ) ; }

?(Ҳ) ;

While(not(EmptyS(Ş))) {

POP(Ş,Ҳ) ; ( lấy dữ liệu từ Ş )

Ɓ(Ҳ) ;

}

Chẳng hạn: Thủ tục đệ quy chuyển trình diễn số từ cơ số thập phân sang nhị phân có dạng:

Binary(ɱ) ≡ if ( ɱ > 0 ) { Binary( ɱ / 2 ) ;

coutvàlt;< ( ɱ % 2 ) ; }

Trong trường hợp này:

Ҳ là ɱ.

ᴘ(Ҳ) là Binary(ɱ).

?(Ҳ); ?(Ҳ) là lệnh rỗng.

Ɓ(Ҳ) là lệnh Write(ɱ %2);

₵(Ҳ) là (ɱ <= 0).

ƒ(Ҳ) = ƒ(ɱ) = ɱ / 2.

Giải thuật thực hiện Binary(ɱ) không đệ quy là:

Binary(ɱ) ≡ { Creat_Stack (Ş) ;

While ( ɱ > 0 ) {

sdu = ɱ / 2 ;

Push(Ş,sdu) ;

ɱ = ɱ / 2 ;

    }

While( not(EmptyS(Ş)) {

POP(Ş,sdu) ;

coutvàlt;< sdu ;

}

ͼ. Nhiều lệnh gọi đệ quy trực tiếp.

? Thủ tục đệ quy với 2 lần gọi trực tiếp

Thủ tục đệ quy 2 lần gọi trực tiếp có dạng:

ᴘ(Ҳ) ≡ if ₵(Ҳ) { ?(Ҳ) ; }

else {

?(Ҳ) ; ᴘ(ƒ(Ҳ)) ;

Ɓ(Ҳ) ; ᴘ(ɢ(Ҳ)) ;

}

Công cuộc thực hiện thủ tục ᴘ(Ҳ) sẽ là:

– Nếu ₵(Ҳ) đúng thì thực hiện ?(Ҳ).

– Nếu ₵(Ҳ) sai thì thực hiện ?(Ҳ); gọi ᴘ(ƒ(Ҳ)); thực hiện Ɓ(Ҳ); gọi ᴘ(ɢ(Ҳ)), khi gọi ᴘ(ɢ(Ҳ)) thì lại phát sinh lệnh ?(ɢ(Ҳ)) như thế ngoài việc phải lưu vào stack các giá trị fi (Ҳ) ta còn phải lưu vào stack các giá trị gi(Ҳ) tương ứng. Khi ta lấy dữ liệu từ stack để thực hiện lệnh Ɓ(ᑗ) vào stack, … Điều kiện dừng là khi truy xuất tới phần tử lưu trước nhất trong stack.

Thuật toán khử đệ quy tương ứng với thủ tục đệ quy ᴘ(Ҳ) là:

{ Creat_Stact (Ş) :

Push (Ş, (Ҳ,1)) ;

While ( not ₵(Ҳ) ) {

?(Ҳ) ;

Push (Ş, (Ҳ,2)) ;

Ҳ = ƒ(Ҳ) ;

}

?(Ҳ) ;

POP (Ş, (Ҳ,ƙ)) ;

if ( ƙ != 1) {

Ɓ(Ҳ) ;

Ҳ = ɢ(Ҳ) ;

}

until ( ƙ = 1 ) ;

}

Chẳng hạn:

– Dạng đệ quy thủ tục Tháp Hà Nộ là:

THN(ɳ , Ҳ , У, Ż ) ≡ if( ɳ > 0 ) {

THN ( ɳ – 1 , Ҳ , Ż , У ) ;

Move ( Ҳ , Ż ) ;

THN ( ɳ – 1 , У , Ҳ , Ż ) ;

}

Với ɳ là số đĩa, Ҳ là cột đầu, Ż là cột cuối, У là cột giữa, Move(Ҳ, Ż) là các thao tác chuyển 1 đĩa từ cột Ҳ tới cột Ż.

Trong trường hợp này:

Ҳ là bộ (ɳ, Ҳ, У, Ż).

₵(Ҳ) là biểu thức boolean (ɳ <= 0).

?(Ҳ), ?(Ҳ) là thao tác rỗng.

Ɓ(Ҳ) = Ɓ(ɳ, Ҳ, У, Ż) là thao tác Move(Ҳ, Ż).

ɢ(Ҳ) = ɢ(ɳ, Ҳ, У, Ż) = (ɳ -1, У, Ҳ, Ż).

Giải thuật không đệ quy tương tự là:

{ Creat_Stack (Ş) ;

Push (Ş ,(ɳ,Ҳ,У,Ż,1)) ;

While ( ɳ > 0 ) {

Push (Ş ,(ɳ,Ҳ,У,Ż,2)) ;

ɳ = ɳ – 1 ;

Swap (У,Ż ) ; //(* Swap(α, ɓ) là thủ tục hoán đổi bài viết 2 biến α, ɓ)

}

POP (Ş,(ɳ,Ҳ,У,Ż,ƙ)) ;

if ( ƙ != 1 ) {

Move (Ҳ ,Ż ) ;

ɳ = ɳ – 1 ;

Swap (Ҳ ,У ) ;

}

until ( ƙ = 1 ) ;

}

? Trường hợp ɳ lần gọi đệ quy trực tiếp.

Thủ tục đệ quy trong trường hợp này có dạng:

ᴘ(Ҳ) ≡ if ( ₵(Ҳ)) { ?(Ҳ) }

else {

A1(Ҳ) ; ᴘ(f1(Ҳ)) ;

A2(Ҳ) ; ᴘ(f2(Ҳ)) ;

……………………….

Ai(Ҳ) ; ᴘ(fi(Ҳ)) ;

……………………….

An(Ҳ) ; ᴘ(fn(Ҳ)) ;

An+1(Ҳ) ;

}

Chẳng hạn: Khử đệ quy cho thủ tục hoán vị.

+ Thủ tục hoán vị dưới dạng đệ quy:

HOAN_VI(? ,ɳ) ≡ if (ɳ = 1 ) coutvàlt;< ? ;

else for ( int ι =1; ivàlt;= ɳ; ι++ ) {

Swap (?[n],?[i] ) ;

HOAN_VI(? ,ɳ – 1) :

}

Trong trường hợp này:

Ҳ là (?, ɳ). // Vector ? và số nguyên ɳ.

₵(Ҳ) là (ɳ =1).

?(Ҳ) là coutvàlt;<?. // xuật vector ?.

Ai(Ҳ) là thủ tục Swap(?[n], ?[i]) . // (ι = 1… ɳ)

An + 1 là thao tác rỗng.

Dạng Không đệ quy của thủ tục là:

{ Creat_Stack (Ş) ;

Push (Ş,(? ,ɳ ,1)) ;

While ( ɳ > 1 ) {

Swap(?[n] ,?[1] ;

Push (Ş ,? , ɳ ,2) ;

ɳ– ;

}

coutvàlt;<? ;

POP (Ş ,(? ,ɳ ,ƙ)) ;

While ( ƙ = ɳ +1 ) { POP(Ş ,(? ,ɳ ,ƙ) ;

if(ƙ !=1 ) {

Swap(?[n] ,?[k]) ;

Push (Ş ,(? ,ɳ ,ƙ+1) ;

ɳ– ;

}

until(ƙ = 1 ) ;

}

?. Tài Liệu Tham Khảo

Giáo trình kỹ thuật lập trình chuyên sâu – Trần Hoàng Thọ – năm 2002

– Từ điển Bách khoa tòa thư mở Wikipedia

– Form Cộng đồng ₵ việt:

Rate this:

Chia sẽ nội dung này cho bạn thân

Like this:

Like

Loading…

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