Khái niệm đệ quy trong lập trình

Admin

10/09/2023

Share

1. Hiểu một cách đơn giản, đệ quy là gì?

Đầu tiên, chúng ta cần hiểu về khái niệm phương thức trong lập trình. Phương thức là một tập hợp các lệnh được sử dụng để máy tính thực hiện các hành động theo ý muốn của người viết, và có thể chứa các tham số đầu vào. Đệ quy xảy ra khi một phương thức tự gọi hoặc định nghĩa lại chính nó.

Xem ví dụ đơn giản dưới đây. Đề bài: Tính tiến đến từ 0 đến n.

public int sum(int n) {
if (n >= 1) {
      return sum(n - 1) + n;
}
return n;
}

Giải thích:.

Như vậy, hai yếu tố cần thiết để thực hiện một phương pháp đệ quy là:.

Mỗi khi sử dụng đệ quy, chương trình sẽ chạy một vòng và bộ nhớ Stack sẽ được chồng thêm một lớp dữ liệu. Điều này có thể dẫn đến lãng phí bộ nhớ nếu không phân tích kỹ các vòng chạy đệ quy để đảm bảo tính toán hiệu quả. Vấn đề này có thể được giải quyết bằng cách tối ưu hóa đòn bẩy đệ quy đuôi.

Viết code bất cẩn, sẽ có n số khung đệ quy ghi đè lên bộ nhớ Stack

2. Đệ quy đuôi và đệ quy đầu

Vậy câu hỏi đặt ra là đệ quy đuôi khác với đệ quy đầu ở đâu. Chúng ta gọi là đệ quy đuôi khi phương thức đệ quy được đặt ở cuối, sau khi chương trình chạy qua điều kiện dừng. Còn lại thì ta gọi đó là đệ quy đầu. Ví dụ, phương thức ở phần 2 là đệ quy đầu, giờ hãy tiếp tục biến đổi một chút và ta có phương thức đệ quy đuôi tính lũy tiến từ currentSum đến n.

public int tailSum(int currentSum, int n) {
   		 if (n <= 1) {
        	return currentSum + n;
    	}
    		return tailSum(currentSum + n, n - 1);
      }

Phương thức đệ quy đuôi được ưu tiên xử lý dứt điểm, không cần chạy nhiều vòng xử lý điều kiện như phương thức đệ quy đầu, giảm nguy cơ tràn bộ nhớ Stack.

3. Đối chiếu giữa đệ quy và vòng lặp

Phép đệ quy có ưu điểm lớn nhất là tiếp cận vấn đề bằng những đoạn code sạch, gọn gàng, dễ đọc và dễ hiểu. Tuy nhiên, nhược điểm rõ ràng của phép đệ quy là nguy cơ cao tràn bộ nhớ Stack như đã được giải thích trước đó.

Cùng giải quyết một vấn đề nhưng một giải pháp khác để thay thế đệ quy là sử dụng vòng lặp.

Đề bài giống với bài toán tính lũy tiến n ở trên, ta có cách giải quyết với vòng lặp như sau:.

public int iterativeSum(int n) {
             int sum = 0;
             if(n < 0) {
             return 0;
      }
             for(int i=0; i<=n; i++) {
            sum += i;
      }
            return sum;
}

Mặc dù vòng lặp có lợi thế là chỉ cần một vòng duy nhất được gọi và không cần lo lắng về vấn đề tràn bộ nhớ Stack. Tuy nhiên, vòng lặp cũng có nhược điểm so với đệ quy là việc viết mã xử lý sẽ trở nên dài và phức tạp hơn.

4. Các ví dụ mở rộng của đệ quy

Đáng kinh ngạc về sức mạnh thực sự của đệ quy là thay vì phải tạo ra các thuật toán dài dòng với vòng lặp, đệ quy cho phép chúng ta áp dụng tư duy toán học trực tiếp vào thuật toán một cách dễ dàng.

Đề bài: Nhập giá trị n và tìm đơn vị của mười lần n.

Để giải quyết vấn đề, chúng ta thực hiện những bước sau đây:.

public int powerOf10(int n) {
            if (n == 0) {
            return 1;
      }
            return powerOf10(n-1) * 10;
}

5. Chuỗi Fibonacci và phương pháp đệ quy

Dãy Fibonacci là một chuỗi vô hạn các số tự nhiên, bắt đầu bằng hai số 0 và 1. Dãy này được xây dựng theo quy tắc mỗi số trong dãy luôn bằng tổng của hai số trước nó. Dưới đây là một số số Fibonacci: 0 1 1 2 3 5 8 13 21 34 55 ….

Để tìm số Fibonacci thứ n, chúng ta cần sử dụng phương pháp đệ quy và xác định quy luật và điều kiện dừng của dãy số Fibonacci.

public int fibonacci(int n) {
            if (n <= 1) {
            return n;
      }
            return fibonacci(n-1) + fibonacci(n-2);
}

6. Đệ quy trong biểu diễn số thập phân dưới dạng nhị phân

Hãy thử đặt ra một tình huống khi chúng ta cần chuyển đổi một số từ hệ thập phân sang hệ nhị phân, và thực hiện các bước sau:

public String toBinary(int n) {
if (n <= 1 ) {
    return String.valueOf(n);
}
    return toBinary(n / 2) + String.valueOf(n % 2);
      }

7. Tổng kết

Đệ quy là một khái niệm cơ bản trong lập trình và rất hiệu quả trong tư duy giải quyết vấn đề. Nhiều bài toán sau khi phân tích có thể được giải quyết bằng đệ quy và nếu tiếp cận bằng đệ quy, nhiều bài toán khác cũng sẽ giảm được đoạn code dài dòng.