Recursion là gì? Tổng hợp những kiến thức quan trọng về hàm Đệ quy mà bạn nên biết

Recursion là gì? Cách sử dụng hàm như thế nào? Quá trình triển khai hàm đệ quy có tác dụng gì? Vì sao lập trình viên cần có các kiến thức liên quan đến hàm Recursion? Những thắc mắc kể trên sẽ được FPT Shop cập nhật thông qua bài viết dưới đây!

Định nghĩa Recursion là gì?

Recursion là một khái niệm quan trọng mà người lập trình sử dụng để giải quyết các vấn đề theo nguyên tắc đệ quy. Trong lập trình, đệ quy xảy ra khi một hàm gọi chính nó hoặc gọi một hàm khác mà sau đó lại gọi lại chính nó. Trường hợp cơ bản của đệ quy là hàm đệ quy gọi chính nó với một tham số giảm dần đến khi đạt điều kiện dừng.

Để dễ hình dung về hàm đệ quy thì bạn hãy xem nó như một vòng lặp trong lập trình. Tuy nhiên, thay vì sử dụng vòng lặp thì chúng ta gọi lại chính hàm trong hàm. Điều này có thể làm cho mã nguồn trở nên ngắn gọn và dễ đọc hơn trong một số trường hợp.

Một ứng dụng phổ biến của đệ quy là trong giải thuật như việc duyệt cây đệ quy, tính giai thừa hoặc sắp xếp đệ quy. Đặc điểm quan trọng mà bạn cần lưu ý khi sử dụng đệ quy là điều kiện dừng để tránh việc hàm gọi chính nó một cách vô hạn. 

Những ứng dụng cơ bản của hàm Recursion

Hàm đệ quy (Recursion) có nhiều ứng dụng cơ bản và rộng rãi trong lập trình. Dưới đây là một số ví dụ về việc sử dụng đệ quy:

Thuật toán tìm kiếm và sắp xếp

Trong thuật toán tìm kiếm, hàm đệ quy có thể được sử dụng để tìm kiếm các phần tử trong một mảng theo cách đệ quy như sau:

• Tìm kiếm nhị phân (Binary Search): Đệ quy thường được sử dụng để triển khai thuật toán tìm kiếm nhị phân. Trong thuật toán này, danh sách được chia nhỏ thành các phần bằng nhau và sau đó kiểm tra xem giá trị tìm kiếm có trong nửa phần nào. Quá trình này được lặp lại trên nửa phần tương ứng cho đến khi tìm thấy phần tử hoặc xác định rằng phần tử không tồn tại trong danh sách.
• Tìm kiếm đường đi (Path Finding): Trong tìm kiếm đường đi trên đồ thị, đệ quy có thể được sử dụng để duyệt các đỉnh và cạnh của đồ thị để tìm đường đi từ một đỉnh đến đỉnh khác. Thuật toán như Depth-First Search (DFS) và Breadth-First Search (BFS) thường được triển khai bằng đệ quy.

Về sắp xếp, các thuật toán sắp xếp đối với mảng và cấu trúc dữ liệu cũng có thể được triển khai thông qua hàm đệ quy:

• Sắp xếp merge (Merge Sort): Merge Sort là thuật toán sắp xếp chia để trị, trong đó đệ quy được sử dụng để chia mảng thành các phần nhỏ hơn, sắp xếp từng phần đó và sau đó kết hợp chúng lại thành một mảng đã sắp xếp.
• Sắp xếp nhanh (Quick Sort): Quick Sort là thuật toán sắp xếp chọn phân hoạch như một phần tử chốt, sử dụng đệ quy để sắp xếp các phần nhỏ hơn và lớn hơn phần tử chốt, sau đó kết hợp chúng lại với nhau.

Thuật toán trên cây (tree) và đồ thị (graph)

Trong thuật toán trên cây và đồ thị, hàm đệ quy có nhiều ứng dụng quan trọng, bao gồm:

• Duyệt cây (tree traversal): Duyệt các nút trong cây (như cây nhị phân, cây tìm kiếm, cây cân bằng) thường được thực hiện bằng cách sử dụng hàm đệ quy. Các phương pháp duyệt như pre-order, in-order và post-order traversal đều dựa trên kỹ thuật đệ quy để duyệt qua các nút theo thứ tự mong muốn.
• Tìm kiếm trên cây và đồ thị: Trong việc tìm kiếm phần tử trên cây hoặc đồ thị, đệ quy có thể được sử dụng để duyệt qua các nút hoặc đỉnh một cách cần thiết để tìm kiếm phần tử hoặc đường đi. Các thuật toán tìm kiếm như Depth-First Search (DFS) và Breadth-First Search (BFS) thường được triển khai theo cách sử dụng đệ quy.
• Quản lý cấu trúc dữ liệu đệ quy: Trong việc thiết kế và quản lý cấu trúc dữ liệu phức tạp như cây và đồ thị, việc sử dụng hàm đệ qui giúp dễ dàng triển khai các thao tác thêm, xóa và duyệt một cách logic và hiệu quả.

Recursion ứng dụng quy hoạt động

Trong quy hoạch động, hàm đệ quy được sử dụng để giải quyết các vấn đề tối ưu hoá bằng cách tận dụng tính chất tái lập và ghi nhớ kết quả của các bài toán phụ. Cụ thể, ứng dụng của hàm đệ qui trong quy hoạch động bao gồm:

• Tìm kiếm đệ quy (Recursive Search): Trong bài toán quy hoạch động, việc tìm kiếm các cách giải quyết tối ưu thường được thực hiện đệ quy. Thuật toán sẽ thăm dò các khả năng và ghi nhớ các lời giải tối ưu của các bài toán nhỏ hơn
• Tối ưu lời giải (Optimal Solution): Quy hoạch động thường áp dụng đệ quy để xác định các lời giải tối ưu cho các bài toán con, sau đó kết hợp chúng để tạo ra lời giải tối ưu cho toàn bộ bài toán.
• Ghi nhớ kết quả (Memoization): Đệ qui trong quy hoạch động thường được kết hợp với kỹ thuật ghi nhớ kết quả (memoization) để tránh tính toán lại các kết quả đã biết.

Phân tích cấu tạo cơ bản của Recursion

Trường hợp cơ bản của Đệ quy - Base case

Trường hợp cơ bản trong đệ quy là trạng thái cuối cùng mà thuật toán phải đạt đến để thoát khỏi việc lặp lại. Trường hợp cơ bản thường được sử dụng để ngăn chặn việc đệ quy tiếp tục khi đã đạt đến một điều kiện cụ thể.

Một số ví dụ cụ thể về trường hợp cơ bản trong đệ quy bao gồm:

Trong thuật toán tính giai thừa, trường hợp cơ bản là khi n bằng 0 (0! = 1) hoặc n bằng 1 (1! = 1).

Trong thuật toán tìm kiếm nhị phân, trường hợp cơ bản là khi mảng cần tìm kiếm đã được chia nhỏ đến mức lẻ và phần tử cần tìm đã được tìm thấy hoặc không tồn tại.

Trong thuật toán duyệt cây, trường hợp cơ bản là khi đến một nút lá (nút không có con).

Trong tất cả các trường hợp trên, trường hợp cơ bản định nghĩa điều kiện dừng cho đệ quy và ngăn chặn việc lặp vô hạn. Việc xác định và xử lý trường hợp cơ bản một cách chính xác là quan trọng trong việc triển khai đệ quy.

Trường hợp đệ quy - Recursive case

Trường hợp đệ quy (recursive case) là phần của thuật toán đệ quạ tạo ra sự lặp lại, cho phép giải quyết bài toán lớn bằng cách giải quyết các bài toán nhỏ hơn. Trong trường hợp đệ quy, thuật toán sẽ gọi chính nó với một bài toán nhỏ hơn hoặc khác để tiếp tục quá trình giải quyết bài toán gốc.

Ví dụ cụ thể về trường hợp đệ quy bao gồm:

• Tính toán giai thừa: Trong thuật toán tính giai thừa, trường hợp đệ quy thường xảy ra khi n! được tính dựa trên (n-1)!.
• Duyệt cây: Trong thuật toán duyệt cây, trường hợp đệ quy thường xảy ra khi duyệt qua các nút con của một nút cha.
• Thuật toán phân chia và xử lý: Trường hợp đệ quy thường được sử dụng trong thuật toán phân rã một bài toán lớn thành các bài toán nhỏ hơn và xử lý chúng.

Nguyên tắc cần biết khi xây dựng hàm Recursion 

Nguyên tắc xây dựng hàm đệ quy là cơ bản về việc triển khai và sử dụng đệ quy trong lập trình. Các nguyên tắc chính bao gồm:

• Base Case: Mọi hàm đệ quy phải có trường hợp cơ bản, điều này ngăn chặn việc lặp vô hạn và đảm bảo thuật toán kết thúc.
• Recursive Case: Hàm đệ qui cần gọi chính nó với dữ liệu đầu vào nhỏ hơn để tiến hành giải quyết các bài toán con.
• Forward Progress: Mỗi lần đệ quy là phải tiến triển về trường hợp cơ bản, nếu không thuật toán sẽ lặp vô hạn
• Design for Convergence: Hàm đệ qui cần được thiết kế để hội tụ đến trường hợp cơ bản sau một số bước xác định
• Recursive Leap of Faith: Nguyên lý cho thấy hàm đệ quy khi gọi chính nó với dữ liệu đầu vào nhỏ hơn sẽ hoạt động đúng.

Các loại Đệ quy cơ bản thường gặp

Đệ quy tuyến tính - Linear Recursion

Đệ quy tuyến tính là một loại đệ quy mà một hàm đệ quy sử dụng chính nó một lần duy nhất trong mỗi lời gọi. Trong quá trình phân tích cấu trúc dữ liệu và thuật toán, đệ quy tuyến tính thường được sử dụng để giải quyết các vấn đề mà lớp bài toán giảm dần một cách tuyến tính theo độ phức tạp.

Một ví dụ cụ thể về đệ quy tuyến tính là dãy Fibonacci. Dãy Fibonacci định nghĩa như sau:

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

Trong trường hợp này, hàm Fibonacci là một hàm đệ quy tuyến tính vì mỗi lời gọi đệ quy chỉ gọi đến chính nó một lần.

Một số ví dụ khác về đệ quy tuyến tính bao gồm tìm kiếm một phần tử trong một mảng sắp xếp, tính toán giai thừa và tìm kiếm địa chỉ của một phần tử trong một cây nhị phân.

Đệ quy nhị phân - Binary Recursion

Đệ quy nhị phân còn được gọi là đệ quy chia đôi. Đây là một loại đệ quy mà một hàm đệ quy sẽ gọi chính nó hai lần trong mỗi lời gọi. Điều này có thể dẫn đến vấn đề được chia nhỏ theo bội số của 2.

Một ví dụ phổ biến về đệ quy nhị phân là thuật toán chia để trị, một kỹ thuật thuật toán mạnh mẽ sử dụng việc chia đôi bài toán thành các phần nhỏ hơn, giải quyết từng phần một rồi kết hợp kết quả.

Một ứng dụng điển hình của đệ quy nhị phân khác là tìm kiếm trong một mảng đã được sắp xếp. Thuật toán tìm kiếm nhị phân là một ví dụ có thể phát triển nhanh chóng của việc sử dụng đệ quy nhị phân để tìm kiếm một phần tử trong một mảng.

Tạm kết

Qua đây, FPT Shop đã giúp bạn đọc tìm hiểu Recursion là gì và những cách ứng dụng cơ bản. Đệ quy có thể được áp dụng trong nhiều tình huống khác nhau để giải quyết các vấn đề theo một cách logic và hiệu quả. Hy vọng bạn đã biết cách sử dụng loại hàm này để phát triển công việc của mình.

Xem thêm:

• Thần số học số 5 – Hé lộ những điều bí mật về cuộc đời đầy tự do nhưng cũng rất bất ổn
• Giới thiệu những kiến thức quan trọng về PHP với cơ hội phát triển nghề nghiệp lý tưởng

Tại FPT Shop cung cấp nhiều loại máy tính xách tay, điện thoại, máy tính bảng… Khi bạn lựa chọn sản phẩm tại đây sẽ nhận được nhiều lợi ích tuyệt vời nhân dịp chào mừng năm mới. Đó chính là chế độ giảm giá sâu trên nhiều mặt hàng, chính sách ưu đãi và bảo hành hấp dẫn. 

• Điện thoại Oppo