Các Thuật Toán đệ Quy (Recursive) - IViettech

Thuật toán đệ quy được dùng hiệu quả trong việc giải các bài toán mà có thể biểu diễn dưới dạng các đối tượng, các hàm mà có thể gọi lại chính nó. Sử dụng các thuật toán đệ quy sẽ giúp cho cách giải bài toán trở nên ngắn gọn và dễ hiểu hơn.

Ví dụ:

• Tính n! sẽ viết f(n+1) = f(n) * (n+1)
• Tính tổng n số nguyên đầu tiên s(n+1) = s(n) + (n+1)
• Tính số tiếp theo của dãy fibonaci: f(n+1) = f(n) + f(n-1)

Việc sử dụng các thuật toán đệ quy sẽ giúp cho việc giải các bài toán trở nên ngắn gọn và dễ hiểu. Tuy nhiên, các thuật toán đệ quy ngốn khá nhiều bộ nhớ đệm khi thực hiện nên thỉnh thoảng gây ra lỗi tràn ngăn xếp (stack) rất khó chịu nên một số ngôn ngữ không khuyến khích dùng đệ qui hay nói cách khác nó không thiết kế tối ưu cho các thuật toán đệ quy.

Tuy vậy, một số ngôn ngữ lập trình xem việc xử lý đệ quy như thế mạnh của mình như Python chẳng hạn. Do vậy, việc sử dụng đệ quy hay không còn tùy thuộc vào bài toán và ngôn ngữ lập trình mà bạn sử dụng.

Các bước xử lý bài toán đệ quy

Lấy ví dụ xử lý hàm tính n! với n là biến không âm ta thực hiện như sau:

• Bước cơ sở: Xác định giá trị của hàm tại vị trí mà ta xác định được giá trị. Ví dụ ở bài toán tính n! là lúc n=0, khi đó f(0) =1
• Bước đệ quy: xác định cách tính cho hàm ở bước n bất kỳ. Ví dụ trong bài toán tính n! lúc đó chúng ta có f(n) = f(n-1)*n

Trong phần này, tôi sẽ trình bày các bài toán như:

•  Tính n!
•  Tính và in ra n số trong dãy Fibonacci
•  Tìm kiếm phần tử trên mảng đã sắp xếp (Binary Search)

Ngoài ra, có rất nhiều bài toán khác theo dạng đệ quy mà bạn có thể tham khảo thêm. Một trong những bài toán nổi tiếng thế giới là bài Tháp Hà Nội mà bạn nên tham khảo.

Bài 1: Viết chương trình để nhận một số n, tính và in ra n!.

Phân tích và tìm cách giải

• Đầu vào: nhập vào giá trị n
• Đầu ra: giá trị n!
• Cơ sở lý thuyết:
  • – Bước cơ sở: f(0) =1
  • – Bước đệ qui: f(n)= f(n-1)*n

Cách biểu diễn thuật toán đệ quy

Trong trường hợp này, tôi sử dụng ngôn ngữ giả.

Declare int n

Input n

If n<0

   Print ‘n phai lon hon hoac bang 0 ’

Else

   Print Factorial(n)

Factorial(n){

   If n=0

     Return 1

   Else

     Return n* Factorial(n-1)

}

Bài tiếp:  Thuật toán in dãy Fibonacci

Bài trước: Thuật toán sắp xếp danh sách đối tượng