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

I. Các Khái niệm về Đệ Quy (recursion):

1. Mô tả đệ quy:

Mô tả mang tính đệ quy về một đối tượng là mô tả theo cách phân tích đố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 mang tính chất của chính đối tượng được mô tả.

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

Ví dụ: Mô tả đệ quy tập số tự nhiên N:

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

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

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 mô tả trực tiếp qua nó: A mô tả qua B, C,.. trong đó B, C, … không chứa A.

– Đệ quy gián tiếp là loại đệ quy mà đối tượng được mô tả gián tiếp qua nó: A mô tả qua A₁, A₂, …, A_n. Trong đó có một A_i được mô tả qua A.

3. Mô tả đệ quy các cấu trúc dữ liệu:

Trong toán học, lập trình người ta thường sử dụng đệ quy để mô tả các cấu trúc phức tạp, có tính đệ quy. Bởi mô tả đệ quy không chỉ là cách mô tả ngắn gọn mà còn tạo khả năng để xây dựng các thao tác xử lý trên các cấu trúc phức tạp. Một cấu trúc 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 phương thức.

Ví dụ: Mô tả đệ quy mảng nhiều chiều:

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

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

4. Mô tả đệ quy giải thuật:

a. 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 mô 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 biểu diễn như một bộ P gồm mệnh đề S (không chứa yếu tố đệ quy) và P : P ≡ P[ S, P ].

v Thực thi giải thuật đệ quy có thể dẫn tới một tiến trình gọi đệ quy không kết thúc khi nó không có khả năng gặp trường hợp dừng, 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 đặt ra. Để kiểm soát quá trình gọi đệ quy của giải thuật đệ quy P người ta thường gắn thao tác gọi P với việc kiểm tra một điều kiện B xác định và biến đổi qua mỗi lần gọi P, quá trình gọi P sẽ dừng khi B 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à:

P ≡ if B then P[ S, P]

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

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

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

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

v Trong các ứng dụng thực tế số lần gọi đệ quy (độ sâu đệ quy) không những phải hữu hạn mà còn phải đủ nhỏ. Bởi vì một lần gọi đệ quy sẽ cần một vùng nhớ mới trong khi vùng nhớ cũ vẫn phải duy trì.

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

v Các hàm đệ quy: Định nghĩa 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 mô tả các dãy số hồi quy.

Ví dụ: Dãy số Fibonaci(FiBo):

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

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

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

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

· Nhận xét: Một định nghĩa 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 đơn giản (không đệ quy).

Ví dụ: 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(n) = FiBo(n – 1) + FiBo(n – 2).

v 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 thường được sử dụng để mô tả các thao tác trên cấu trúc dữ liệu có tính đệ quy.

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

Không phải mọi ngôn 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 ngôn 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 ngôn ngữ lập trình hiện nay đề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 ngữ C++ cho phép mã hóa giải thuật đệ quy một cách thuận lợi nhờ vào kỹ thuật khai báo trước tiêu đề nên không có sự phân biệt hình 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 đơn giản thường gặp:

a. Đệ 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 đơn giản nhất có dạng:

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

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

}

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

b. Đệ 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:

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

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

}

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

c. Đệ 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à:

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

Begin thực hiện S;

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

Else gọi P

End;

}

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

II. Bài Toán Đệ Quy

1. Các bước thực hiện 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 phương pháp đệ quy ta cần thực hiện tuần tự 3 nội dung sau:

– Thông số 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.

a. Thông số hóa bài toán:

Tổng quát hóa bài toán cụ thể 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 ra các thông số cho bài toán tổng quát đặc biệt là nhóm các thông số biểu thị kích thước của bài toán – các thông số điều khiển ( các thông số mà đọ lớn của chúng đặc trưng cho độ phức tạp của bài toán., và giảm đi qua mỗi lần gọi đệ quy.

Ví dụ: n trong hàm FiBo(n) ở ví phần trên.

b. 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 thước bài toán nhỏ nhất), mà giải thuật không đệ quy (thường rất đơn giản).

Ví dụ: FiBo(0) = FiBo(1) = 1 trong ví dụ ở phần trên.

c. Phân rã bài toán tổng quát theo phươ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 chia 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 thước nhỏ hơn.

Ví dụ: Đệ quy giai thừa: FAC(n) = n* FAC(n – 1).

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

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

a. 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 thước khác nhau từ cột A sang cột C theo cách:

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

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

– Trong suốt quá trình chuyển các chồng đĩa ở các cột luôn được xếp đúng(đĩa có kích thước bé được đặt trên đĩa có kích thướ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 vị trí 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à:

T = ( 2^64­ – 1) * t S = 1.84 * 10^19­­ * t S

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

Bài toán phức tạp này có thể giải rất đơn giản bằng giải thuật đệ quy.

Thông số hóa bài toán

Xét bài toán ở mức độ tổng quát nhất: chuyển n (n >= 0) từ cột X sang cột Z lấy cột Y 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(n, X, Y, Z) chứa 4 thông số n, X, Y, Z; n thuộc tập số tự nhiên N; X,Y, Z 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, A, B, C).

Dễ thấy rằng: trong 4 thông số của bài toán thì thông số n là thông số quyết định độ phức tạp của bài toán ( 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), n là thông số điều khiển.

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

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

THN(1, X, Y, Z) ≡ { Move(X, Z) }

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

THN(0, X, Y, Z) ≡ { rỗng }

Phân rã bài toán

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

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

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

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

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

THN(n, X, Y, Z) ≡ { THN (n -1,X,Z,Y) ;

Move ( X, Z ) ;

THN (n -1,Y,X,Z) ;

}

Với n đĩ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 xếp 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 trưng cho độ phức tạp của giải thuật.

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

Ta có: f(0) = 0;

f(1) = 1;

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

do đó: f(n) = 1 + 2 + 2^2­ + … + 2^n-1 = 2ⁿ – 1

Để chuyển 64 đĩa cần 2⁶⁴ – 1 bước hay xấp xỉ 10²⁰ bước. Cần khoảng 10 triệu năm với một máy tính nhanh nhất hiện nay để làm việc này.

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

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

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

Ý tưởng giải thuật:

– Trường hợp neo: b₀ – a₀ < ε

+ Nếu f(a₀).f(b₀) <= 0 thì hàm f có nghiệm trên [a₀, b₀]. Vì ta đang tìm nghiệm xấp xỉ với độ chính xác ε a₀ là nghiệm xấp xỉ cần tìm.

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

– Trường hợp b₀ – a₀ > ε thì chia đôi đoạn [a₀, b₀] 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 f (nếu có), hay một hằng E (đủ lớn) nếu f không có nghiệm xấp xỉ trên [a₀, b₀].

Thông số hóa bài toán.

Xét hàm FUN với 3 thông số là g, a, b, (FUN (g, a, b)) trả về giá trị nghiệm xấp xỉ ε của phương trình g(x) = 0 trên đoạn [a ,b] hoặc giá trị C 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(f,a_0,b₀).

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

b – a < ε

Khi đó:

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

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

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

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

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

– Còn không thì FUN(g, a, b) = Fun(g, c, b). (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 C++

const double epsilon = ; const double E = ;

double FUN(double a , double b )

{ if((b – a) < epsilon ) if(f(a)*f(b) <= epsilon return (a ) ;

else return ( L ) ;

else

{

double c = (a + b ) / 2 ;

double F = FUN(a , c) ;

if( F < E ) return F ;

else return ( FUN(c , b) ) ;

}

}

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

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

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

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

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

2. Xét thủ tục đệ quy tháp Hà Nội – THN(n, X, Y, Z)

void THN( int n , char X,Y,Z)

{

if(n > 0) {

THN(n -1,X,Z,Y ) ;

Move ( X , Z ) ;

THN(n – 1,Y,X,Z ) ;

}

return ;

}

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

Sơ đồ thực hiện lời gọi THN(3, A, B, C) là:

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

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

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

A à C; Aà B; C à B; Aà C; B à A ; B à C; Aà C

– Lời gọi cấp 0: THN(3, A, B, C) sẽ làm nảy sinh 2 lời gọi cấp 1: THN(2,A,B, C); THN(2, B, A, C) cùng với các thông tin của quá trình xử lý còn dang dở.

– Các lời gọi cấp 1: THN(2, A, C, B), THN(2, B, A, C) sẽ làm nãy sinh lời gọi cấp 2: THN(1, A, B, C); THN(1, C, A, B); THN(1, B, C, A); THN(1, C, B, A); cùng với các thông tin của quá trình còn xử lý dang dở.

– Các lời gọi cấp 2: THN(1, A, B, C); THN(1, C, A, B); THN(1, B, C, A); THN(1, A, B, C); sẽ làm nảy sinh các lời gọi cấp 3 dưới dạng THN(0, X, Y, Z); cùng với các thông tin của quá trình xử lý còn dang dở.

Quá trình gọi dừng lại khi gặp trường hợp suy biến.

Quá trình xử lý ngược với quá trình gọi bắt đầu khi thực hiện xong các trường hợp neo nhằm hoàn thiện các bước xử lý còn dang dở song song với quá trình hoàn thiện các lời gọi là quá trình loại bỏ các lưu trữ thông tin giải thuật trung gian.

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

– Ở mỗi lần gọi phải lưu trữ thông tin trạng thái con dang dở của tiến trình xử lý ở thời điểm gọi. Số trạng thái này bằng số lần gọi chưa được hoàn tất.

– Khi thực hiện xong một lần gọi cần khôi phục lại toàn bộ thông tin trạng thái trước khi gọi.

– Lệnh gọi cuối cùng (ứng với trường hợp suy biến) sẽ được hoàn tất đầu tiên, thứ tự dãy các lệnh gọi được hoàn tất ngược với thứ tự gọi, tương ứng dãy thông tin trạng thái được hồi phục theo thứ tự ngược với thứ tự lưu trữ.

Cấu trúc 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 trúc lưu trữ thỏa luật LIFO (Last In First Out). Một kểu cấu trúc lưu trữ thường được sử dụng trong trường hợp này là cấu trúc chồng (Stack).

Trong ngôn ngữ C++ thực hiện cơ chế đệ quy nhờ trong quá trình biên dịch, phần mềm ngôn ngữ tự động phát sinh ra cấu trúc stack để quản lý 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 địa phương (gồm cả các thông số) sẽ được cấp phát vùng nhớ mới ở đỉnh stack. Nhờ vậy các tác động địa phương của thủ tục sẽ không làm thay đổi các trạng thái xử lý còn dang dở.

IV. Khử Đệ Quy

1. Tổng quan vấn đề khử đệ quy.

Đệ quy là phương pháp giúp 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 (gọn gàng, dễ hiểu, dễ chuyển thành chương trình). Nhưng việc xử lý giải thuật đệ quy lại thường làm tốn không gian nhớ và thời gian xử lý, hơn nữa không phải mọi ngôn ngữ lập trình đều cho phép mã hóa đệ quy. Vì vậy, 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 chỉ 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 đề còn gọi 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 bao giờ cũng đơn giản và cho đến nay vẫn chưa có giải 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 quan niệm đệ 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.

Tuy nhiên do việc khử đệ quy không phải bao giờ cũng dễ và vì vậy trong nhiều trường hợp ta cũng phải chấp nhận sử dụng chương trình đệ quy.

2. Các trường hợp khử đệ quy đơn giản

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

v Hàm tính giá trị của dữ liệu mô 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:

F(n) = C Khi n = n₀ ( C là một hằng)

= g(n, f(n, n-1)) khi n> n₀

Ví dụ: Hàm giai thừa FAC(n) = n! = 1 khi n = 0

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

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

long int FAC ( int n)

{ int k = 0;

long int F = 1;

while(k < n) F = ++k * F;

return F;

}

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

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

P(X) ≡ if (B(X)) D(X)

Else {

A(X);

P(f(X));

}

Sơ đồ khối quá trình thực hiện lệnh gọi thủ tục P(X) có dạng sau:

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

While(! B(X))

{

A(X);

X = f(X);

}

D(X);

Ví dụ: Tìm ước chung lớn nhất (UCLN) của 2 số nguyên dựa vào thuật toán Euclide.

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

UCLN(m , n , var us) ≡ if ( n = 0 ) us = m ;

else USCLN(n , m mod n , us ) ;

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

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

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

Tức là:

f(X) ≡ if( C(X) ) return ( f (g(X)));

else return (a(x));

Đoạn chương trình tính f = f(X₀) là:

U = X₀;

While( C(U)) U = g(U);

f = a(U);

Ví dụ: Với m, n >= 0 ta có hàm đệ quy tính UCLN(m, n) là:

UCLN(m ,n ) ≡ if (m != 0 ) return(UCLN ( abs(m – n) , min(m , n) ) ;

else return n ;

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

int USCLN(int m , int n)

{ while( n != 0) { int t1 = m ; int t2 = n ;

m = abs(t1-t2) ;

if(t1<t2) n = t1 ; else n = t2 ;

}

return(m) ;

}

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

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

– Dạng toán học

– Dạng giải mã:

A(X ) ≡ if C(X) return (DS ( A( CS (X) ), FS(CS (X). X) ) );

else return (BS(X));

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(X), CS(Y), DS(U, V), FS(U, V) là các thao tác đơn giản, không có lệnh gọi hàm con. X, Y, U, V 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.

v Sơ đồ tổng quát tính giá trị A(X):

Gọi U₀ ≡ X là giá trị đối số cần tính của hàm A. Việc tính A(U₀) sẽ phát sinh lệnh gọi tính A(U₁) với U₁ = CS(U₀) (giả sử C(U₀) = true).

Cứ như vậy, khi mà C(U_i) còn đúng thì việc tính A(U_i) sẽ phát sinh lệnh tính A(U_{i +1}) với U_{i + 1} = CS(U_i).

Với giả thiết là U₀ = X thuộc miền xác định của A, thì quá trình 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à ∃ k thỏa:

C(U₀) = C(U₁) = … = C(U_{k – 1} ) = true, C(U_k ) = false.

Xét dãy số:

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

U₀ = X {cho trước}

U_{i + 1} = CS(U_i) i = 0 … k-1

+ Dãy: { V_i } = { A(U_i)} (2.)

V₀ = A(U₀ ) = A(X₀) (giá trị cần tính).

V_i = A(U_i ) = DS(A( CS( U_i )), FS(CS(U_i), U_i) )

= DS(A( U_{i + 1})), FS(U_{i + 1}))

= DS(V_{i + 1}, FS(U_{i + 1}, U_i)) với 0 < i < k

V_k = BS(U_k ) (vì C(U_k) =false )

Dựa vào dãy số {U_i}, {V_i} (mô tả bởi (1.) và (2.) ta tính A(X) theo giải thuật sau:

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

(Với C(U₀) = C(U₁) = … = C(U_{k – 1}) = true, C(U_k) = false )

_– Sử dụng giá trị U_i để tính lần được ngược V_i từ k xuống 0 theo (2.), V₀ chính là giá trị cần tính (V₀ = A(X)).

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

– Bước 1: tính U_i bắt đầu từ U₀ theo (2.) lưu vào Stack S.

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

K = 0;

U = X; (U₀ = X)

push(S, U); (chèn U₀ vào đỉnh stack S)

while(C(U)) {

k = k + 1;

U = CS(U); (U_{k + 1} = CS(U_k))

push(S, U); // Chèn U_{k + 1} vào đỉnh Stack S. }

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

pop(S, U) ; (U = U_k)

V = BS(U) ; (C(U_k ) sai; V = V_k = BS (U_k))

for (int i = 0; i < k; i++) {

Y = U;

pop (S, U) ; (U = U_i)

V = DS(V, FS(Y, U )); (C(U_i) đúng; V_i = DS (V_{i + 1}, FS(U_{i + 1}, U_i)))

}

V = A(X₀);

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

a. 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ớ vì cách tổ chức Stack một cách mặc định thích hợp cho mọi trường hợp thường là không tối ưu trong từng trường hợp cụ thể. Vì vậy sẽ rất tốt khi người lập trình chủ động tạo ra cấu trúc dữ liệu Stack đặc dụng cho từng chương trình con đệ quy cụ thể.

b. 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à:

P(X) ≡ if C(X) { D(X) }

else A(X); P(f(X)); B(X);

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

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

A(X), B(X), D(X) là các nhóm lệnh không đệ quy ( không chứa lệnh gọi đến P).

f(X) là hàm của X.

Tiến trình thực hiện thủ tục P(X) là:

+ Nếu C(X) đúng thì thực hiện D(X).

+ Còn không (C(X) sai ) thì thực hiện A(X); gọi P(f(X)); thực hiện B(X). ( B(X) chỉ thực hiện khi P(f(X)) thực hiện xong).

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

Giả sử quá khứ quá trình đệ quy kết thúc sau k lần gọi đệ quy thì ta phải thực hiện một dãy k thao tác B theo thứ tự: B(f^{k -1} (X)) , B(f^{k -2} (X)) , . . . ,B(f(f(X))) ,B(f(X)),B(X).

Để thực hiện dãy thao tác { B(fⁱ (X)) } theo thứ tự ngược với thứ tự phát sinh ta cần dãy dữ liệu { fⁱ (X) } ≡ { X , f(X) , f(f(X)) , . . . , fⁱ(X) , . . . , f^{x -1} (X) }

Trình tự thực hiện P(X) được diễn tả bằng mô hình sau:

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

P(X) ≡ { Creat_Stack (S) ; ( tạo stack S )

While( not (C(X)) { A(X) ;

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

X = f(X) ; }

D(X) ;

While(not(EmptyS(S))) {

POP(S,X) ; ( lấy dữ liệu từ S )

B(X) ;

}

Ví dụ: Thủ tục đệ quy chuyển biểu diễn số từ cơ số thập phân sang nhị phân có dạng:

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

cout<< ( m % 2 ) ; }

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

X là m.

P(X) là Binary(m).

A(X); D(X) là lệnh rỗng.

B(X) là lệnh Write(m %2);

C(X) là (m <= 0).

f(X) = f(m) = m / 2.

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

Binary(m) ≡ { Creat_Stack (S) ;

While ( m > 0 ) {

sdu = m / 2 ;

Push(S,sdu) ;

m = m / 2 ;

    }

While( not(EmptyS(S)) {

POP(S,sdu) ;

cout<< sdu ;

}

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

v 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:

P(X) ≡ if C(X) { D(X) ; }

else {

A(X) ; P(f(X)) ;

B(X) ; P(g(X)) ;

}

Quá trình thực hiện thủ tục P(X) sẽ là:

– Nếu C(X) đúng thì thực hiện D(X).

– Nếu C(X) sai thì thực hiện A(X); gọi P(f(X)); thực hiện B(X); gọi P(g(X)), khi gọi P(g(X)) thì lại phát sinh lệnh A(g(X)) như vậy ngoài việc phải lưu vào stack các giá trị fⁱ (X) ta còn phải lưu vào stack các giá trị gⁱ(X) tương ứng. Khi ta lấy dữ liệu từ stack để thực hiện lệnh B(U) vào stack, … Điều kiện dừng là khi truy xuất tới phần tử lưu đầu tiên trong stack.

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

{ Creat_Stact (S) :

Push (S, (X,1)) ;

While ( not C(X) ) {

A(X) ;

Push (S, (X,2)) ;

X = f(X) ;

}

D(X) ;

POP (S, (X,k)) ;

if ( k != 1) {

B(X) ;

X = g(X) ;

}

until ( k = 1 ) ;

}

Ví dụ: Khử đệ quy thủ tục Tháp Hà Nội.

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

THN(n , X , Y, Z ) ≡ if( n > 0 ) {

THN ( n – 1 , X , Z , Y ) ;

Move ( X , Z ) ;

THN ( n – 1 , Y , X , Z ) ;

}

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

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

X là bộ (n, X, Y, Z).

C(X) là biểu thức boolean (n <= 0).

D(X), A(X) là thao tác rỗng.

B(X) = B(n, X, Y, Z) là thao tác Move(X, Z).

g(X) = g(n, X, Y, Z) = (n -1, Y, X, Z).

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

{ Creat_Stack (S) ;

Push (S ,(n,X,Y,Z,1)) ;

While ( n > 0 ) {

Push (S ,(n,X,Y,Z,2)) ;

n = n – 1 ;

Swap (Y,Z ) ; //(* Swap(a, b) là thủ tục hoán đổi nội dung 2 biến a, b)

}

POP (S,(n,X,Y,Z,k)) ;

if ( k != 1 ) {

Move (X ,Z ) ;

n = n – 1 ;

Swap (X ,Y ) ;

}

until ( k = 1 ) ;

}

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

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

P(X) ≡ if ( C(X)) { D(X) }

else {

A1(X) ; P(f1(X)) ;

A2(X) ; P(f2(X)) ;

……………………….

Ai(X) ; P(fi(X)) ;

……………………….

An(X) ; P(fn(X)) ;

An+1(X) ;

}

Ví dụ: Khử đệ quy cho thủ tục hoán vị.

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

HOAN_VI(V ,n) ≡ if (n = 1 ) cout<< V ;

else for ( int i =1; i<= n; i++ ) {

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

HOAN_VI(V ,n – 1) :

}

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

X là (V, n). // Vector V và số nguyên n.

C(X) là (n =1).

D(X) là cout<<V. // xuật vector V.

A_i(X) là thủ tục Swap(V[n], V[i]) . // (i = 1… n)

A_{n + 1} là thao tác rỗng.

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

{ Creat_Stack (S) ;

Push (S,(V ,n ,1)) ;

While ( n > 1 ) {

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

Push (S ,V , n ,2) ;

n– ;

}

cout<<V ;

POP (S ,(V ,n ,k)) ;

While ( k = n +1 ) { POP(S ,(V ,n ,k) ;

if(k !=1 ) {

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

Push (S ,(V ,n ,k+1) ;

n– ;

}

until(k = 1 ) ;

}

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

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

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

http://vi.wikipedia.org/wiki/Đệ_qui

http://en.wikipedia.org/wiki/Recursion_(computer_science)

– Form Cộng đồng C việt: congdongcviet.com