Slide
Lý thuyết
Đệ quy (Recursion) là kỹ thuật một phương thức tự gọi lại chính nó để giải quyết một bài toán bằng cách chia nhỏ bài toán thành các phiên bản nhỏ hơn giống nhau, cho đến khi đạt đến một điều kiện dừng đơn giản (base case). Một phương thức được gọi là đệ quy nếu nó chứa lời gọi đến chính nó bên trong thân phương thức đó.
Ưu điểm: Code thường ngắn gọn, trực quan và dễ đọc hơn cho những bài toán có tính chất đệ quy.
Nhược điểm: Tốn bộ nhớ (do mỗi lần gọi tạo ra một frame mới trong stack), có thể chậm hơn lặp (vòng lặp) và dễ gây tràn stack nếu không có điều kiện dừng hợp lý.
Một hàm đệ quy yêu cầu có 2 yếu tố sau:
- Giá trị cơ sở: Đây chính là điều kiện để dừng vòng lặp đệ quy.
- Thân hàm: Đây chính là các câu lệnh xử lí trong hàm.
Ứng dụng phổ biến
- Xử lý cấu trúc dữ liệu cây (Tree), đồ thị (Graph).
- Thuật toán tìm kiếm (ví dụ: tìm kiếm nhị phân).
- Sắp xếp (ví dụ: Merge Sort, Quick Sort).
- Tính toán các dãy số như Fibonacci, giai thừa.
Ví dụ: Đệ quy tính tổng từ 1 đến số n
S(n)=1+2+…+n
static int Tong(int n)
{
if (n == 1)
return 1;
return n + Tong(n – 1);
}
Lưu ý quan trọng
- Phải có điều kiện dừng → tránh vòng lặp vô hạn
- Đệ quy sâu quá có thể gây StackOverflow
Bài tập
Bài tập 1. Tính giai thừa
Cho số nguyên n (0 ≤ n ≤ 12). Viết hàm đệ quy tính n! theo công thức đệ quy sau:
n! = + 1, nếu n ≤ 1
n × (n − 1)!, nếu n > 1
Input
• Dòng duy nhất chứa số nguyên n
Output
• Giá trị của n!
namespace ViDu1
{
internal class Program
{
static void Main(string[] args)
{
Console.Write("Mời nhập n: ");
int n = int.Parse(Console.ReadLine());
if (n < 0)
{
Console.Write("Không có giai thừa của số âm");
}
else
{
Console.Write("{0} giai thừa bằng {1}", n, GiaiThua(n));
}
}
static int GiaiThua(int n)
{
if (n == 0)
{
return 1;
}
else
{
return n * GiaiThua(n - 1);
}
}
}
}
Bài tập 2. Tính lũy thừa
Cho hai số nguyên a, n (a > 0, n ≥ 0). Viết hàm đệ quy tính a! theo công thức đệ quy sau:
Input
• Dòng duy nhất chứa hai số nguyên a và n
Output
• Giá trị của a!
namespace ViDu1
{
internal class Program
{
static void Main(string[] args)
{
Console.WriteLine("Nhập a:");
double a = Convert.ToDouble(Console.ReadLine());
Console.WriteLine("Nhập n:");
int n = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Cách 1:a mũ n = {0}", Power(a, n));
Console.WriteLine("Cách 2:a mũ n = {0}", Power1(a, n));
}
static double Power(double a, int n)
{
if (n == 0)
return 1;
else
return (Power(a, n - 1) * a);
}
static double Power1(double a, int n)
{
if (n == 0)
return 1;
else if ((n > 0) && (n % 2 == 0))
return (Power(a, n / 2) * Power(a, n / 2));
else
//((n > 0) && (n % 2 != 0))
return (Power(a, (n - 1) / 2) * Power(a, (n - 1) / 2) * a);
}
}
}
Bài tập 3. Tìm ước số chung lớn nhất bằng thuật toán Euclid
Cài đặt hàm đệ quy sử dụng thuật toán Euclid để tìm Ước số chung lớn nhất (USCLN) của 2 sốnguyên dương m và n. Biết rằng:
Input
• Dòng duy nhất chứa hai số nguyên dương m và n
Output
• USCLN của m và n
class Program
{
static int UCLN(int a, int b)
{
if (b == 0)
return Math.Abs(a); // đảm bảo kết quả luôn dương
return UCLN(b, a % b);
}
static void Main()
{
Console.Write("Nhập a: ");
int a = int.Parse(Console.ReadLine());
Console.Write("Nhập b: ");
int b = int.Parse(Console.ReadLine());
int kq = UCLN(a, b);
Console.WriteLine($"UCLN({a}, {b}) = {kq}");
}
}
Bài tập 4. Chuyển đổi số từ hệ thập phân (DEC) sang hệ nhị phân (BIN)
Cho một số nguyên dương n. Viết hàm đệ quy chuyển đổi một số nguyên dương n từ hệ thập phân (DEC) sang hệ nhị phân (BIN).
Input
• Một dòng duy nhất chứa số nguyên dương n
Output
• Một dòng duy nhất chứa kết quả chuyển số nguyên dương n từ hệ DEC sang hệ BIN
namespace ViDu1
{
internal class Program
{
static void Main(string[] args)
{
Console.WriteLine("Nhập số thập phân:");
int n = Convert.ToInt32(Console.ReadLine());
Console.Write("Số nhị phân là ");
ConvertToBinaryNumber(n);
Console.ReadKey();
}
static void ConvertToBinaryNumber(int number)
{
if (number > 0)
{
ConvertToBinaryNumber(number / 2);
Console.Write(number % 2);
}
}
}
}
Bài tập 5. Bài toán số đôi thỏ
Một đôi thỏ (gồm một thỏ đực và một thỏ cái) không sinh cho đến khi chúng đủ 2 tháng tuổi. Sau khi đủ 2 tháng tuổi, mỗi đôi thỏ sinh một đôi thỏ con (gồm một thỏ đực và một thỏ cái) mỗi tháng. Hỏi sau n tháng có bao nhiêu đôi thỏ, tháng đầu tiên có một đôi thỏ sơ sinh:
Trong hình vẽ trên, ta quy ước:
• Cặp thỏ nâu là cặp thỏ có độ tuổi 1 tháng.
• Cặp thỏ được đánh dấu (màu đỏ và màu xanh) là cặp thỏ có khả năng sinh sản.
Nhìn vào hình vẽ trên ta nhận thấy:
• Tháng đầu tiên và tháng thứ 2: Chỉ có 1 đôi thỏ.
• Tháng thứ ba: đôi thỏ này sẽ đẻ ra một đôi thỏ con, do đó trong tháng này có 2 đôi thỏ.
• Tháng thứ tư: chỉ có đôi thỏ ban đầu sinh con nên đến thời điểm này có 3 đôi thỏ.
• Tháng thứ năm: có hai đôi thỏ (đôi thỏ đầu và đôi thỏ được sinh ra ở tháng thứ ba) cùng sinh con nên ở tháng này có 2 + 3 = 5 đôi thỏ.
• Tháng thứ sáu: có ba đôi thỏ (2 đôi thỏ đầu và đôi thỏ được sinh ra ở tháng thứ tư) cùng sinh con ở thời điểm này nên đến đây có 3 + 5 = 8 đôi thỏ.
Input
• Một dòng duy nhất chứa số nguyên dương n
Output
• Số đôi thỏ ở tháng thứ n
Đây là một bài toán có liên quan tới dãy số Fibonacci nổi tiếng 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 với quy luật là một số bất kì bằng 2 số phía trước cộng lại.
namespace ViDu1
{
internal class Program
{
static void Main(string[] args)
{
Console.WriteLine("Nhập n:");
int n = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Số đôi thỏ ở tháng thứ " + n + " là " + fibonacci(n));
Console.ReadKey();
}
static int fibonacci(int n)
{
if (n < 0)
{
return -1;
}
else if (n == 0 || n == 1)
{
return n;
}
else
{
return fibonacci(n - 1) + fibonacci(n - 2);//đệ quy
}
}
}
}
Bài tập làm thêm (tất cả đều sử dụng đệ quy)
Bài 6*: Giải bài toán tháp Hà Nội
Bài toán tháp Hà Nội có nguồn gốc từ một truyền thuyết Ấn Độ và đã được biết đến rộng rãi do nhà toán học người Pháp, Édouard Lucas, giới thiệu vào năm 1883 trong quyển sách “Récréations Mathématiques”.
Truyền thuyết kể về một ngôi đền cổ ở Ấn Độ, nơi có ba cây cột đá và 64 chiếc đĩa vàng khác kích cỡ. Các linh mục ở đền thờ phải chuyển toàn bộ các đĩa từ một cột sang cột khác, tuân theo quy tắc không bao giờ đặt đĩa lớn hơn lên đĩa nhỏ hơn. Truyền thuyết nói rằng, khi toàn bộ các đĩa được chuyển đến cột mới, thế giới sẽ kết thúc.
Édouard Lucas đã lấy cảm hứng từ truyền thuyết này để tạo ra bài toán tháp Hà Nội, đặt tên theo tên thủ đô của Việt Nam vào thời đó.
Bài toán tháp Hà Nội được mô tả cụ thể như sau:
Cho 3 cây đinh A, B và C và n chiếc đĩa có kích thước khác nhau. Ban đầu, các chiếc đinh được đặt ở cột A, theo thứ tự lớn nhất ở dưới cùng, nhỏ dần khi đến chiếc đĩa cuối cùng.
Mục tiêu của bài toán là di chuyển toàn bộ chiếc đĩa từ chiếc đinh A sang chiếc đinh C, sử dụng chiếc đinh B làm trung gian, tuân thủ các quy tắc sau:
Chỉ có 3 đinh để di chuyển, không có chiếc đinh thứ 4 nào. Một lần chỉ được di chuyển một đĩa, và chỉ được di chuyển chiếc đĩa nằm trên đỉnh của đinh, không được di chuyển đĩa nằm giữa.
Một đĩa chỉ có thể được đặt lên một đĩa lớn hơn, tuy nhiên không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất.
Bài 7*: Tìm tổng các chữ số của 1 số nguyên
Bài 8*: Chuyển số nguyên ở dạng thập phân sang dạng thập lục phân
Hệ thập lục phân (Hexadecimal/Hex – cơ số 16) là hệ đếm sử dụng 16 ký tự: 0-9 và A-F (tương ứng 10-15) để biểu diễn dữ liệu, thường được dùng trong lập trình và khoa học máy tính để rút gọn nhị phân (1 byte = 2 ký tự hex). Nó giúp biểu diễn các số lớn gọn hơn và dễ thao tác với bộ nhớ.
Các đặc điểm chính của hệ thập lục phân:
Ký tự: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A (10), B (11), C (12), D (13), E (14), F (15).
Ứng dụng: Thường dùng trong mã màu (ví dụ: #FFFFFF cho màu trắng), lập trình assembly, địa chỉ bộ nhớ, và gỡ lỗi (debug).
Bài 9*: Tìm kiếm nhị phân
Kiến thức cơ bản: https://blog.28tech.com.vn/c-tim-kiem-nhi-phan
Code C#: https://www.tinhocsoctrang.com/2023/03/tim-kiem-nhi-phan-binary-search-trong-c-sharp.html