[DSA] Đệ quy
1. Đệ quy
Đệ quy là một kỹ thuật lập trình trong đó một hàm gọi lại chính nó để giải quyết vấn đề. Thay vì sử dụng vòng lặp để thực hiện các công việc lặp lại, đệ quy cho phép lặp lại một khối mã thông qua việc gọi đệ quy với các tham số khác nhau để giải quyết các phần con của vấn đề lớn hơn.
Khi đệ quy được sử dụng, một hàm sẽ gọi chính nó bên trong thân chương trình của nó để giải quyết một vấn đề nhỏ hơn hoặc trường hợp cơ sở (base case - là trường hợp để dừng việc lặp). Kỹ thuật đệ quy thường được sử dụng trong các thuật toán đệ quy như quicksort, mergesort, fibonacci, v.v.
2. Ứng dụng của kỹ thuật đệ quy trong lập trình:
- Thuật toán đệ quy: Đệ quy thường được sử dụng để giải quyết các bài toán đệ quy, ví dụ như thuật toán tìm kiếm nhị phân, thuật toán sắp xếp mergesort và quicksort.
- Cấu trúc dữ liệu đệ quy: Các cấu trúc dữ liệu đệ quy như danh sách liên kết, cây, đồ thị và ngăn xếp thường được hiện thực bằng cách sử dụng đệ quy.
- Kiểm tra và xử lý cây: Kỹ thuật đệ quy rất hữu ích trong việc kiểm tra và xử lý các cây, ví dụ như tìm kiếm các node, thêm hoặc xóa node.
- Tìm kiếm đường đi: Đệ quy có thể được sử dụng để tìm kiếm đường đi trong các đồ thị hoặc các cấu trúc dữ liệu khác.
- Xử lý các chuỗi ký tự: Đệ quy cũng có thể được sử dụng để xử lý các chuỗi ký tự, ví dụ như chuỗi con chung dài nhất, tìm kiếm từ khóa trong chuỗi, v.v.
- Tính toán số học: Các thuật toán đệ quy cũng có thể được sử dụng để tính toán các giá trị số học, ví dụ như tìm số Fibonacci, tính toán giai thừa, v.v.
Tóm lại, đệ quy là một công cụ mạnh mẽ và linh hoạt trong lập trình, nó có thể được sử dụng trong nhiều ngữ cảnh để giải quyết các vấn đề khác nhau.
3. Cách sử dụng đệ quy
Để sử dụng đệ quy trong lập trình, ta sẽ tạo một hàm đệ quy, trong đó hàm sẽ gọi chính nó với một đầu vào khác để giải quyết vấn đề nhỏ hơn, cho đến khi đầu vào đạt đến trạng thái cơ sở. Khi đầu vào đạt đến trạng thái cơ sở, hàm sẽ trả về kết quả cuối cùng.
Ví dụ đơn giản về kỹ thuật đệ quy là tính tổng các số nguyên từ 1 đến n bằng cách sử dụng đệ quy. Ví dụ sau đây sử dụng kỹ thuật đệ quy để tính tổng các số nguyên từ 1 đến n:
#include <stdio.h>
int sum(int n)
{
if (n == 0) {
return 0;
} else {
return n + sum(n - 1);
}
}
int main()
{
int n = 5;
int result = sum(n);
printf("Tong cac so tu 1 den %d la %d\n", n, result);
return 0;
}
Ở ví dụ trên, hàm sum sẽ tính tổng các số từ 1 đến n. Nếu đầu vào n bằng 0, hàm sẽ trả về 0 (trường hợp cơ sở). Nếu không, hàm sẽ trả về tổng của n và kết quả của hàm gọi lại chính nó với đầu vào n-1 (tính toán vấn đề nhỏ hơn).
Trong hàm main, chúng ta sử dụng hàm sum để tính tổng các số từ 1 đến n. Kết quả sẽ được in ra màn hình. Khi chạy chương trình, kết quả sẽ là: "Tổng các số từ 1 đến 5 là 15".
4. Một số bài toán đệ quy:
4.1. Tính giai thừa của một số nguyên dương n:
#include <stdio.h>
int giaiThua(int n)
{
if (n == 0) {
return 1;
} else {
return n * giaiThua(n - 1);
}
}
int main()
{
int n = 5;
int result = giaiThua(n);
printf("Giai thua cua %d la %d\n", n, result);
return 0;
}
4.2. Tìm số Fibonacci thứ n:
#include <stdio.h>
int fibonacci(int n)
{
if (n == 0 || n == 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
int main()
{
int n = 6;
int result = fibonacci(n);
printf("So Fibonacci thu %d la %d\n", n, result);
return 0;
}
4.3. Tìm ước chung lớn nhất của hai số nguyên a và b:
#include <stdio.h>
int ucln(int a, int b)
{
if (b == 0) {
return a;
} else {
return ucln(b, a % b);
}
}
int main()
{
int a = 12, b = 18;
int result = ucln(a, b);
printf("Uoc chung lon nhat cua %d va %d la %d\n", a, b, result);
return 0;
}
4.4. Tìm số lớn nhất trong một mảng số nguyên:
#include <stdio.h>
int maxInArray(int arr[], int n)
{
if (n == 1) {
return arr[0];
} else {
int max = maxInArray(arr, n - 1);
return arr[n - 1] > max ? arr[n - 1] : max;
}
}
int main()
{
int arr[] = { 5, 9, 3, 7, 2 };
int n = 5;
int result = maxInArray(arr, n);
printf("So lon nhat trong mang la %d\n", result);
return 0;
}
4.5. Kiểm tra xem một số có phải là số nguyên tố hay không:
#include <stdio.h>
int isPrime(int n, int i)
{
if (i == 1) {
return 1;
} else {
if (n % i == 0) {
return 0;
} else {
return isPrime(n, i - 1);
}
}
}
int main()
{
int n = 7;
int result = isPrime(n, n / 2);
if (result == 1) {
printf("%d la so nguyen to\n", n);
} else {
printf("%d khong phai la so nguyen to\n", n);
}
return 0;
}
4.6. Tính tổng các chữ số của một số nguyên dương:
#include <stdio.h>
int sumOfDigits(int n)
{
if (n == 0) {
return 0;
} else {
return n % 10 + sumOfDigits(n / 10);
}
}
int main()
{
int n = 12345;
int result = sumOfDigits(n);
printf("Tong cac chu so cua %d la %d\n", n, result);
return 0;
}
5. Một số bài tập về đệ quy:
5.1. Viết chương trình đệ quy để tính lũy thừa của một số
#include <stdio.h>
double power(double base, int exponent) {
if (exponent == 0) {
return 1;
} else if (exponent > 0) {
return base * power(base, exponent-1);
} else {
return 1 / power(base, -exponent);
}
}
int main() {
double base = 2;
int exponent = 5;
double result = power(base, exponent);
printf("%.2f^%d = %.2f", base, exponent, result);
return 0;
}
5.2. Viết chương trình C đệ quy để đảo ngược một chuỗi.
#include <stdio.h>
#include <string.h>
void reverse_string(char* str, int start, int end) {
if (start >= end) {
return;
}
char temp = str[start];
str[start] = str[end];
str[end] = temp;
reverse_string(str, start+1, end-1);
}
int main() {
char str[100];
printf("Enter a string: ");
fgets(str, 100, stdin);
str[strcspn(str, "\n")] = '\0'; // remove the newline character from input
reverse_string(str, 0, strlen(str)-1);
printf("Reversed string: %s", str);
return 0;
}
5.3. Viết một chương trình C đệ quy để kiểm tra xem một chuỗi đã cho có phải là một palindrome hay không.
#include <stdio.h>
#include <string.h>
int isPalindrome(char str[], int left, int right) {
if (left >= right) {
return 1; // Trường hợp đệ quy cơ bản
}
if (str[left] != str[right]) {
return 0; // Không phải palindrome
}
return isPalindrome(str, left + 1, right - 1); // Gọi đệ quy
}
int main() {
char str[100];
printf("Nhập chuỗi: ");
scanf("%s", str);
int len = strlen(str);
if (isPalindrome(str, 0, len - 1)) {
printf("Chuỗi là palindrome.");
} else {
printf("Chuỗi không phải là palindrome.");
}
return 0;
}
5.4. Viết chương trình C đệ quy tìm tổng của một mảng các số nguyên.
#include <stdio.h>
int sumArray(int arr[], int n) {
if (n == 0) {
return 0; // Trường hợp đệ quy cơ bản
}
return arr[n-1] + sumArray(arr, n-1); // Gọi đệ quy
}
int main() {
int arr[100], n, i, sum;
printf("Nhập số phần tử của mảng: ");
scanf("%d", &n);
printf("Nhập các phần tử của mảng:\n");
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
sum = sumArray(arr, n);
printf("Tổng của các phần tử trong mảng là %d.", sum);
return 0;
}
5.5. Viết chương trình C đệ quy để đếm số lần xuất hiện của một ký tự đã cho trong một chuỗi.
Để đếm số lần xuất hiện của một ký tự trong một chuỗi bằng phương pháp đệ quy, ta sử dụng thuật toán như sau:
- Nếu chuỗi là rỗng, trả về 0.
- Nếu ký tự đầu tiên trong chuỗi bằng với ký tự cần đếm, trả về 1 cộng với kết quả đệ quy của phần còn lại của chuỗi.
- Nếu ký tự đầu tiên trong chuỗi không bằng với ký tự cần đếm, trả về kết quả đệ quy của phần còn lại của chuỗi.
#include <stdio.h>
// Hàm đệ quy để đếm số lần xuất hiện của một ký tự trong một chuỗi
int countChar(char* str, char ch) {
if (*str == '\0') {
return 0; // Trường hợp đệ quy cơ bản: chuỗi rỗng
}
if (*str == ch) {
return 1 + countChar(str + 1, ch); // Ký tự đầu tiên trong chuỗi bằng ký tự cần đếm
}
return countChar(str + 1, ch); // Ký tự đầu tiên trong chuỗi không bằng ký tự cần đếm
}
int main() {
char str[] = "hello world";
char ch = 'l';
int count = countChar(str, ch);
printf("So lan xuat hien cua ky tu '%c' trong chuoi '%s' la %d", ch, str, count);
return 0;
}
Trong chương trình trên, hàm countChar được sử dụng để đếm số lần xuất hiện của một ký tự trong một chuỗi bằng phương pháp đệ quy. Tham số str là chuỗi đang xét và ch là ký tự cần đếm.
Trong hàm countChar, nếu chuỗi là rỗng, đây là trường hợp đệ quy cơ bản và ta trả về 0.
Nếu ký tự đầu tiên trong chuỗi bằng với ký tự cần đếm, ta trả về 1 cộng với kết quả đệ quy của phần còn lại của chuỗi.
Nếu ký tự đầu tiên trong chuỗi không bằng với ký tự cần đếm, ta trả về kết quả đệ quy của phần còn lại của chuỗi.
5.6. Viết chương trình C đệ quy để kiểm tra xem một mảng đã cho có được sắp xếp theo thứ tự không giảm hay không.
Để kiểm tra xem một mảng đã cho có được sắp xếp theo thứ tự không giảm hay không bằng phương pháp đệ quy, ta sử dụng thuật toán như sau:
- Nếu mảng có ít hơn hai phần tử, trả về 1 vì một mảng rỗng hoặc chỉ có một phần tử được coi là đã được sắp xếp.
- Nếu phần tử đầu tiên lớn hơn phần tử thứ hai trong mảng, trả về 0 vì mảng không được sắp xếp theo thứ tự không giảm.
- Nếu phần tử đầu tiên nhỏ hơn hoặc bằng phần tử thứ hai trong mảng, ta kiểm tra phần tử thứ hai trở đi bằng cách đệ quy hàm cho phần mảng con từ phần tử thứ hai trở đi đến hết mảng.
#include <stdio.h>
// Hàm đệ quy để kiểm tra một mảng đã cho có được sắp xếp theo thứ tự không giảm hay không
int isNonDecreasing(int arr[], int n) {
if (n < 2) {
return 1; // Trường hợp đệ quy cơ bản: mảng có ít hơn hai phần tử
}
if (arr[0] > arr[1]) {
return 0; // Phần tử đầu tiên lớn hơn phần tử thứ hai trong mảng
}
return isNonDecreasing(arr + 1, n - 1); // Kiểm tra phần tử thứ hai trở đi
}
int main() {
int arr1[] = {1, 2, 3, 4, 5};
int arr2[] = {1, 3, 2, 4, 5};
int n = sizeof(arr1) / sizeof(arr1[0]);
if (isNonDecreasing(arr1, n)) {
printf("Mang arr1 da cho duoc sap xep theo thu tu khong giam");
} else {
printf("Mang arr1 da cho khong duoc sap xep theo thu tu khong giam");
}
if (isNonDecreasing(arr2, n)) {
printf("Mang arr2 da cho duoc sap xep theo thu tu khong giam");
} else {
printf("Mang arr2 da cho khong duoc sap xep theo thu tu khong giam");
}
return 0;
}
5.7. Viết chương trình C đệ quy để in các phần tử của cây nhị phân theo thứ tự duyệt trước.
Để in các phần tử của cây nhị phân theo thứ tự duyệt trước, ta sử dụng phương pháp đệ quy để duyệt cây theo thứ tự như sau:
- In ra giá trị của nút hiện tại.
- Nếu nút hiện tại có cây con bên trái, gọi đệ quy để duyệt cây con bên trái.
- Nếu nút hiện tại có cây con bên phải, gọi đệ quy để duyệt cây con bên phải.
- Dưới đây là mã nguồn C cho chương trình in các phần tử của cây nhị phân theo thứ tự duyệt trước:
#include <stdio.h>
#include <stdlib.h>
// Định nghĩa cấu trúc nút trong cây nhị phân
struct node {
int data;
struct node* left;
struct node* right;
};
// Hàm tạo một nút mới
struct node* newNode(int data) {
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
// Hàm in các phần tử của cây nhị phân theo thứ tự duyệt trước
void preOrder(struct node* node) {
if (node == NULL) {
return; // Trường hợp đệ quy cơ bản
}
printf("%d ", node->data); // In giá trị của nút hiện tại
preOrder(node->left); // Gọi đệ quy để duyệt cây con bên trái
preOrder(node->right); // Gọi đệ quy để duyệt cây con bên phải
}
int main() {
// Tạo cây nhị phân
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
// In các phần tử của cây nhị phân theo thứ tự duyệt trước
printf("Cac phan tu cua cay nhi phan theo thu tu duyet truoc la: ");
preOrder(root);
return 0;
}
=============
Viết chương trình C đệ quy tìm chiều cao của cây nhị phân.
Viết chương trình C đệ quy để tìm số cách leo lên n bậc cầu thang, trong đó bạn có thể đi 1 hoặc 2 bậc cùng một lúc.
Viết chương trình C đệ quy để tạo tất cả các hoán vị có thể có của một chuỗi.
Viết chương trình C đệ quy để kiểm tra xem một cây nhị phân đã cho có phải là cây nhị phân tìm kiếm hay không.
Viết chương trình C đệ quy tìm phần tử nhỏ thứ k trong cây tìm kiếm nhị phân.
Viết chương trình C đệ quy để in tất cả các tập con của một tập hợp đã cho.
Viết chương trình C đệ quy tìm độ dài dãy con chung dài nhất của hai xâu.
Nguồn: chatGPT
Không có nhận xét nào