Đệ quy (Cơ bản) - Nguyễn Trung Thành

 . 
Phân tích: Ta có R(2) = √ √ và R(1) = √ . 
 R(n) = √ ( ). Kiểm tra lại thì ta thấy công thức đúng. 
Và cuối cùng là bước 7: R(4) = √ ≈ 2.485 
R(4) = √ 𝑅( ) 
R(2) = √ 𝑅( ) 
R(3) = √ 𝑅( ) 
R(1) = 1 
Bước 1. Gọi R(3) 
Bước 2. Gọi R(2) 
Bước 3. Gọi R(1) 
Bước 4. Trả về 1 
Bước 5. Trả về √ 
Bắt đầu khó hiểu 
Đệ quy (cơ bản) – Trang 9 
3. Luyện tập viết code 
3a. Trình tự phân tích một bài toán theo kiểu đệ quy 
Bước 4. Viết code 
+ Điểm dừng trước. 
+ Gọi đệ quy sau. 
LƯU Ý : trên đây chỉ là các bước luyện tập với những bài toán đệ quy đơn giản. Đối 
với những bài toán phức tạp hơn thì cần nhiều bước hơn, cần phải có sự tư duy 
cao. 
Luyện tập thử 8 bài toán ví dụ luôn nhé !!! 
Bước 1. Viết S(n) và S(n-1). 
Bước 2. Tìm mối liên hệ giữa S(n) và S(n-1). Biểu diễn S(n) theo S(n-1). 
Bước 3. Tìm điểm dừng (bài toán đơn giản nhất). Thông thường điểm 
dừng là S(1), S(0), 
Đệ quy (cơ bản) – Trang 10 
3b. Những bài toán đơn giản 
Bài toán 1 : vẫn là bài toán quen thuộc . 
Tính S(n) = 1 + 2 + 3 + .. + n. 
Bước 1. Viết S(n) và S(n-1). 
S(n) = 1 + 2 + 3 +  + (n-1) + n 
S(n-1) = 1 + 2 + 3 +  + (n-1) 
Bước 2. Biểu diễn S(n) theo S(n-1). 
S(n) = S(n-1) + n 
Bước 3. Tìm điểm dừng (bài toán đơn giản nhất). 
S(1) = 1 
Bước 4. 
Dòng Mã 
1 
2 
3 
4 
5 
6 
int S (int n) 
{ 
 if (n == 1) return 1; 
 return S(n-1) + n; 
} 
Đệ quy (cơ bản) – Trang 11 
Chạy thử nhé 
Kết quả S(4) = 1 + 2 + 3 + 4 = 10. Chính xác. 
Đệ quy (cơ bản) – Trang 12 
Bài toán 2 : Tính P(n) = 2n. 
Bước 1. 
P(n) = 2 * 2 * 2 *  * 2 * 2 
P(n-1) = 2 * 2 * 2 * ... * 2 
Bước 2. 
P(n) = P(n-1) * 2 
Bước 3. 
P(0) = 1 
Bước 4. 
Dòng Mã 
1 
2 
3 
4 
5 
6 
int P (int n) 
{ 
 if (n == 0) return 1; 
 return P(n-1) * 2; 
} 
n số 2 
n-1 số 2 
Đệ quy (cơ bản) – Trang 13 
Bài toán 3 : Tính P(x,n) = xn (x và n là số nguyên, n ≥ 0). 
Đây là bài toán mở rộng của bài toán số 2 ở trên. 
Hãy tự suy nghĩ 3 bước đầu nhé. 
Bước 4. 
Dòng Mã 
1 
2 
3 
4 
5 
6 
int P (int x, int n) 
{ 
 if (n == 0) return 1; 
 return P(x, n-1) * x; 
} 
Đệ quy (cơ bản) – Trang 14 
Bài toán 4 : 
Tính tổng ( ) 
Bài toán này cũng không quá khó, bạn xem thử code rồi suy nghĩ xem nhé. 
Bước 4. 
Dòng Mã 
1 
2 
3 
4 
5 
6 
float T (int n) 
{ 
 if (n == 1) return 0.5; 
 return T(n-1) + (float)n/(n+1); 
} 
Đệ quy (cơ bản) – Trang 15 
Bài toán 5 : 
Viết hàm kiểm tra xem mảng a có toàn số dương hay không. 
a[0] a[1] a[2]  a[n-2] a[n-1] 
Bước 1 và 2. 
Ta gộp chung cả 2 bước vì ta khó tưởng tượng được. 
- Giả sử ta muốn mảng a có 4 phần tử đều là số dương. 
Tức là từ a*0+ đến a[3+ đều là số dương. 
Hay nói cách khác: từ a*0+ đến a[2] là số dương, và a*3] là số dương. 
- Muốn a*0+ đến a[2] là số dương, 
Thì a*0+ đến a[1] là số dương, và a*2] là số dương. 
 ToànSốDương từ a*0+ đến a[n-1] = ToànSốDương từ a*0+ đến a[n-2+, đồng thời 
a[n-1+ cũng phải là số dương. 
Bước 3. 
Khi mảng a chỉ có 1 phần tử a[0], ta dễ dàng kiểm tra được a[0] là số dương hay 
không. 
Bước 4. 
Dòng Mã 
1 
2 
3 
4 
5 
6 
int ToanSoDuong (int a[], int n) 
{ 
 if (n == 1) return (a[0] % 2 == 0); 
 return ToanSoDuong(a,n-1) && (a[n-1] % 2 == 0); 
} 
Đệ quy (cơ bản) – Trang 16 
3c. Những bài toán phức tạp hơn 
Bài toán 6 : tính R(n) = √ √( ) √( ) √ √ (n dấu căn) 
Bước 1 và bước 2. 
Rõ ràng ta thấy nếu viết R(n) và R(n-1) sẽ rất khó tìm thấy mối liên hệ giữa chúng. 
Đây là bài toán khó hơn :D Ta cứ thử viết đại đi. 
R(2) = √ √ 
R(1) = √ 
 R(n) = √ ( ) 
Đây chỉ là ta dự đoán, ta cần kiểm tra lại bằng máy tính bỏ túi. Kiểm tra lại thì ta 
thấy dự đoán đúng (khỏi cần chứng minh = Toán học :v). 
Bước 3. 
R(1) = √ = 1 
Bước 4. (nhớ khai báo thư viện math.h nhé) 
Dòng Mã 
1 
2 
3 
4 
5 
6 
float R (int n) 
{ 
 if (n == 1) return 1; 
 return sqrt(n + R(n-1)); 
} 
Bạn nên xem lại ví dụ số 3 trong mục “2c. Các ví dụ minh họa” để xem lược đồ gọi 
đệ quy nhé. 
Đệ quy (cơ bản) – Trang 17 
Bài toán 7 : Viết hàm kiểm tra xem N có phải là số có toàn chữ số lẻ hay không. 
Đụng tới các bài toán về chữ số, ta liền nhớ về các chiêu thức div 10 và mod 10. 
 Nếu N có dạng ̅̅ ̅̅ ̅̅ ̅ thì 
+ N / 10 = ̅̅ ̅̅ ̅ 
+ N % 10 = d 
Bước 1 và 2. 
Giả sử số N có dạng ̅̅ ̅̅ ̅̅ ̅ 
Và cuối cùng muốn ̅ có toàn chữ số lẻ thì a là số lẻ, ta dễ dàng xét được. 
Đến đây ta rút ra được : N toàn chữ số lẻ  (N%10 lẻ) và (N/10 toàn chữ số lẻ). 
toàn chữ số lẻ 
số lẻ 
𝑎𝑏𝑐𝑑̅̅ ̅̅ ̅̅ ̅ 
toàn chữ số lẻ 
số lẻ 
𝑎𝑏𝑐̅̅ ̅̅ ̅ 
Muốn 𝑎𝑏𝑐̅̅ ̅̅ ̅ có toàn chữ số lẻ thì 
Muốn 𝑎𝑏𝑐𝑑̅̅ ̅̅ ̅̅ ̅ có toàn chữ số lẻ thì 
toàn chữ số lẻ 
số lẻ 
𝑎𝑏̅̅ ̅ 
Muốn 𝑎𝑏̅̅ ̅ có toàn chữ số lẻ thì 
Đệ quy (cơ bản) – Trang 18 
Bước 3. 
Bài toán đơn giản nhất là khi N có 1 chữ số, ta dễ dàng xét được N là số lẻ hay 
không. 
Bước 4. 
Dòng Mã 
1 
2 
3 
4 
5 
6 
7 
int ToanChuSoLe (int N) 
{ 
 if (N < 10) return (N % 2 == 1); 
 int HangDonVi = N % 10; 
 return (HangDonVi % 2 == 1) && ToanChuSoLe(N/10); 
} 
Đệ quy (cơ bản) – Trang 19 
Lược đồ phác họa các bước đi của bài toán 7 như sau : 
Giả sử N = 1297. Để cho ngắn gọn, ta hiểu hàm ToanChuSoLe là hàm S. 
Và cuối cùng là bước 7: S(1297) = true và false = false. 
Kết luận : 1297 không phải là số có toàn chữ số lẻ. 
S(1297) = (7 lẻ) và S(129) 
Bước 1. Gọi S(129) 
Bước 2. Gọi S(12) 
Bước 3. Gọi S(1) 
Bước 4. Trả về true 
Bước 5. Trả về false 
(vì 2 chẳn) 
false và true = false 
S(129) = (9 lẻ) và S(12) 
S(12) = (2 lẻ) và S(1) 
S(1) = 1 lẻ = true 
7 lẻ S(129) 
Đệ quy (cơ bản) – Trang 20 
Bài toán 8 : Tìm số lớn nhất mảng 1 chiều có n phần tử. 
Ban đầu mình định để cho các bạn suy nghĩ bài này, nhưng mình thấy không ổn 
nên mình làm luôn. 
Mảng a như sau 
a[0] a[1] a[2]  a[n-2] a[n-1] 
Bước 1. 
max (n) = số lớn nhất từ a*0+ đến a[n-1] 
max(n-1) = số lớn nhất từ a*0+ đến a[n-2] 
Bước 2. 
Để tìm max từ a*0+ đến a[n-1], thì ta tìm số lớn nhất từ a*0+ đến a[n-2+, sau đó so 
sánh với a[n-1]. 
Công thức truy hồi sẽ là 
max(n) = số lớn nhất trong 2 số a[n-1] và max(n-1) 
Bước 3. 
Khi n = 1, mảng a chỉ có 1 phần tử duy nhất là a*0+, nên a*0+ cũng là max. 
max(1) = a[0] 
max (n) 
max (n-1) 
Đệ quy (cơ bản) – Trang 21 
Bước 4. 
Dòng Mã 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
int max (int a[], int n) 
{ 
 if (n == 1) return a[0]; 
 int max2 = max (a, n-1); 
 if (a[n-1] > max2) 
 return a[n-1]; 
 else 
 return max2; 
} 
Nói thêm : thật ra các bạn có thể code ngắn gọn hơn như sau 
Dòng Mã ngắn gọn hơn (không khuyến khích sử dụng) 
1 
2 
3 
4 
5 
6 
7 
8 
9 
int max (int a[], int n) 
{ 
 if (n == 1) return a[0]; 
 if (a[n-1] > max(a,n-1)) 
 return a[n-1]; 
 else 
 return max(a,n-1); 
} 
Nhưng chúng ta phải nhớ 1 khuyết điểm của đệ quy là sự bùng nổ tổ hợp. Nếu viết 
code ngắn gọn như trên, ta sẽ gọi hàm max đến 2 lần nếu a[n-1] <= max(a,n-1). 
Tưởng tượng mảng có 50 phần tử = ,49, 48, , 1, 0-. Như vậy trường hợp xui xẻo 
nhất đã xuất hiện: hàm max luôn được gọi 2 lần vì a[i] luôn > a[i+1]. 
Tổng số lần hàm max được gọi là 250 – 1 lần, một con số rất lớn(treo máy). 
Trong khi đó, nếu bạn sử dụng code mẫu của mình ở trên, thì chỉ mất 50 lần gọi 
hàm max mà thôi. 
“Sự chênh lệch vô cùng lớn sẽ tạo ra đẳng cấp khác biệt.” 
Đệ quy (cơ bản) – Trang 22 
4. Bài tập 
Tất cả 8 ví dụ mình làm ở trên, đều thuộc dạng đệ quy tuyến tính. 
Nếu có thời gian, bạn nên luyện tập với bài toán sau : 
a) Tính tổng T(n) = 12 + 22 + 32 +  + n2. 
b) Tính tổng ( ) 
c) Tìm số Fibonacci thứ n. Đây là loại đệ quy nhị phân. 
d) Tìm ước chung lớn nhất của 2 số (2 cách : trừ liên tiếp và chia Euclide). 
e) Đếm các chữ số lẻ của số N. 
f) Ta đã quen thuộc với bài toán S(n) = 1 + 2 + 3 +  + n. 
Dòng Mã 
1 
2 
3 
4 
5 
6 
int S (int n) 
{ 
 if (n == 1) return 1; 
 return S(n-1) + n; 
} 
Có một cách giải khác bằng đệ quy. Để tính tổng 1+2++10 ta gọi hàm S(1,10). 
Dòng Mã 
1 
2 
3 
4 
5 
6 
int S (int i, int n) 
{ 
 if (i == n) return i; 
 return i + S(i+1,n); 
} 
Cách giải này có “bình thường” như những gì ta đã làm ? Khi nào ta mới giải 
được bằng cách “quái lạ” này ? 
Đệ quy (cơ bản) – Trang 23 
g) (nâng cao) Mảng tăng dần. 
Cho mảng a có 3 phần tử. Giá trị mỗi phần tử nằm từ 0 đến 9 (0 ≤ a*i+ ≤ 9). 
Mảng a được gọi là mảng tăng khi a*i+ ≤ a[i+1] với 0 ≤ i < n. 
Ví dụ a = {1,2,3}, a = {2,5,8}, 
Yêu cầu : đếm số lượng mảng a tăng dần (có 3 phần tử). 
Đây là bài giải bình thường. Code chưa được tốt, chưa được tối ưu. 
u chính là a[0], v là a[1] và t là a[2]. 
Dòng Mã 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
void Dem_Mang_Tang() 
{ 
 int dem = 0; 
 for (int u = 0; u <= 9; u++) 
 for (int v = 0; v <= 9; v++) 
 for (int t = 0; t <= 9; t++) 
 if (u <= v && v <= t) 
 { 
 dem++; 
 } 
 printf("So luong mang tang = %d", dem); 
} 
Giả sử mảng a không có 3 phần tử mà có n phần tử thì cách làm bình thường 
có giải được không ? 
Viết hàm đệ quy giải bài toán trên. 
Đệ quy (cơ bản) – Trang 24 
5. Lời kết 
Trên đây chỉ là những điều cơ bản nhất về đệ quy. 
8 bài tập ví dụ đều đi kèm với đầy đủ source code. Mình còn viết một số demo cho 
vài bài tập (các bạn xem trong thư mục demo). 
Đệ quy (cơ bản) – Trang 25 
Mình cũng mất rất là nhiều thời gian để làm tài liệu này trong khi mình có thể vui vẻ 
đi ăn chơi Tết thoải mái. Chỉ có điều mình sợ rằng tài liệu chưa được tốt, có khi đệ 
quy quá khó hiểu sẽ làm cho các bạn dễ bị chết. Sau này các bạn sẽ còn tiếp cận với 
những bài toán đệ quy đẳng cấp cao hơn. Hi vọng nếu bạn vững được gần hết các ý 
trong tài liệu này thì bạn sẽ có một cái nền vững chắc. 
Mình cũng mong rằng nếu nhiệt tình hơn, bạn có thể đóng góp ý kiến về cách trình 
bày của tài liệu, các ví dụ,để cho tài liệu ngày một hoàn thiện hơn. 
Cảm ơn các bạn đã sử dụng tài liệu này. 
Nguyễn Trung Thành. 
Đại học Khoa học Tự nhiên (HCMUS). 
https://www.facebook.com/abcxyztcit 
Email: itga.trial1@yahoo.com.vn