Khái Niệm đệ Quy - VOER

Mô tả đệ quy

Trong nhiều tình huống việc mô tả các bài toán, các giải thuật, các sự kiện, các sự vật các quá trình, các cấu trúc, . . . sẽ đơn giản và hiệu quả hơn nếu ta nhìn được nó dưới góc độ mang tính đệ qui.

Mô tả mang tính đệ qui 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ó.

Các 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 )

- Mô tả đệ quy cấu trúc xâu (list) kiểu T : + Cấu trúc rỗng là một xâu kiểu T.

+ Ghép nối một thành phần kiểu T(nút kiểu T ) với một xâu kiểu T ta có một

xâu kiểu T.

- Mô tả đệ quy cây gia phả : Gia phả của một người bao gồm mgười đó và gia phả của cha và gia phả của mẹ.

- Mô tả đê quy thủ tục chọn hoa hậu : + Chọn hoa hậu của từng khu vực. + Chọn hoa hậu của các hoa hậu.

- Mô tả đệ quy thủ tục sắp tăng dãy a[m:n] ( dãy a[m], a[m+1], . . . , a[n] ) bằng phương pháp Sort_Merge (SM) :

SM (a[m:n]) ≡ Merge ( SM(a[m : (n+m) div 2]) , SM (a[(n+m) div 2 +1 : n] ) Với : SM (a[x : x]) là thao tác rỗng (không làm gì cả ).

Merge (a[x : y] , a[(y+1) : z]) là thủ tục trộn 2 dãy tăng a [x : y] , a[(y+1) : z] để được một dãy a[x : z] tăng.

- Đinh nghĩa đệ quy hàm giai thừa FAC( n) = n ! 0 ! = 1

n ! = n * ( n - 1 ) !

Phương pháp đệ quy mạnh ở chổ nó cho phép mô tả một tập lớn các đối tượng chỉ bởi một số ít các mệnh đề hoặc mô tả một giải thuật phức tạp bằng một số ít các thao tác (một chương trình con đệ quy).

Một mô tả đệ quy đầy đủ gồm 2 phần :

- Phần neo : mô tả các trường hợp suy biến của đối tượng (giải thuật) qua một cấu trúc (thao tác) cụ thể xác định .

1 là số tự nhiên, cấu trúc rỗng là một xâu kiểu T, 0 ! = 1 , SM (a[x:x])

là thao tác rỗng.

- Phần quy nạp: mô tả đối tượng (giải thuật) trong trường hợp phổ biến thông qua chính đối tượng (giải thuật ) đó một cách trực tiếp hoặc gián tiếp. Ví dụ : n! = n * (n - 1) !

SM (a[m:n]) ≡ Merge (SM (a[m:( m+n) div 2] , SM (a[(m+n) div 2 +1 : n]) )

Nếu trong mô tả không có phần neo thì đối tượng mô tả có cấu trúc lớn vô hạn, giải thuật mô tả trở thành cấu trúc lặp vô tận.