}
else
{
return
findBisect(cards, card, mid+1, high);
}
}
Tôi đã b sung m t l nh in đ có th theo dõi đ
c m t lo t nh ng l n kích ho t đ quy. Tôi đã th
ổ
ộ ệ
ể
ể
ượ
ộ
ạ
ữ
ầ
ạ ệ
ử
đo n mã sau:
ạ
Card card1 =
new
Card(1, 11);
System.out.println(findBisect(cards, card1, 0, 51));
và nh n đ
c k t qu d
i đây:
ậ
ượ ế
ả ướ
0, 51
0, 24
13, 24
19, 24
22, 24
23
Sau đó tôi l p m t lá bài không có trong c (15 Rô), và th c tìm nó. Tôi đã nh n đ
c k t qu :
ậ
ộ
ỗ
ử ố
ậ
ượ ế
ả
0, 51
0, 24
13, 24
13, 17
13, 14
13, 12
-1
Nh ng phép th này không ch ng minh đ
c r ng ch
ng trình đúng đ n. Th c t là bao nhiêu ki m
ữ
ử
ứ
ượ ằ
ươ
ắ
ự ế
ể
th cũng không th ch ng minh đ
c tính đúng đ n nói trên. Song qua vi c xem xét m t vài tr
ng
ử
ể ứ
ượ
ắ
ệ
ộ
ườ
h p và ki m tra mã l nh, b n có th t thuy t ph c b n thân.
ợ
ể
ệ
ạ
ể ự
ế
ụ ả
S l n kích ho t đ quy th
ng t 6 đ n 7, vì v y ta ch kích ho t
ố ầ
ạ ệ
ườ
ừ
ế
ậ
ỉ
ạ compareCard có 6 ho c 7 l n thôi, so
ặ
ầ
v i t n 52 l n n u tìm ki m tuy n tính. Nói chung, phép chia đôi thì nhanh h n nhi u so v i tìm ki m
ớ ậ
ầ
ế
ế
ế
ơ
ề
ớ
ế
tuy n tính, và cò nhanh n a v i các m ng l n.
ế
ữ ớ
ả
ớ
Có hai l i th
ng g p trong ch
ng trình đ quy, đó là quên đ a vào tr
ng h p c s và vi t l i g i đ
ỗ
ườ
ặ
ươ
ệ
ư
ườ
ợ ơ ở
ế ờ ọ ệ
quy song không bao gi d n đ n tr
ng h p c s . L i sai nào cũng d n đ n đ quy vô h n, và bi t
ờ ẫ
ế
ườ
ợ ơ ở ỗ
ẫ
ế
ệ
ạ
ệ
l
ệ StackOverflowException s đ c phát ra. (Hãy hình dung m t s đ ngăn x p cho m t ph ng th c
ẽ ượ
ộ ơ ồ
ế
ộ
ươ
ứ
đ quy không bao gi k t thúc.)
ệ
ờ ế
13.9 C bài và c bài con
ỗ
ỗ
Sau đây là nguyên m u (xem M c
ẫ
ụ 8.5) c a
ủ findBisect:
public static int
findBisect(Card[] deck, Card card,
int
low,
int
high)
Ta có th coi
ể
cards, low, và high ch là m t thông s quy đ nh m t
ỉ
ộ
ố
ị
ộ c bài con
ỗ
. Cách suy nghĩ này r t
ấ
