A
B
C
D
F
G
E
H
K
C U TRÚC D LI U VÀ Ấ Ữ Ệ
C U TRÚC D LI U VÀ Ấ Ữ Ệ
GI I THU T (501040)Ả Ậ
GI I THU T (501040)Ả Ậ
Ch ng 5: Đ quiươ ệ
Ch ng 5: Đ quiươ ệ
ĐH Bách Khoa Tp.HCM Ch ng 5: Đ quiươ ệ 2
Khoa Công ngh Thông tinệ
Khái ni m đ quiệ ệ
Khái ni m (đ nh nghĩa) đ qui có dùng l i chính ệ ị ệ ạ
nó.
Ví d : ụgiai th aừ c a n là 1 n u n là 0 ho c là n nhân ủ ế ặ
cho giai th aừ c a n-1 n u n > 0ủ ế
Quá trình đ qui g m 2 ph n:ệ ồ ầ
Tr ng h p c s (base case)ườ ợ ơ ở
Tr ng h p đ qui: c g ng ti n v tr ng h p c ườ ợ ệ ố ắ ế ề ườ ợ ơ
sở
Ví d trên:ụ
Giai th a c a n là 1 n u n là 0ừ ủ ế
Giai th a c a n là n * (giai th a c a n-1) n u n>0ừ ủ ừ ủ ế
ĐH Bách Khoa Tp.HCM Ch ng 5: Đ quiươ ệ 3
Khoa Công ngh Thông tinệ
Tính giai th aừ
Đ nh nghĩa không đ qui:ị ệ
n! = n * (n-1) * … * 1
Đ nh nghĩa đ qui:ị ệ
n! = 1 n u n=0ế
n * (n-1)! n u n>0ế
Mã C++:
int factorial(int n) {
if (n==0) return 1;
else return (n * factorial(n - 1));
}
ĐH Bách Khoa Tp.HCM Ch ng 5: Đ quiươ ệ 4
Khoa Công ngh Thông tinệ
Thi hành hàm tính giai th aừ
n=2
…
2*factorial(1)
factorial (2)
n=1
…
1*factorial(0)
factorial (1)
n=0
…
return 1;
factorial (0)
1
1
6
2
n=3
…
3*factorial(2)
factorial (3)
ĐH Bách Khoa Tp.HCM Ch ng 5: Đ quiươ ệ 5
Khoa Công ngh Thông tinệ
Tr ng thái h th ng khi thi hành ạ ệ ố
hàm tính giai th aừ
factorial(3) factorial(3)
factorial(2)
factorial(3)
factorial(2)
factorial(1)
factorial(3)
factorial(2)
factorial(1)
factorial(0)
factorial(3)
factorial(2)
factorial(1)
factorial(3)
factorial(2)
factorial(3)
t
G i hàmọ
factorial(3)
G i hàmọ
factorial(2)
G i hàmọ
factorial(1)
G i hàmọ
factorial(0)
Tr v t ả ề ừ
hàm
factorial(0
)
Tr v t ả ề ừ
hàm
factorial(1
)
Tr v t ả ề ừ
hàm
factorial(2
)
Tr v t ả ề ừ
hàm
factorial(3
)
Stack h th ngệ ố
Th i gian h th ngờ ệ ố
t
