Giới thiệu về thuật toán đệ quy – Recursion Algorithm (Phần 1)

Đệ quy (Recursion) là một trong những giải thuật rất quen thuộc trong lập trình. Một số bài toán buộc phải dùng đệ quy mới giải quyết được (như bài toán duyệt cây). Đệ quy là một giải thuật chứa thao tác gọi lại chính nó. Điều này giúp mô tả một dãy lớn các thao tác bằng một số thao tác ngắn gọn trong đó chứa thao tác gọi lại chính nó.

Hôm nay, chúng ta sẽ cùng tìm hiểu một số khái niệm cơ bản về giải thuật đệ quy và một số bài toán kinh điển sử dụng đệ quy.

Định nghĩa hàm đệ quy
Trong lập trình, một hàm được gọi là đệ quy khi nó gọi chính nó trong thân hàm.
Một hàm đệ quy f(n) được xác định dựa trên giản đồ sau:
Phần cơ bản: Điều kiện thoát khỏi đệ quy, bao gồm một giá trị hoặc một tập giá trị ban đầu: f(0),f(1),..
Phần đệ quy: Tính f(n+1) dựa trên một giá trị f(k) đã biết trước đó
Ví dụ:
Tính n! = (n-1)! * n
Dãy fibonacy: f(n) = f(n-1)+ f(n-2)

Giải thuật đệ quy
Là thuật toán gọi lại chính nó với tham số nhỏ hơn.
Phù hợp để xử lý các đối tượng định nghĩa đệ quy
Ngôn ngữ lập trình cấp cao cho phép người lập trình thiết kế các hàm và thủ tục đệ quy.

Ví dụ: một hàm gọi chính nó

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);
	
   printf("%d ",value);   
}

Ví dụ: một hàm mà gọi tới hàm khác mà trả về lời gọi tới hàm ban đầu

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);
	
   printf("%d ",value);   
}

Đặc điểm của hàm đệ quy

Một hàm đệ quy có thể tiếp tục diễn ra vô số lần giống như một vòng lặp vô hạn. Để tránh điều này, bạn phải ghi nhớ hai thuộc tính sau của hàm đệ qui:

  • Điều kiện cơ bản: phải có ít nhất một điều kiện để khi mà gặp điều kiện này thì việc gọi chính hàm đó (gọi đệ qui) sẽ dừng lại.
  • Tiệm cận: mỗi khi hàm đệ quy được gọi thì nó càng tiệm cận tới điều kiện cơ bản.

Ưu và nhược điểm

Giải thuật đệ quy có ưu điểm là thuận lợi cho việc biểu diễn bài toán, đồng thời làm gọn chương trình. Tuy nhiên cũng có nhược điểm, đó là không tối ưu về mặt thời gian (so với sử dụng vòng lặp), gây tốn bộ nhớ.

2 thoughts on “Giới thiệu về thuật toán đệ quy – Recursion Algorithm (Phần 1)

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *