Xin chào tất cả mọi người!
Như mọi người cũng đã biết thì trong giới lập trình có rất nhiều cấp bậc khác nhau như Fresher, Junior, Senior, ….và những ngôn ngữ khác nhau như Java, C#, PHP, Python… Mỗi ngôn ngữ sẽ có các đặc điểm, tính chất khác nhau. Nhưng bên cạnh đó có những phương pháp là những giải thuật mà tất cả các ngôn ngữ đều có thể áp dụng vào trong các project của mình để được xử lý tối ưu nhất.
Chúng ta cùng đến phần đầu tiên: Giải thuật “Đệ Quy” – một giải thuật được sử dụng khá nhiều
Để biết cách sử dụng giải thuật này thì trước hết cần phải hiểu nó là cái gì mà nó lại được sử dụng nhiều và có thể nhiều khi các lập trình viên ngồi lập trình mà không để ý là mình đang dùng nó.
Vậy, Đệ Quy là một hàm xử lý mà bên trong thân hàm gọi lại chính nó nhưng xử lý các bước nhỏ hơn, từ đó tổng hợp lại thành kết quả của bài toán.
Nghe có thể hơi mơ hồ, chúng ta có thể minh họa như sau:
void Recusion(){
Recusion();
}
Nhưng nếu để ý thấy hàm bên trên, nó sẽ gọi lại chính nó vô hạn lần và không thể dừng lại. Vậy nên điều kiện bắt buộc khi sử dụng giải thuật này là phải tìm ra đường dẫn đến một trường hợp có thể dừng lại.
Vậy để sử dụng giải thuật “Đệ Quy”, chúng ta cần phải chuẩn bị các bước sau:
1. Tham số hóa bài toán: Đưa bài toán thành 1 hàm có các tham số cần phải sử dụng trong các bài toán và các bước lặp lại.
2. Phân tích các trường hợp: Phân tích bài toán thành các trường hợp lớn rồi nhỏ dần để có thể tiến tới trường hợp dừng lại
3. Tìm trường hợp để dừng lại
Các bài toán có thể chia thành các bài toán con nhỏ hơn nhưng có cùng ý nghĩa với bài toán lớn thì có thể áp dụng giải thuật này. Cụ thể hơn về các bài toán thì mọi người hãy tham gia vào Club CodeGym Thuật để có thể hiểu rõ hơn nhé.
Vậy chúng ta đã biết được giải thuật này là gì và các bước để triển khai nó. Và giờ, tại mình sẽ nói về các loại hình của giải thuật này
Loại hình 1: Đệ Quy Tuyến Tính:
Loại hình này nghĩa là trong thân hàm chỉ có gọi lại chính nó 1 lần và tổng hợp dần kết quả.
Minh họa:
<result_type> Recusion(<pram>){
return Recusion(<param>);
}
Loại hình 2: Đệ Quy Nhị Phân:
Loại hình này là trong thân hàm sẽ có 2 lần gọi lại chính nó và kết quả được tổng hợp từ 2 lần gọi đó.
Minh họa:
<result_type> Recusion(<pram>){
return Recusion(<param>) + Recusion(<param>);
}
Loại hình 3: Đệ Quy Lồng:
Loại hình này là trong tham số chính là kết quả của hàm đó.
Minh họa:
<result_type> Recusion(<pram>){
return Recusion(Recusion(<param>));
}
Loại hình 4: Đệ Quy Hỗ Tương:
Loại hình này là sẽ có các hàm gọi lẫn nhau
Minh họa:
<result_type> Recusion1(<pram>){
return Recusion2(<param>);
}
<result_type> Recusion2(<pram>){
return Recusion1(<param>);
}
Loại hình 5: Đệ Quy Quay Lui – hay còn được giang hồ gọi là “Vét Cạn”
Loại hình này là phương pháp thử sai. Sẽ cho thử tất cả các trường hợp, nếu trường hợp đó sai sẽ quay lui lại để tìm trường hợp khác đúng đắn hơn.
Minh họa: Bài toán kinh điển nhất đó chính là di chuyển con mã trên bàn cờ vua – Mọi người có thể tìm kiếm trên Google nha.
Vậy là đã hết phần I, nếu thấy hay thì ủng hộ mình và Club nhé, nếu có gì thấy sai sót thì hãy góp ý để giúp mình hoàn thiện hơn.
Xin cảm ơn các bạn đã đọc và hẹn gặp lại ở các phần tiếp theo!!!
