Khóa học CTDL và GT

Bài 5.2: Phân tích và thiết kế giải thuật đệ quy

Chào mừng các bạn quay trở lại với chuỗi bài về Cấu trúc dữ liệu và Giải thuật! Sau khi đã làm quen với những khái niệm cơ bản, hôm nay chúng ta sẽ mở cánh cửa bước vào một thế giới mới đầy quyến rũ và đôi khi "hack não": thế giới của Đệ Quy (Recursion).

Đệ quy không chỉ là một kỹ thuật lập trình; nó là một lối suy nghĩ, một cách tiếp cận vấn đề dựa trên việc chia nhỏ nó thành các phiên bản nhỏ hơn, tương tự chính nó. Nghe có vẻ trừu tượng đúng không? Đừng lo, chúng ta sẽ cùng nhau làm sáng tỏ khái niệm này, tìm hiểu cách phân tích, thiết kế và triển khai các giải thuật đệ quy một cách hiệu quả, kèm theo rất nhiều ví dụ thực tế bằng C++.

Đệ Quy Là Gì? Một Cách Tiếp Cận Tự Lặp

Nói một cách đơn giản nhất, đệ quy là một kỹ thuật trong đó một hàm tự gọi chính nó để giải quyết một vấn đề. Tưởng tượng bạn đứng giữa hai tấm gương song song; bạn sẽ thấy vô số hình ảnh của chính mình lặp lại vô tận. Đệ quy cũng có nét tương đồng như vậy, nhưng không phải là vô tận!

Ý tưởng cốt lõi của đệ quy là: Để giải quyết một vấn đề lớn, chúng ta giải quyết một (hoặc nhiều) phiên bản nhỏ hơn của chính vấn đề đó, rồi sử dụng kết quả để xây dựng lời giải cho vấn đề lớn. Quá trình này lặp lại cho đến khi vấn đề trở nên đủ nhỏ để có thể giải quyết trực tiếp mà không cần gọi đệ quy nữa.

Tại Sao Lại Cần Đệ Quy?

Mặc dù hầu hết các bài toán có thể giải bằng đệ quy cũng có thể giải bằng vòng lặp (lặp - iteration), đệ quy mang lại một số lợi ích đáng kể trong nhiều trường hợp:

1. Tính thanh lịch và súc tích: Đối với những bài toán có bản chất đệ quy (ví dụ: duyệt cây, các bài toán chia để trị, các cấu trúc dữ liệu định nghĩa đệ quy như danh sách liên kết, cây), giải pháp đệ quy thường rất tự nhiên, dễ đọc và ngắn gọn hơn đáng kể so với giải pháp lặp.
2. Tư duy tự nhiên: Đôi khi, việc định nghĩa một vấn đề theo cách đệ quy giúp ta hiểu sâu sắc hơn cấu trúc của vấn đề đó.
3. Phù hợp với một số cấu trúc dữ liệu/giải thuật: Các giải thuật trên cây (duyệt tiền thứ tự, trung thứ tự, hậu thứ tự), đồ thị (DFS), hay các giải thuật như QuickSort, MergeSort có cài đặt đệ quy rất trực quan và hiệu quả.

Tuy nhiên, đệ quy cũng có mặt trái cần lưu ý:

• Overhead: Việc gọi hàm đệ quy tốn thêm chi phí (lưu ngữ cảnh hàm vào stack) so với vòng lặp đơn giản.
• Nguy cơ Stack Overflow: Nếu độ sâu đệ quy quá lớn (số lần gọi hàm lồng nhau quá nhiều), bộ nhớ stack có thể bị tràn, gây ra lỗi chương trình.
• Hiệu quả: Một số giải thuật đệ quy đơn giản (như tính Fibonacci ngây thơ) có thể rất kém hiệu quả do tính toán trùng lặp nhiều lần các giá trị con.

Cấu Trúc Của Một Hàm Đệ Quy

Mọi hàm đệ quy "chuẩn mực" đều phải có ít nhất hai phần chính:

1. Trường hợp Cơ sở (Base Case): Đây là điều kiện dừng của đệ quy. Khi đạt đến trường hợp cơ sở, hàm sẽ trả về một giá trị (hoặc thực hiện một hành động) mà không gọi đệ quy nữa. Trường hợp cơ sở là BẮT BUỘC để tránh vòng lặp đệ quy vô tận. Trường hợp cơ sở thường xử lý vấn đề ở dạng đơn giản nhất, không thể chia nhỏ thêm.
2. Bước Đệ Quy (Recursive Step): Đây là phần hàm tự gọi chính nó. Trong bước này, hàm giải quyết vấn đề lớn bằng cách:
   • Gọi đệ quy để giải quyết một hoặc nhiều phiên bản nhỏ hơn của vấn đề ban đầu.
   • Kết hợp kết quả từ các lời gọi đệ quy nhỏ hơn (nếu có) để tạo ra lời giải cho vấn đề hiện tại.

Quan trọng là mỗi lần gọi đệ quy trong Bước Đệ Quy phải làm cho vấn đề tiến gần hơn đến Trường hợp Cơ sở. Nếu không, chúng ta sẽ rơi vào vòng lặp đệ quy vô tận.

Phân Tích và Thiết Kế Giải Thuật Đệ Quy

Quá trình này thường bao gồm các bước sau:

1. Xác định bài toán dưới dạng đệ quy: Định nghĩa rõ ràng bài toán P(input) và mối liên hệ giữa P(input) với các bài toán con P(smaller_input_1), P(smaller_input_2), ...
2. Tìm trường hợp cơ sở: Xác định giá trị nhỏ nhất của input mà bài toán có thể giải quyết trực tiếp mà không cần đệ quy. Đây là điểm dừng của quá trình.
3. Xác định bước đệ quy: Giả sử rằng bạn có thể giải quyết các bài toán con P(smaller_input) (đây là "niềm tin đệ quy" - recursive leap of faith), làm thế nào để sử dụng kết quả đó để giải quyết P(input)? Đây là công thức đệ quy.
4. Đảm bảo tiến về trường hợp cơ sở: Kiểm tra lại xem liệu mỗi lần gọi đệ quy có thực sự làm cho input nhỏ đi (theo một nghĩa nào đó) và cuối cùng chắc chắn đạt đến trường hợp cơ sở hay không.

Hãy cùng xem xét các ví dụ cụ thể để hiểu rõ hơn nhé!

Ví dụ 1: Tính Giai Thừa (Factorial)

Bài toán: Tính giai thừa của một số nguyên không âm n, ký hiệu là n!. Định nghĩa:

• 0! = 1
• n! = n * (n-1)! với n > 0

Đây chính là một định nghĩa đệ quy tự nhiên!

• Xác định bài toán đệ quy: Factorial(n)
• Trường hợp cơ sở: Khi n = 0, Factorial(0) = 1.
• Bước đệ quy: Khi n > 0, Factorial(n) = n * Factorial(n-1).

Hãy viết hàm C++ cho bài toán này:

#include <iostream>

// Hàm tính giai thừa sử dụng đệ quy
long long factorial(int n) {
    // Bước 2: Trường hợp cơ sở - Khi n = 0, trả về 1
    if (n == 0) {
        return 1;
    }
    // Đảm bảo đầu vào hợp lệ (giai thừa chỉ định nghĩa cho số không âm)
    if (n < 0) {
        std::cerr << "Error: Factorial is not defined for negative numbers." << std::endl;
        return -1; // Hoặc ném ngoại lệ
    }

    // Bước 3: Bước đệ quy - n! = n * (n-1)!
    // Hàm tự gọi chính nó với đối số nhỏ hơn (n-1)
    return (long long)n * factorial(n - 1);
}

int main() {
    int num = 5;
    long long result = factorial(num);

    if (result != -1) {
        std::cout << num << "! = " << result << std::endl; // Output: 5! = 120
    }

    num = 0;
    result = factorial(num);
    std::cout << num << "! = " << result << std::endl; // Output: 0! = 1

    num = 10;
    result = factorial(num);
    std::cout << num << "! = " << result << std::endl; // Output: 10! = 3628800

    return 0;
}

Giải thích code:

• Hàm factorial(n) nhận vào một số nguyên n.
• Dòng if (n == 0) kiểm tra Trường hợp cơ sở. Nếu n bằng 0, hàm trả về 1 và dừng lại, không có lời gọi đệ quy nào xảy ra nữa.
• Dòng if (n < 0) xử lý trường hợp đầu vào không hợp lệ (mặc dù định nghĩa toán học không có giai thừa số âm, hàm của chúng ta nên có cách xử lý).
• Dòng return (long long)n * factorial(n - 1); là Bước đệ quy. Hàm gọi chính nó với đối số n - 1. Kết quả của lời gọi đệ quy này (factorial(n - 1)) sau đó được nhân với n và trả về.
• Mỗi lần gọi factorial(n - 1), giá trị của n giảm đi 1, đảm bảo rằng cuối cùng chúng ta sẽ đạt đến Trường hợp cơ sở n = 0.
• Lưu ý sử dụng long long cho kết quả vì giai thừa tăng rất nhanh.

Hãy hình dung cách gọi factorial(3) hoạt động:

1. factorial(3) gọi factorial(2) và đợi kết quả.
2. factorial(2) gọi factorial(1) và đợi kết quả.
3. factorial(1) gọi factorial(0) và đợi kết quả.
4. factorial(0) đạt Trường hợp cơ sở, trả về 1.
5. factorial(1) nhận kết quả 1 từ factorial(0), tính 1 * 1 = 1, trả về 1.
6. factorial(2) nhận kết quả 1 từ factorial(1), tính 2 * 1 = 2, trả về 2.
7. factorial(3) nhận kết quả 2 từ factorial(2), tính 3 * 2 = 6, trả về 6.

Đây là cách ngăn xếp (call stack) hoạt động để quản lý các lời gọi đệ quy lồng nhau.

Ví dụ 2: Dãy Fibonacci

Bài toán: Tính số Fibonacci thứ n trong dãy Fibonacci, ký hiệu là F(n). Dãy Fibonacci bắt đầu bằng 0, 1, 1, 2, 3, 5, 8, ... Định nghĩa:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) với n > 1

Đây cũng là một định nghĩa đệ quy rõ ràng.

• Xác định bài toán đệ quy: Fibonacci(n)
• Trường hợp cơ sở: Khi n = 0, Fibonacci(0) = 0. Khi n = 1, Fibonacci(1) = 1. (Có hai trường hợp cơ sở ở đây).
• Bước đệ quy: Khi n > 1, Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2).

Code C++:

#include <iostream>

// Hàm tính số Fibonacci thứ n sử dụng đệ quy
int fibonacci(int n) {
    // Bước 2: Trường hợp cơ sở
    if (n <= 1) {
        return n;
    }

    // Đảm bảo đầu vào hợp lệ (thường tính từ F(0) trở đi)
    if (n < 0) {
        std::cerr << "Error: Fibonacci is typically defined for non-negative integers." << std::endl;
        return -1; // Hoặc ném ngoại lệ
    }

    // Bước 3: Bước đệ quy - F(n) = F(n-1) + F(n-2)
    // Gọi đệ quy 2 lần với các đối số nhỏ hơn (n-1) và (n-2)
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int num = 6; // Tính F(6)
    int result = fibonacci(num);

    if (result != -1) {
        std::cout << "Fibonacci number " << num << " is: " << result << std::endl; // Output: Fibonacci number 6 is: 8
    }

    num = 0;
    result = fibonacci(num);
    std::cout << "Fibonacci number " << num << " is: " << result << std::endl; // Output: Fibonacci number 0 is: 0

    num = 1;
    result = fibonacci(num);
    std::cout << "Fibonacci number " << num << " is: " << result << std::endl; // Output: Fibonacci number 1 is: 1

    return 0;
}

Giải thích code:

• Hàm fibonacci(n) nhận vào số thứ tự n.
• Dòng if (n <= 1) kiểm tra Trường hợp cơ sở. Nếu n là 0 hoặc 1, hàm trả về chính n và dừng.
• Dòng return fibonacci(n - 1) + fibonacci(n - 2); là Bước đệ quy. Hàm gọi chính nó hai lần với n - 1 và n - 2, sau đó cộng kết quả lại.
• Mỗi lần gọi đệ quy đều làm giảm đối số, cuối cùng sẽ đạt đến các trường hợp cơ sở n = 0 hoặc n = 1.

Lưu ý quan trọng về hiệu quả: Mặc dù cài đặt đệ quy cho Fibonacci rất trực quan, nó lại rất kém hiệu quả đối với các giá trị n lớn. Điều này là do có rất nhiều phép tính trùng lặp. Ví dụ, để tính fibonacci(5), chúng ta cần fibonacci(4) và fibonacci(3). Để tính fibonacci(4), chúng ta cần fibonacci(3) và fibonacci(2). Như vậy, fibonacci(3) bị tính hai lần. Đối với n lớn, số lượng các lời gọi hàm trùng lặp tăng theo cấp số mũ. Đây là một ví dụ điển hình về khi nào cần cân nhắc tối ưu hóa đệ quy (bằng kỹ thuật ghi nhớ - memoization hoặc dùng phương pháp lặp/quy hoạch động).

Ví dụ 3: Tính Tổng Các Phần Tử Trong Mảng

Bài toán: Tính tổng của tất cả các phần tử trong một mảng số nguyên. Chúng ta có thể định nghĩa bài toán này một cách đệ quy như sau: Tổng của arr[0...n-1] (mảng có n phần tử) bằng phần tử cuối cùng arr[n-1] cộng với tổng của arr[0...n-2] (mảng có n-1 phần tử).

• Xác định bài toán đệ quy: SumArray(arr, n) - tính tổng của n phần tử đầu tiên trong mảng arr.
• Trường hợp cơ sở: Khi n = 0 (mảng rỗng), tổng là 0.
• Bước đệ quy: Khi n > 0, SumArray(arr, n) = arr[n-1] + SumArray(arr, n-1).

Code C++:

#include <iostream>

// Hàm tính tổng các phần tử trong mảng sử dụng đệ quy
// arr: con trỏ tới mảng (hoặc mảng)
// n: số lượng phần tử cần tính tổng (bắt đầu từ cuối mảng lùi về)
int sumArray(int arr[], int n) {
    // Bước 2: Trường hợp cơ sở - Khi không còn phần tử nào (n <= 0)
    if (n <= 0) {
        return 0;
    }

    // Bước 3: Bước đệ quy - Tổng = phần tử cuối cùng + tổng của phần còn lại
    // arr[n-1] là phần tử cuối cùng trong n phần tử xét đến
    // sumArray(arr, n-1) là tổng của n-1 phần tử đầu tiên
    return arr[n - 1] + sumArray(arr, n - 1);
}

int main() {
    int myArr[] = {1, 2, 3, 4, 5};
    int size = sizeof(myArr) / sizeof(myArr[0]); // Tính kích thước mảng

    int totalSum = sumArray(myArr, size);

    std::cout << "Sum of array elements: " << totalSum << std::endl; // Output: Sum of array elements: 15

    int emptyArr[] = {}; // Mảng rỗng
    size = 0;
    totalSum = sumArray(emptyArr, size);
    std::cout << "Sum of empty array: " << totalSum << std::endl; // Output: Sum of empty array: 0

    return 0;
}

Giải thích code:

• Hàm sumArray(arr, n) tính tổng của n phần tử đầu tiên trong mảng arr. Chúng ta truyền size ban đầu là tổng số phần tử và giảm dần về 0.
• if (n <= 0) là Trường hợp cơ sở. Nếu n bằng 0 (không còn phần tử nào để cộng), trả về 0.
• return arr[n - 1] + sumArray(arr, n - 1); là Bước đệ quy. Nó lấy phần tử cuối cùng của tập hợp n phần tử đang xét (arr[n - 1]) và cộng với tổng của n - 1 phần tử đầu tiên (được tính bởi lời gọi đệ quy sumArray(arr, n - 1)).
• Mỗi lần gọi đệ quy, giá trị n giảm đi 1, tiến gần đến Trường hợp cơ sở n = 0.

Ví dụ 4: Tháp Hà Nội (Tower of Hanoi)

Bài toán Tháp Hà Nội là một ví dụ kinh điển chứng minh vẻ đẹp và sức mạnh của đệ quy, vì giải thuật đệ quy của nó cực kỳ trực quan và dễ hiểu, trong khi việc triển khai lặp lại khá phức tạp.

Bài toán: Cho 3 cái cọc (gọi là cọc nguồn A, cọc đích C, cọc trung gian B) và n đĩa có kích thước khác nhau xếp chồng lên nhau theo thứ tự giảm dần trên cọc nguồn A. Mục tiêu là chuyển toàn bộ n đĩa từ cọc nguồn A sang cọc đích C, tuân thủ các quy tắc sau:

1. Chỉ được di chuyển một đĩa mỗi lần.
2. Chỉ có thể di chuyển đĩa trên cùng của một cọc.
3. Không bao giờ được đặt đĩa lớn hơn lên trên đĩa nhỏ hơn.

Làm thế nào để giải bài toán này bằng đệ quy? Hãy suy nghĩ về cách chuyển n đĩa:

• Trường hợp cơ sở: Nếu chỉ có 1 đĩa (n = 1), ta chỉ cần di chuyển đĩa đó trực tiếp từ cọc nguồn sang cọc đích.
• Bước đệ quy: Để chuyển n đĩa từ A sang C (qua B), ta thực hiện các bước sau:
  1. Chuyển n-1 đĩa nhỏ hơn từ cọc nguồn A sang cọc trung gian B (sử dụng C làm cọc đích tạm thời). Đây là một bài toán con đệ quy!
  2. Di chuyển đĩa lớn nhất (đĩa thứ n) từ cọc nguồn A sang cọc đích C. Đây là một thao tác trực tiếp.
  3. Chuyển n-1 đĩa từ cọc trung gian B sang cọc đích C (sử dụng A làm cọc nguồn tạm thời). Đây lại là một bài toán con đệ quy khác!

Code C++:

#include <iostream>
#include <string>

// Hàm giải bài toán Tháp Hà Nội sử dụng đệ quy
// n: số lượng đĩa cần chuyển
// source: tên cọc nguồn (ví dụ: 'A')
// destination: tên cọc đích (ví dụ: 'C')
// auxiliary: tên cọc trung gian (ví dụ: 'B')
void towerOfHanoi(int n, char source, char destination, char auxiliary) {
    // Bước 2: Trường hợp cơ sở - Nếu chỉ có 1 đĩa
    if (n == 1) {
        std::cout << "Move disk 1 from peg " << source << " to peg " << destination << std::endl;
        return; // Dừng đệ quy
    }

    // Bước 3: Bước đệ quy

    // 1. Chuyển n-1 đĩa từ nguồn sang trung gian (đích là trung gian, nguồn là đích tạm thời)
    towerOfHanoi(n - 1, source, auxiliary, destination);

    // 2. Di chuyển đĩa lớn nhất từ nguồn sang đích
    std::cout << "Move disk " << n << " from peg " << source << " to peg " << destination << std::endl;

    // 3. Chuyển n-1 đĩa từ trung gian sang đích (nguồn là trung gian, trung gian là nguồn tạm thời)
    towerOfHanoi(n - 1, auxiliary, destination, source);
}

int main() {
    int numDisks = 3; // Số lượng đĩa
    std::cout << "Steps to solve Tower of Hanoi with " << numDisks << " disks:" << std::endl;
    // Gọi hàm đệ quy với 3 đĩa, nguồn A, đích C, trung gian B
    towerOfHanoi(numDisks, 'A', 'C', 'B');

    // Output cho numDisks = 3 sẽ là:
    // Move disk 1 from peg A to peg C
    // Move disk 2 from peg A to peg B
    // Move disk 1 from peg C to peg B
    // Move disk 3 from peg A to peg C
    // Move disk 1 from peg B to peg A
    // Move disk 2 from peg B to peg C
    // Move disk 1 from peg A to peg C

    return 0;
}

Giải thích code:

• Hàm towerOfHanoi(n, source, destination, auxiliary) nhận số đĩa n và tên của 3 cọc.
• if (n == 1) là Trường hợp cơ sở. Nếu chỉ có 1 đĩa, in ra bước di chuyển và dừng.
• Dòng towerOfHanoi(n - 1, source, auxiliary, destination); là lời gọi đệ quy đầu tiên trong Bước đệ quy. Nó giải quyết bài toán con: chuyển n-1 đĩa từ source đến auxiliary (coi destination là cọc trung gian).
• Dòng std::cout << ... in ra bước di chuyển đĩa lớn nhất sau khi n-1 đĩa nhỏ hơn đã được dời đi.
• Dòng towerOfHanoi(n - 1, auxiliary, destination, source); là lời gọi đệ quy thứ hai. Nó giải quyết bài toán con còn lại: chuyển n-1 đĩa từ auxiliary đến destination (coi source là cọc trung gian).
• Mỗi lời gọi đệ quy giảm số lượng đĩa n, cuối cùng đạt đến Trường hợp cơ sở n = 1.

Ví dụ này minh họa rõ rệt cách đệ quy cho phép chúng ta giải quyết một vấn đề phức tạp bằng cách phân rã nó thành các phiên bản nhỏ hơn tương tự chính nó.

Phân Tích Hiệu Năng (Thời Gian và Không Gian) Của Giải Thuật Đệ Quy

Khi phân tích giải thuật đệ quy, chúng ta quan tâm đến:

1. Độ phức tạp thời gian (Time Complexity): Thường được biểu diễn bằng các hệ thức truy hồi (recurrence relation). Ví dụ:

   • Factorial: T(n) = T(n-1) + O(1) (một lời gọi đệ quy, một phép nhân). Giải hệ thức này cho ra T(n) = O(n).
   • Fibonacci (ngây thơ): T(n) = T(n-1) + T(n-2) + O(1) (hai lời gọi đệ quy, một phép cộng). Giải hệ thức này cho ra T(n) = O(phi^n), trong đó phi ≈ 1.618 (số vàng) - độ phức tạp theo cấp số mũ, rất tệ.
   • Tower of Hanoi: T(n) = 2 * T(n-1) + O(1) (hai lời gọi đệ quy cho n-1 đĩa, một bước di chuyển đĩa lớn nhất). Giải hệ thức này cho ra T(n) = O(2^n) - cũng theo cấp số mũ. Việc giải các hệ thức truy hồi đòi hỏi kiến thức về toán rời rạc, nhưng ý tưởng cơ bản là biểu diễn chi phí của bài toán lớn dựa trên chi phí của các bài toán con và chi phí của các thao tác khác.

2. Độ phức tạp không gian (Space Complexity): Đệ quy sử dụng bộ nhớ trên ngăn xếp (call stack) để lưu trữ ngữ cảnh của các lời gọi hàm đang chờ hoàn thành. Độ sâu đệ quy tối đa chính là độ phức tạp không gian của giải thuật (tính theo số lượng khung ngăn xếp).

   • Factorial: Độ sâu tối đa là n. Không gian: O(n).
   • Fibonacci (ngây thơ): Độ sâu tối đa là n. Không gian: O(n).
   • Tower of Hanoi: Độ sâu tối đa là n. Không gian: O(n).

So với giải thuật lặp tương đương (nếu tồn tại), giải thuật đệ quy thường có độ phức tạp không gian lớn hơn do sử dụng stack, trong khi giải thuật lặp thường chỉ cần không gian O(1) (ngoại trừ không gian lưu trữ dữ liệu đầu vào/đầu ra).

Đệ Quy và Lặp: Khi Nào Sử Dụng Cái Nào?

• Sử dụng đệ quy khi:
  • Bài toán có định nghĩa hoặc cấu trúc tự nhiên theo kiểu đệ quy (ví dụ: các cấu trúc dữ liệu cây, đồ thị, fractal).
  • Giải pháp đệ quy rõ ràng, dễ đọc và bảo trì hơn so với giải pháp lặp tương đương.
  • Bài toán yêu cầu backtracking hoặc duyệt theo chiều sâu (DFS), vốn có bản chất đệ quy.
• Sử dụng lặp khi:
  • Bài toán có thể giải quyết dễ dàng bằng vòng lặp đơn giản (ví dụ: tính tổng, tìm kiếm tuyến tính).
  • Bạn cần hiệu suất cao nhất về thời gian hoặc không gian (tránh overhead của lời gọi hàm và nguy cơ stack overflow).
  • Giải pháp đệ quy dẫn đến tính toán trùng lặp không cần thiết và việc tối ưu hóa trở nên phức tạp hơn so với chuyển sang lặp.

Nhiều giải thuật đệ quy có thể chuyển đổi sang dạng lặp bằng cách quản lý ngăn xếp một cách tường minh (sử dụng cấu trúc dữ liệu stack). Tuy nhiên, đôi khi việc này làm mất đi sự thanh lịch của giải pháp đệ quy ban đầu.

Các Cạm Bẫy Thường Gặp Khi Sử Dụng Đệ Quy

• Thiếu hoặc Sai Trường hợp Cơ sở: Đây là lỗi phổ biến nhất dẫn đến đệ quy vô tận và tràn stack (stack overflow). Luôn đảm bảo có một hoặc nhiều trường hợp cơ sở và logic của chúng là đúng.
• Không Tiến Về Trường hợp Cơ sở: Đảm bảo mỗi lời gọi đệ quy với đầu vào nhỏ hơn thực sự làm cho vấn đề tiến gần hơn đến trường hợp cơ sở.
• Tính Toán Trùng Lặp: Như ví dụ Fibonacci ngây thơ, cùng một bài toán con được giải quyết nhiều lần. Điều này có thể được khắc phục bằng kỹ thuật ghi nhớ (memoization) hoặc quy hoạch động (dynamic programming), hoặc chuyển sang giải pháp lặp.
• Tràn Ngăn Xếp (Stack Overflow): Xảy ra khi độ sâu đệ quy quá lớn, vượt quá giới hạn bộ nhớ stack của hệ thống. Điều này có thể xảy ra với đầu vào lớn hoặc khi thiếu/sai trường hợp cơ sở.

Bài tập ví dụ:

Đếm mảng

Trong một buổi thực tập tại bệnh viện, FullHouse Dev được giao nhiệm vụ xây dựng hệ thống quản lý thuốc. Để kiểm tra khả năng tư duy logic của họ, người hướng dẫn đã đưa ra một bài toán thú vị về việc đếm các mảng đặc biệt.

Bài toán

Cho một số nguyên \(N\). Bạn cũng được cho \(Q\) truy vấn thuộc loại sau:

Xác định số lượng mảng khác biệt có kích thước \(K\) thỏa mãn các điều kiện:

• Mỗi phần tử trong mảng là số nguyên tố
• Tích của tất cả các phần tử trong mảng bằng \(N\)
• Mảng tạo thành là đối xứng

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\)
• Dòng thứ hai chứa số nguyên \(Q\)
• Dòng tiếp theo chứa \(Q\) số nguyên cách nhau bởi dấu cách, biểu thị giá trị \(K\) cho mỗi truy vấn

OUTPUT FORMAT:

• In ra \(Q\) số nguyên cách nhau bởi dấu cách biểu thị kết quả cho \(Q\) truy vấn theo modulo \(10^9 + 7\)

Ràng buộc:

• \(1 \leq N \leq 10^{12}\)
• \(1 \leq Q \leq 10^5\)
• \(1 \leq K \leq 10^5\)

Ví dụ

INPUT

10
2
3 4

OUTPUT

7 7

Giải thích

Với truy vấn 1 (K = 3): Các mảng thỏa mãn điều kiện là các mảng đối xứng có tích các phần tử bằng 10 và mỗi phần tử là số nguyên tố.

Với truy vấn 2 (K = 4): Tương tự, đây là các mảng đối xứng có độ dài 4, tích các phần tử bằng 10 và mỗi phần tử là số nguyên tố.

Lưu ý:

• Hai mảng được coi là khác biệt nếu tồn tại ít nhất một vị trí mà giá trị phần tử ở hai mảng khác nhau
• Một mảng được gọi là đối xứng nếu đọc từ trái sang phải và từ phải sang trái đều giống nhau Đây là hướng giải bài "Đếm mảng" một cách ngắn gọn:

1. Phân tích N: Bước đầu tiên và quan trọng nhất là phân tích N thành thừa số nguyên tố: N = p1^a1 * p2^a2 * ... * pm^am. Do N <= 10^12, bạn cần thuật toán phân tích hiệu quả (thử chia cho các số nguyên tố đến sqrt(N), phần còn lại xử lý riêng). Lưu trữ các cặp (pi, ai).

2. Tổng số thừa số nguyên tố: Tính tổng các số mũ: TotalExponents = a1 + a2 + ... + am. Đây chính là tổng số phần tử (bao gồm cả lặp lại) trong mảng cần tìm.

3. Kiểm tra điều kiện K: Bất kỳ mảng nào thỏa mãn điều kiện (các phần tử là ước số nguyên tố của N, tích bằng N) đều phải có đúng TotalExponents phần tử (tính cả lặp). Do đó, nếu K != TotalExponents, số lượng mảng thỏa mãn là 0.

4. Sử dụng tính đối xứng: Mảng có kích thước K là đối xứng nghĩa là A[i] = A[K-1-i]. Điều này có nghĩa là các thừa số nguyên tố từ phân tích của N phải được phân bổ vào các vị trí sao cho các cặp đối xứng có giá trị bằng nhau.

5. Xét hai trường hợp cho K:

   • K chẵn (K = 2L): Mảng gồm L cặp đối xứng (A[i], A[K-1-i]) với i từ 0 đến L-1. Mỗi thừa số nguyên tố pi với số mũ ai trong N phải được phân bổ sao cho số lượng pi ở các vị trí 0 đến L-1 là ai/2. Điều này chỉ có thể xảy ra nếu tất cả các số mũ ai đều là số chẵn. Nếu có bất kỳ ai nào là số lẻ, kết quả là 0. Nếu tất cả ai đều chẵn, bài toán trở thành đếm số cách sắp xếp L phần tử, trong đó có ai/2 phần tử là pi cho mỗi i. Số cách này là một tổ hợp lặp (multinomial coefficient): L! / ((a1/2)! * (a2/2)! * ... * (am/2)!).
   • K lẻ (K = 2L + 1): Mảng gồm L cặp đối xứng và 1 phần tử ở giữa A[L]. Thừa số nguyên tố pi ở các vị trí 0 đến L-1 xuất hiện gấp đôi trong mảng đầy đủ. Phần tử ở giữa A[L] xuất hiện một lần. Điều này chỉ có thể xảy ra nếu có đúng một thừa số nguyên tố pk trong phân tích của N có số mũ ak là số lẻ. Nếu có 0 hoặc nhiều hơn 1 thừa số nguyên tố với số mũ lẻ, kết quả là 0. Nếu có đúng một pk với số mũ lẻ ak, thì phần tử ở giữa A[L] phải là pk. Các thừa số nguyên tố còn lại (các pi với i != k, có số mũ ai chẵn) và pk (sau khi "dùng" 1 cho vị trí giữa, còn ak-1 lần, là số chẵn) phải được phân bổ vào L vị trí đầu 0 đến L-1. Số lượng pi cần ở các vị trí này là ai/2 (với i != k) và (ak-1)/2 (với i = k). Bài toán trở thành đếm số cách sắp xếp L phần tử, trong đó có ai/2 phần tử là pi (cho i != k) và (ak-1)/2 phần tử là pk. Số cách này cũng là một tổ hợp lặp: L! / ((a1/2)! * ... * ((ak-1)/2)! * ... * (am/2)!).

6. Tính toán Tổ hợp lặp Modulo: Kết quả cần tính modulo 10^9 + 7. Đây là một số nguyên tố. Công thức N! / (k1! * ... * km!) mod P được tính bằng N! * (k1!)^(-1) * ... * (km!)^(-1) mod P. Sử dụng định lý Fermat Nhỏ để tính nghịch đảo modulo: x^(-1) mod P = x^(P-2) mod P. Bạn nên tiền tính (precompute) giai thừa và nghịch đảo giai thừa modulo để tính nhanh.

7. Xử lý truy vấn Q: Đối với mỗi giá trị K trong truy vấn, áp dụng logic ở bước 3, 4 và 5 để tính kết quả và in ra.

Tóm lại các bước chính:

• Phân tích N thành thừa số nguyên tố: { (p1, a1), ..., (pm, am) }.
• Tính TotalExponents = sum(ai).
• Tiền tính giai thừa và nghịch đảo giai thừa modulo 10^9 + 7.
• Đối với mỗi truy vấn K:
  • Nếu K != TotalExponents, kết quả là 0.
  • Nếu K == TotalExponents:
    • Đếm số lượng ai lẻ (OddExpCount).
    • Nếu K chẵn (K=2L): Nếu OddExpCount > 0, kết quả là 0. Ngược lại, tính L! / prod((ai/2)!) mod M.
    • Nếu K lẻ (K=2L+1): Nếu OddExpCount != 1, kết quả là 0. Ngược lại (giả sử ak là số mũ lẻ duy nhất), tính L! / ((ak-1)/2)! * prod(ai/2)! (i!=k) mod M.

Làm thêm nhiều bài tập miễn phí tại đây