Khử đệ quy
Trạng thái của tiến trình xử lý một giải thuật ở một thời điểm được đặc trưng bởi nội dung các biến và lệnh cần thực hiện kế tiếp. Với tiến trình xử lý một giải thuật đệ qui ở từng thời điểm thực hiện, con cần lưu trữ cả các trạng thái xử lý đang còn dang ...
Trạng thái của tiến trình xử lý một giải thuật ở một thời điểm được đặc trưng bởi nội dung các biến và lệnh cần thực hiện kế tiếp. Với tiến trình xử lý một giải thuật đệ qui ở từng thời điểm thực hiện, con cần lưu trữ cả các trạng thái xử lý đang còn dang dở .
Xét giải thuật đệ quy tính giai thừa:
FAC ( n ) ≡ if(n = 0 ) then retrun 1 ;
else retrun ( n * FAC (n - 1)) ;
Sơ đồ quá trình tính gía trị 3 ! theo giải thuật đệ quy :
Khi thực hiện lời gọi FAC (3 ) sẽ phát sinh lời gọi FAC (2 ) , đồng thời phải lưu giữ thông tin trạng thái xử lý còn dang dỏ ( FAC ( 3 ) = 3 * FAC ( 2 ) ) . Đến lượt mình
lời gọi FAC ( 2 ) lại làm phát sinh lời gọi FAC (1 ) ,đồng thời vẩn phải lưu trử thông tin trạng thái xử lý còn dang dở ( FAC (2 ) = 2 * FAC ( 1 ) ) ,.. . Cứ như vậy cho tới
khi gặp lời gọi
trường hợp neo ( FAC (0 ) = 1 ) .
Tiếp sau qúa trình gọi là một qúa trình xử lý ngược được thực hiện :
- Dùng giá trị FAC ( 0 ) để tính FAC ( 1 ) theo sơ đồ xử lý còn lưu trử . - Dùng giá trị FAC ( 1 ) để tính FAC ( 2 ) theo sơ đồ xử lý còn lưu trử - Dùng giá trị FAC ( 2 ) để tính FAC ( 3 ) theo sơ đồ xử lý còn lưu trử .
Đồng thời với qúa trình xử lý ngược là qúa trình xóa bỏ các thông tin về giải thuật xử
lý trung gian ( qúa trình thu hồi vùng nhớ ) .
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) :
Xét thủ tục đệ quy tháp Hà Nội THN (n , X , Y , Z)
THN (n : integer ; X ,Y , Z : char)
≡ if (n > 0 ) then
{ THN(n-1,X ,Z ,Y) ; Move(X, Z) ;
THN(n-1,Y,X,Z) ;
}
Để 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à :
Lời gọi c/0 Lới gọi c/1 Lời gọi c/2 Lời gọi c/3
THN(0,A,C,B)
THN(1,A,B,C) A ---> C
THN(0,B,A,C)
THN(2,A,C,B) A ---> B
THN(0,C,B,A)
THN(1,C,A,B) C --->B
THN(0,A,C,B)
THN(3,A,B,C) A ---> C
THN(0,B,A,C)
THN(1,B,C,A) B ---> A
THN(0,C,B,A)
THN(2,B,A,C) B ---> C
THN(0,A,C,B)
THN(1,A,B,C) A ---> C
THN(0,B,A,C)
Với THN(0 ,X , Y , Z ) là trường hợp neo 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 hai lời gọi cấp 1 : THN (2 ,A, C, B) ; THN (2 , B , A , C ) cùng với các thông tin của qúa 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 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 ) ; cùng với các thông tin của qúa trình xử lý còn 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ạng : THN(0 ,X, Y, Z) (thao tác rỗng tương ứng với
trường hợp suy biến ); cùng với các thông tin của qúa 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 .
Qúa 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ý con dang dở song song với quá trình hoàn thiện các lời gọi là qúa 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 qúa 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 (hoàn tất) 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 neo) 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 Firt Out ) . Một kiể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).
Với một chồng S thường cho phép chúng ta thực hiện các thao tác sau trên nó : - Thủ tục Creatstack(S) : Tạo chồng S rỗng
- Thủ tục Push(x,S) : Lưu trữ thêm dữ liệu x vào đĩnh stack S
( x là dữ liệu kiểu đơn giản giản hoặc có cấu trúc )
- Thủ tục Pop(x,S) : Lấy giá trị đang lưu ở đĩnh S chứa vào trong đối tượng dữ
liệu x và loại bỏ giá trị này khỏi S ( lùi đỉnh S xuống một mức ) .
- Hàm Empty(S) : ( kiểu boolean ) Kiểm tra tính rỗng của S : cho giá trị đúng
nếu S rỗng , sai nếu S không rỗng .
Cài đặt cụ thể của S có thể thực hiện bằng nhiều phương pháp phụ thuộc vào từng ngôn ngữ lập trình và từng mục đích sử dụng cụ thể .
Cài đặt ( bằng cấu trúc mảng ) chồng S mà mỗi phần tử là một đối tượng dữ liệu thuộc kiểu T trong PASCAL như sau :
Const sizestack = ;
Type stackType = record
St : array [1 . . sizestack ] of T ;
Top : 0 . . sizestack ;
end ;
Thủ tục Creatstack(S) : tạo chồng S rỗng :
Procedure Creatstack( var S : StackType )
Begin
S.Top := 0 ;
End;
Thủ tục Push(x,S) : Chèn - Lưu trữ thêm dữ liệu x vào đĩnh stack S
( x là dữ liệu kiểu đơn giản giản hoặc có cấu trúc )
Procedure Push( var S : StackType ; x : T) ;
Begin
S.St[S.Top +1] := x ;
S.Top := S.Top + 1 ;
End;
Thủ tục Pop(x,S) : Xóa - Lấy giá trị đang lưu ở đĩnh S chứa vào trong đối
tượng dữ liệu x và loại bỏ giá trị này khỏi S ( lùi đỉnh S xuống một mức ) . Procedure Pop( var S : StackType ; var x : T ) ;
Begin
x := S.St[S.Top] ;
S.Top := S.Top - 1 ;
End;
Hàm Empty(S) : ( Hàm boolean ) Kiểm tra tính rỗng của Stack S
Function Empty( S : StackType ) : boolean ;
Begin
Empty := ( S.Top = 0 ) ; End ;
Mô hình stack S và tác dụng các thao tác trên nó .
3 3 --------- 3 --------- 3 ---------
2 2 --------- 2 -- x 1 --- 2 ---------
1 1 ---x o -- 1 ---x o ---- 1 ---x o ----
Createstack(S) ; Push(S, xo ) ; Push(S,x1 ) ; pop(S,y)
( S.top = 0 ) S.St[1] := xo S.St[2] := x1 y := x1
S.top := 1 S.top := 2 S.Top := 1 ;
NNLT PASCAL và C++ thực hiện được cơ chế đệ qui 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ở.
Đệ 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 trên các NNLT) . Nhưng như đã chỉ ra ở trên việc xử lý giải thuật đệ quy lại thường gây khó khăn cho máy tính (tốn không gian nhớ và thời gian xử lý), hơn nữa không phải mọi NNLT đều cho phép mã hóa giải thuật đệ quy (ví dụ : FORTRAN) . Vì vậy việc thay thế một chương trình đệ quy ( có chứa chương trình con đệ 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 lại là kỹ thuật xây dựng giải thuật không đệ quy tương ứng thay thế giải thuật đệ quy . Rất đáng tiếc việc xậy dựng giải thuật không đệ quy thay thế cho một giải thuật đệ quy đã có lại là một việc không phải bao giờ cũng đơn giản và đế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 .
+ để có được một chương trình không đệ 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 .
Các trường hợp khử đệ quy bằng vòng lặp .
Hàm tính gía tri của dãy dữ liệu mô tả bằng hồi quy .
-Ý tưởng dẫn dắt :
Xét một vòng lặp trong đó sử dụng 1 tập hợp biến W = (V , U ) gồm tập hợp U
các biến bị thay đổi trong vòng lặp và V là các biến còn lại.
Dạng tổng quát của vòng lặp là :
W := Wo ; { Wo = ( Uo,Vo) }
while C(U) do U := g(W) (3.1.1)
Gọi Uo là trạng thái của U ngay trước vòng lặp , Uk với k >0 là trạng thái của U
sau lần lặp thứ k (giả sử còn lặp đến lần k ) .
Ta có :
Uo mang các giá trị được gán ban đầu
Uk = g(W) = g(Uk-1 , Vo ) = f(uk-1) với k = 1 .. n (3.1.2)
Với n là lần lặp cuối cùng , tức C(Uk ) đúng với mọi k < n , C(Un) sai Sau vòng lặp W mang nội dung (Un ,Vo ) .
Ta thấy : để tính gía trị dãy được định nghĩa bởi quan hệ hồi quy dạng (3.1.2) ta có thể dùng giải thuật lặp mô tả bởi đoạn lệnh (3.1.1) .
-Giải thuật tính gía trị của dãy hồi quy thường gặp dạng :
f(n)= C khi n = no ( C là một hằng )
= g(n,f(n -1)) khi n> no
Ví dụ :
Hàm giai thừa FAC (n) = n ! = 1 khi n = 0
= n * FAC(n - 1) khi n > 0
Tổng n số đầu tiên của dãy đan dấu sau : Sn = 1 - 3 + 5 - 7 .. + (-1)n+1 * (2n-1)
S(k) = 1 khi k =1
= S(k-1) + (- 1)k+1 *(2*k-1) với k > 1
- Giải thuật đệ quy tính giá trị f(n)
f(n) = if(n = no) then return C ;
else return (g(n,f(n -1)) ;
- Giải thuật lặp tính giá tri f(n) k := no ; F := C ;
{ F = f(no) }
While( k < n ) do begin
k := k +1 ;
F := g(k,F ) ;
end ; }
{ F = f(n) }
Hoặc : F := C ;
For k := no to n -1 do begin
k := k + 1 ;
F := g(k,F) ; end ;
Trong trường hợp này :
W = U = ( k ,F )
Wo = Uo = ( no,C ) C(U) = ( k < n)
f(W) = f(U) = f(k,F) = (k+1,g(k,F)))
Hàm tính FAC(n) = n! không đệ quy + Trong NN LT PASCAL
Function FAC ( n : integer ) : longint ; var k : integer ;
F : longint ; Begin
F := 1 ; k := 0 ;
while (k < n ) do begin
k := k + 1 ; F := F * k ; end ;
FAC := F ; end ;
hoặc :
Function FAC ( n : integer ) : longint ; var k : integer ;
F : longint ; Begin
F := 1 ;
For k:= 1 to n do F := F * k ; FAC := F ;
end ;
+ Trong NN LT C++ long int FAC ( int n ) { int k = 0 ;
long int F = 1 ;
while ( k < n ) F = ++k * F ; return (F) ;
}
Hoặc :
long int FAC ( int n ) { long int F = 1 ;
for ( int k = 1; k <= n ; k++) F = k * F ; return (F) ;
}
Dạng hàm Sn không đệ quy + trên NN LT Pascal :
Function S(n : integer ) : integer ; var k ,tg : integer ;
Begin
k := 1 ; tg := 1 ;
while ( k < n ) do begin
k := k + 1 ;
if odd (k) then tg := tg + (2 * k - 1 ) else tg := tg - (2 * k - 1 ) ;
end ;
S := tg ;
end ;
+ Trong NN LT C++ int S ( int n )
{ int k = 1 , tg = 1 ;
while ( k < n ) { k ++ ;
if (k%2) tg + = 2 * k - 1 ;
else tg - = 2 * k + 1 ;
}
return ( tg ) ;
}
b) Các thủ tục đệ qui dạng đệ qui đuôi.
Xét thủ tục P dạng :
P(X) ≡ if B(X) then D(X)
else { A(X) ;
P(f(X)) ;
}
Trong đó : X là tập biến ( một hoặc một bộ nhiều biến ).
P(X) là thủ tục đệ quy phụ thuộc X
A(X) ; D(X) là các nhóm thao tác (lệnh ) không đệ quy
f(X) là hàm biến đổi X
Xét qúa trình thi hành P(X) :
gọi Po là lần gọi P thứ 0 (đầu tiên ) P(X)
P1 là lần gọi P thứ 1 (lần 2) P(f(X))
Pi là lần gọi P thứ i ( lần i + 1) P(f(f(...f(X)...)
( P(fi(X)) hợp i lần hàm f )
Trong lần gọi Pi nếu B(fi(X)) không đúng (false) thì thi hành lệnh A và gọi Pi+1 ; nếu B(fi(X)) đúng (true) thì thi hành lệnh D và kết thúc qúa trình gọi . Giả sử P được gọi đúng n +1 lần . Khi đó ở trong lần gọi cuối cùng (thứ n ) Pn thì B(fn(X)) đúng , lệnh D được thi hành và chấm dứt thao tác gọi thủ tục P . 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 ( not B(X) ) do begin
A(X) ;
X := f(X) ; end ;
D(X) ;
Để đổi 1 số nguyên không âm y ở cơ số 10 sang dạng cơ số k ( 2 <= k <= 9 ) với
việc dùng mảng A ( A : array[1 . . size ] of 0..k -1 , size là một hằng được khai báo
trước ) để chứa các ký số trong hệ k phân ( với quy ước ký số có ý nghĩa thấp được
chứa ở chỉ số cao ) khi đó thủ tục đệ quy Convert(x,m) để tạo dãy gía trị : A[0] ,
A[1] , . . . , A[m] như sau (hãy tự giải thích ) :
Convert(n,m) ≡ if n <> 0 then Begin
A[m] := n mod k ;
Convert(n div k , m -1) ;
En
Lệnh gọi Convert(y,n) dùng để đổi số nguyên y trong cơ số 10 sang cơ số k lưu
dãy
ký số trong mảng A ;
Trong ví dụ này ta có :
X là ( n, m ) ;
B(X) là biểu thức boolean not( n <> 0 ) A(X) là lệnh gán A[m] := n mod k ;
f(X) là hàm f(n,m ) = ( n div k , m - 1 ) ;
D(X) là lệnh rỗng
Đoan lệnh lặp tương ứng với thủ tục Convert(x,m) là :
While (n <> 0) then begin
A[m] := n mod k ; { A(X) }
n := n div k ; { X := f(X) }
m := m - 1 ; end ;
Tìm USCLN của 2 số nguyên dựa vào thuật toán Euclide .
- Giải thuật đệ quy (dưới dạng thủ tục ) tìm USCLN(m,n) bằng thuật toán Euclide :
USCLN(m , n , var us) ≡ if ( n = 0 ) then us := m
else USCLN(n , m mod n , us ) ;
- Trong trường hợp này thì :
X là ( m , n , us )
P(X) là USCLN(m ,n ,us)
B(X) là n = 0
D(X) là lệnh gán us := m A(X) là lệnh rỗng
f(X ) là f(m,n,us) = ( n , m mod n ,us )
- Đoạn lệnh lặp tương ứng là :
While (n <> 0 ) do begin
sd := m mod n ;
m := n ;
n := sd ;
end ;
us := m ;
- Thủ tục không đệ quy tương ứng trong Pascal .
Procedure USCLN(m , n : integer ; var us : integer ) ; var sd : integer ;
begin
while ( n <> 0 ) do begin
sd := m mod n ;
m := n ;
n := sd ;
end ;
us := m ; end ;
- Hàm con không đệ quy tương ứng trong C++ void USCLN(int m , int n , int& us ) { while(n != 0 ) { int sd = m % n ; m = n ;
n = sd ;
}
us = m ;
}
c) Các hàm đệ qui dạng đệ qui đuôi (tail-recusive).
Xét hàm đệ qui dạng :
f(g(X)) khi C (X) đúng
f ( X ) =
Tức là :
f ( X )
Tính f(Xo ) .
Ta có :
f(Xo ) = f(g(Xo ))
a (X ) khi C (X) sai
≡ if( C(X) ) then return( f(g(X))
else return( a(x))
vơí C(Xo ) đúng .
= f(g(g(Xo )))
= ...
= f(gk (Xo ))
= a(gk (Xo ))
( gk(xo) = g(g (g (xo)))))
với C(g(Xo )) đúng .
với C(gk-1 (Xo )) đúng . với C(gk (Xo )) sai.
)
Đặt : Uo = Xo = go (Xo )
Ui = gi (Xo ) = g(gi-1 (Xo )) = g(Ui-1 ) với i >= 1
Ta có quan hệ sau
Uo = Xo
Ui = g(Ui-1 ) i = 1 ... k . Với k là số nhỏ nhất mà C(Uk ) sai .
Lúc đó : f(Xo ) = a(Uk )
Vậy đoạn chương trình tính f = f(Xo) là : U := Xo ;
while C(U) do U := g(U) ;
f := a(U) ;
Với m , n > = 0 ta có hàm đệ quy tính USCLN(m,n) là :
USCLN(m ,n ) ≡ if (m <> 0 ) then return(USCLN ( abs(m - n) , min(m , n) ) ; else return n ;
Trong trường hợp này :
X là (m ,n ) ;
C (X) = C(m ,n) là m <> 0 ;
g(X) = g(m ,n ) = (abs(m -n ) , min (m ,n ) ) ;
a(x) = a(m ,n ) = n ;
- Đoạn chương trình tính USCLN(a ,b) là :
m := a ; n := b ;
while ( m <> 0 ) do begin
t1 := m ;
t2 := n ;
m := abs(t1 - t2 ) ;
n := min(t1,t2 ) ;
end ;
USCLN := n ;
- Hàm không đệ qui tương ứng trong Pascal.
Function USCLN(m , n : integer ) : integer ; var t1 , t2 : integer ;
begin
while (n <> 0 ) do begin t1 := m ; t2 := n ;
m := abs(t1 - t2 ) ;
if(t1 < t2 ) then n := t1
else n := t2 ;
end ;
USCLN := m ;
- Dạng hàm 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) ;
}
Dạng hàm đệ qui ARSAC.
Dạng toán học :
DS(A(CS(X) ) , FS(CS(X) , X ) ) ) khi C(X) đúng
A(X) =
BS(X) khi C(X) sai
a2) Dạng mã giả :
A(X ) ≡ if C(X) then 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 đệ qui .
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 véc tơ
Đây là dạng 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 gía trị A(X) :
Gọi Uo = X là gía trị đối số cần tính của hàm A . Việc tính A(Uo) sẽ phát sinh lệnh gọi tính A(U1) với U1 = CS(Uo) ( gỉa sử C(Uo) true ).
Cứ như vậy , khi mà C(Ui ) còn đúng thì việc tính A(Ui ) sẽ phát sinh lệnh tính A(Ui+1) với Ui+1 = CS(Ui ).
Với giả thiết là Uo = 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(Uo) = C(U1) = . . = C(Uk-1) = true , C(Uk) = false.
Xét 2 dãy số :
- Dãy : { Ui } = { CS(Ui) } ( 2.1)
Uo = X { cho trước }
Ui+1 = CS(Ui) i = 0 . . k-1
- Dãy : { Vi } = { A(Ui) } (2.2)
Vo = A(Uo) = A(Xo) ( gía trị cần tính ).
Vi = A(Ui) = DS(A(CS(Ui ), FS(CS(Ui), Ui ) )
= DS(A(Ui+1),FS(Ui+1,Ui))
= DS(Vi+1,FS(Ui+1,Ui)) với 0< i < k ( vì C(Ui) đúng )
Vk = BS(Uk) ( vì C(Uk) = false )
Dựa vào 2 dãy số {Ui } ,{Vi} ( mô tả bởi (2.1) và (2.2) ) ta tính A(X) theo giải thuật
sau :
- Tính và ghi nhớ các Ui từ 0 đến k theo (2.1).
( Với C(Uo) = C(U1) = ...= C(Uk-1) = True , C(Uk) = False )
- Sử dụng dãy gía trị Ui để tính lần ngược Vi từ k xuống 0 theo (2.2) , Vo chính là gía trị cần tính ( Vo = A(X ) ).
Giải thuật không đệ quy tính gía trị hàm Arsac bằng sử dụng cấu trúc Stack .
Để thực hiện giải thuật trên thì dãy Ui phải được tính và lưu trử trong một cấu trúc dữ liệu thích hợp , để khi cần đến (khi tính Vi ) dễ lấy ra sử dụng . Đặc điểm quan
trong của dãy Ui là thỏa luật LIFO : thứ tự sử dụng ngược với thứ tự tạo sinh . Cấu
trúc dữ liệu cho phép lưu trữ thuận lợi dãy phần tử thỏa luật LIFO ( vào sau ra trước - Last In First Out ) là câu trúc Stack
( Trên cấu trúc Stack 2 thao tác cơ bản đặc trưng là :
+ Push(S,X) : Chèn phần tử dữ liệu X vào đĩnh Stack S .
+ Pop(S,X) : Lấy ra khỏi stack S phần tử dữ liệu ở đĩnh và chứa nó
vào biến X ).
Giải thuật không đệ qui tính Vo = A(X) dựa trên 2 công thức (2.1 ) , (2. 2 ) và sử
dụng Stack S là :
+ Bước 1 : tính Ui bắt đầu từ Uo theo (2.1) lưu vào Stack S CreateStack(S) ; ( tạo stack rỗng S )
k := 0 ;
U := X ; ( Uo = X )
push(S,U) ; ( chèn UO vào đĩnh stack S ) while C(U) do begin
k := k+1 ;
U := CS(U) ; ( Uk+1 = CS(Uk))
push (S,U) ; ( chèn Uk+1 vào đĩnh Stack S ) end ;
+ Bước 2 : Lấy dữ liệu trong Stack S tính Vi theo (2. 2) pop(S,U) ; ( U = Uk )
V := BS(U) ; ( C(Uk) sai ; V=Vk = BS (Uk))
for i := k -1 downto 0 do
begin
Y := U ; ( Y = Ui+1)
pop(S,U) ;
V := DS(V,FS(Y,U)) ;
end ;
{ V = A(Xo) }
Hoặc :
( U = Ui )
( C(Ui) đúng ; Vi = DS(Vi+1,FS(Ui+1,Ui)) )
+ Bước 1 : tính Ui bắt đầu từ Uo theo (2.1) lưu vào Stack S CreateStack(S) ; ( tạo stack rỗng S )
U := Xo ; ( Uo = Xo )
push(S,U) ; ( chèn UO vào đĩnh stack S ) while C(U) do begin
U := CS(U) ; ( UK+1 = CS(UK))
push (S,U) ; ( chèn Uk+1 vào đĩnh Stack S ) end ;
+ Bước 2 : Lấy dữ liệu trong Stack S tính Vi theo (2. 2) pop(S,U) ; ( U = Uk )
V := BS(U) ; ( C(Uk) sai ; V=Vk = BS (Uk))
While(not emptystack(S)) do
begin
Y := U ; ( Y = Ui+1)
pop(S,U) ; ( U = Ui )
V := DS(V,FS(Y,U)) ; ( C(Ui) đúng ; Vi =
DS(Vi+1,FS(Ui+1,Ui)) )
end ;
{ V = A(Xo) }
Cơ chế lưu trử dãy dữ liệu LIFO bằng Stack là một đặc trưng của quá trình xử lý giải thuật đệ quy điều cần quan tâm là cấu trúc stack thường chiếm nhiều bộ nhớ . Vì vậy người ta luôn tìm cách tránh dùng nó khi còn tránh được
Trường hợp thủ tục CS là song ánh .
Trường hợp CS là song ánh từ miền D lên miền D thì hàm CS có hàm ngược CS-1 . Gọi hàm ngược của hàm CS là hàm CSM1 .
Ta có : CSM1(CS(X)) = CS-1(CS(X)) = X với ∀ X ∈ D .
Nên : CSM1(Ui+1) = CS-1(CS(Ui)) = Ui với i = k-1, . . ,1,0
Khi đó ta không cần lưu giữ các giá trị trung gian của dãy { Ui } mà chỉ cần xuất phát từ Uk dùng hàm CSM1 để khôi phục lại các gía trị Ui vói i<k . Giải thuật tính A(X ) sẽ trở thành :
+ Bước 1 : Dựa vào (2.1) tính Uk
U := X ; ( Uo = X ) k := 0 ;
while C(U) do begin
k := k+1 ;
U := CS(U) ; ( UK+1 = CS(UK)) end ;
+ Bước 2 : Tính Vk , Vk-1, .. V1, Vo dựa vào Uk ,(2.2) và CSM1 V := BS(U) ; ( V=Vk = BS (Uk) )
for i := k -1 downto 0 do begin
Y := U ; ( Y = Ui+1 )
U := CSM1(U) ; (Ui = CSM1(Ui+1) )
V := DS(V,FS(Y,U)) ;
( Vi = DS(Vi+1,FS(Ui+1,Ui) )
end ;
{ V = Vo = A(X )}
Trường hợp thủ tục DS có tính hoán vị .
Xét công thức tính :
Vi = DS(Vi+1,FS(Ui+1,Ui)) với mọi i<k
Đặt : U’i = FS(Ui+1,Ui )
DS(Vi+1,U’i) = Vi+1 T U’i
Ta có :
Vo = DS(V1, FS(U1,Uo) = DS(V1,U’o) = V1 T U’0 V1 = DS(V2, FS(U2,U1) = DS(V2,U’1) = V2 T U’1 V2 = DS(V3, FS(U3,U2) = DS(V3,U’2) = V3 T U’2
Vi = DS(Vi+1, FS(Ui+1,Ui) = DS(Vi+1,U’i) = Vi+1 T U’i ( 3 - 1 )
Vk-1 = DS(Vk, FS(Uk,Uk-1) = DS(Vk,U’k-1) = Vk T U’k-1
Vk = BS(Uk)
Khi DS có tính hoán vị tức : DS(DS(x,y),z) = DS(DS(x,z),y)
( Viết trên ký hiệu T : (x T y) T z = (x T z) T y
Thực hiện thế lần lượt V1 rồi V2 ... trong công thức Vo.
Ta có :
Vo = V1 T U’0 = ( V2 T U’1) T Uo = ( V2 T U’0 ) T U’1
= ( ( V3 T U’2) T U’o) T U’1 = ((V3 T U’2) T U’o ) T U’1
= ( (V3 T U’o) T U’2 ) T U’1
= ( (V3 T U’o) T U’1 ) T U’2
V0 = ( ... ((( Vk T U’o) T U’1) T U’2 ) T ... ..T U’k-2) T U’k-1 (3 - 2 )
(3 - 2) là một dãy liên tiếp ( một tổng ) k phép toán T mà ta đã biết giải thuật tính. Thực vậy :
Thiết lập dãy Wi như sau : W0 = Vk
Wi = Wi-1 T U’i-1 với i = 1..k
Tức là : Wo = Vk = BS(Uk ) (3 - 3 )
Wi = Wi-1 T U’i-1 = DS(Wi-1,FS(Ui,Ui-1)) i=1..k
Wk chính là gía trị Vo cần tính .
Như vậy giải thuật tính Wk ( Vo = A(X ) ) gồm 2 bước :
Bước 1: Xác định k và Uk theo công thức ( 1 - 1 )
Bước 2: Tính dãy Wi , trong lúc tính thì phải tính lại dãy Ui ,theo ( 3 - 3)
A(X ) = Vo = Wk .
Giải thuật không đệ qui tương ứng dược xem như bài tập .
Dẫn nhập.
Để thực hiện một chương trình con đệ quy thì hệ thống phải tổ chức vùng lưu trữ thỏa quy tắc LIFO (vùng Stack). Vì vậy chỉ những ngôn ngữ lập trình có khả năng tạo vùng nhớ stack mới cho phép tổ chức các chương trình con đệ quy. 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 có ích 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ể .
Phần tiềp theo sẻ trình bày việc khử đệ quy một số dạng thủ tục đệ quy theo hướng thay giải thuật đệ quy bằng các vòng lặp và một cấu trúc dữ liệu kiểu stack thích hợp .
Thủ tục đệ qui chi 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) then D(X
else begin
A(X) ; P(f(X)) ; B(X) ;
end ;
Với :
X là một bién đơn hoặc biến véc tơ.
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) sẻ 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ỉ được 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ọi thì thông tin giải thuật B(Y) lại được sinh ra (nhưng chưa thực hiện ) .
Gỉa sử qúa 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(fk-1(X)) , B(fk-2(X)) , . ,B(f(f(X)))
,B(f(X)),B(X).
Để thực hiện dãy thao tác { B(fi(X)) } theo thứ tự ngược với thứ tự phát sinh ta cần dãy dữ liệu {fi(X) } truy xuất theo nguyên tắc LIFO. Ta sẻ dùng một Stack để lưu trử dãy { fi(X) } ≡ { X , f(X) , f(f(X)) , . . . , fi(X) , . . . , fk-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)) do begin A(X) ;
Push(S,X) ; ( cất gía trị X vào stack S )
X := f(X) ;
end ;
D(X) ;
While(not(EmptyS(S))) do begin
POP(S,X) ; ( lấy dữ liệu từ S )
B(X) ;
end ;
}
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 ) then begin
Binary( m div 2 ) ; write( m mod 2 ) ; end;
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 mod 2 ) ; C(X) là ( m <= 0 ) .
f(X) = f(m) = m div 2 .
Giái thuật thực hiện Binary(m) không đệ quy là :
Binary (m ) ≡ { Creat_Stack (S) ;
While ( m > 0 ) do begin
sdu := m mod 2 ;
Push(S,sdu) ;
m := m div 2 ; end;
While( not(EmptyS(S)) do begin
POP(S,sdu) ;
Write(sdu) ; end;
}
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 :
P(X) ≡ if C(X) then D(X)
else begin
A(X) ; P(f(X)) ; B(X) ; P(g(X)) ; end ;
Qúa 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 gía trị fi(X) ta con phải lưu vào stack các gía trị gi(X) tương ứng . Khi ta lấy dữ liệu từ stack để thực hiện lệnh B(U) mà chưa gặp điều kiện kết thúc thì ta thực hiện P(g(U)) và lại phải lưu gía trị g(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 .
Như vậy là ngoài dữ liệu X , con phải lưu vào ngăn xếp thêm thứ tự lần gọi ( cụm gọi )
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)) ; Repeat
While ( not C(X) ) do begin
A(X) ;
Push (S, (X,2)) ; X := f(X) ; end ;
D(X) ;
POP (S, (X,k)) ;
if ( k <> 1) then begin
B(X) ;
X := g(X) ; end ;
until ( k = 1 ) ;
}
thủ tục Tháp Hà Nội .
+ Dạng đệ quy của thủ tục Tháp Hà Nội là :
THN(n , X , Y, Z ) ≡ if( n > 0 ) then begin
THN ( n - 1 , X , Z , Y ) ;
Move ( X , Z ) ;
THN ( n - 1 , Y , X , Z ) ; end ;
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à thao tác chuyển 1 đĩa từ cột X tới cột Z .
Trong trường hợp này :
Biến 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) ;
f(X) = f(n ,X ,Y ,Z) = (n - 1 , X , Z , Y) .
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)) ; Repeat
While ( n > 0 ) do begin
Push (S ,(n,X,Y,Z,2)) ;
n := n - 1 ;
Swap (Y,Z ) ; (* Swap(a,b) là thủ tục hoán
end ;
POP (S,(n,X,Y,Z,k)) ;
if ( k <> 1 ) then begin
Move (X ,Z ) ;
n := n - 1 ;
Swap (X ,Y ) ;
end ;
until ( k = 1 ) ;
}
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 :
đổi nội dung 2 biến a ,b *)
P(X) ≡ if C(X) then D(X)
else begin
A1(X) ; P(f1(X)) ; A2(X) ; P(f2(X)) ;
Ai(X) ; P(fi(X)) ;
An(X) ; P(fn(X)) ; An+1(X) ;
end ;
Cũng giống như trong trường hợp (3a) là khi quay trở lại sau khi thực hiện một lần đệ quy, cần biết đó là lệnh gọi thuộc nhóm thứ mấy trong dãy lệnh gọi để biết thao tác cần thực hiện tiếp. Vì vậy trong chồng cần giữ thêm vị trí nhóm lệnh gọi .
Dạng lặp tương ứng là :
{ Creat_Stack (S) ; Push(S,(X,1)) ; Repeat
While (not C(X) ) do begin
A1(X) ;
Push (S,(X,2)) ; X := f1(X) ; end ;
D(X) ;
POP(S,(X,k)) ;
While( k = n+1 ) do begin An+1 ;
POP(S,(X,k)) ; end ;
if ( k > 0 ) then begin
Ak(X) ;
Push (S,(X,k+1)); X := f k (X)
end ;
until (k = 1 ) ; }
cho thủ tục hoán vị . + Thủ tục hoán vị dưới dạng đệ quy :
HVI(V ,n) ≡ if (n = 1 ) then Print ( V )
else for i := n downto 1 do
begin
Swap (V[n],V[i] ) ; HVI(V ,n - 1) : end ;
trong trường hợp này thì :
X là bộ (V ,n ) . (* vector V và số nguyên n *)
C(X) là ( n = 1 ) .
D(X) là Print (V) . (* xuất vector V *)
Ai(X) là thủ tục Swap(V[n] ,V[i] ) ( i = 1 .. n ) .
An+1 là thao tác rỗng .
fi(X) = f(V, n ) = ( V, n - 1) .( với i = 1 . . n ) Dạng lặp của thủ tục là :
{ Creat_Stack (S) ; Push (S,(V ,n ,1)) ; Repeat
While ( n > 1 ) do begin
Swap(V[n] ,V[1] ;
Push (S ,V , n ,2) ; n := n -1 ;
end ;
Print (V) ;
POP (S ,(V ,n ,k)) ;
While ( k = n +1 ) do POP(S ,(V ,n ,k) ; if(k <> 1 ) then begin
Swap(V[n] ,V[k]) ;
Push (S ,(V ,n ,k+1) ; n := n - 1 ;
end ;
until(k = 1 ) ;
