De qui la gi

Đệ quy là một thuật ngữ không còn xa lạ trong ngôn ngữ lập trình. Vậy đệ quy là gì? Viết thuật toán đệ quy trong C/C++ như thế nào? Bài viết dưới đây sẽ giúp bạn hiểu rõ hơn về Đệ quy và những ứng dụng của nó trong C/C++ nhé!

• Đệ quy là gì?
  • Đệ quy trong C++
    • Khái niệm hàm đệ quy trong lập trình
• Ưu điểm và nhược điểm hàm đệ quy
  • Phân loại đệ quy
• Thuật toán đệ quy C++
  • Thành phần của thuật toán đệ quy
  • Giải thuật đệ quy C++
• Ví dụ minh họa
  •  Ví dụ 1
  • Ví dụ 2

Đệ quy là gì?

Theo Wikipedia, Đệ quy (Recursion) được hiểu là khi sự vật được định nghĩa theo chính nó hoặc thuộc loại của nó. Đệ quy là sự tự lặp đi lặp lại nhiều lần của chính sự vật, sự việc nào đó.

Ảnh trong ảnh

Ví dụ như việc bạn đặt 2 chiếc gương giống y như nhau và đối diện nhau (gương A và gương B). Khi nhìn vào mặt gương A ta sẽ thấy bóng phản chiếu của tấm gương B có nhỏ hơn kích thước thật.

Nhưng trên mặt của tấm gương B lại đang phản chiếu lại ảnh của tấm gương A nên khi mặt tấm gương B bị phản chiếu trong A ta có thể nhìn thấy bóng của A trong bóng của B (bóng của A lại bị thu nhỏ hơn bóng của B).

Quá trình này cứ lặp đi lặp lại dài vô hạn hoặc cho đến khi mắt người không nhìn thấy được. Người ta gọi là ảnh trong ảnh.

Ví dụ đệ quy

Đệ quy trong C++

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

Đệ quy là phương pháp dùng hàm để gọi lại chính nó. Trong quá trình giải thuật, một hàm ta lại có thể gọi lại chính tên hàm đó để tiếp tục giải dựa trên dữ liệu đã khai báo trước đó thì được gọi là đệ quy.

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

• Ưu điểm: Làm một hàm phức tạp trở nên đơn giản hơn bằng cách giải từng phần nhỏ.
• Hạn chế: Thời gian làm bài sẽ không được tối ưu do phải giải nhiều bài hơn. Thậm chí còn tốn bộ nhớ nếu phải chia nhỏ quá nhiều lần.

Phân loại đệ quy

Đệ quy trực tiếp là phương pháp đệ quy dùng một hàm để tự gọi lại chính nó.

Đệ quy gián tiếp là phương pháp đệ quy dùng một hàm X lời gọi đến hàm Y mà hàm Y lại chứa lời gọi đến chính hàm X.

Đệ quy trong C++

Thuật toán đệ quy C++

Thành phần của thuật toán đệ quy

• Điều kiện cơ sở: Điều kiện thoát khỏi đệ quy.
• Phần đệ quy (Cú pháp): Thân hàm có chứa cú pháp lời gọi đệ quy.

Giải thuật đệ quy C++

Giải thuật:

Kieu_tra_ve_ten_ham(danh_sach_ham_so)

{

if (dieu_kien_dung_thoa)

return gia_tri;

else

return ten_ham(danh_sach_doi_so) phep_toan ten_doi_so;

}

Lưu ý:

• Thông thường, những hàm có kiểu dữ liệu trả về khác kiểu void mới sử dụng Đệ quy (trừ các trường hợp đặc biệt).
• Trong bài toán này phải có dieu_kien_dung_thoa để Đệ quy kết thúc.
• phep_toan ở đây là bài toán bất kỳ phù hợp đề bài của bạn.

Ví dụ

Ví dụ minh họa

 Ví dụ 1

Đề: Tính tổng các số chia hết cho 5 nằm trong đoạn [0,N] với N là một số bất kỳ.

Input và Output ví dụ 1

Phân tích đề: Do các số nằm trong đoạn [0, N] nên ta có thể bắt đầu từ 0 và tăng dần đến N và ngược lại. Do các số chia hết cho 5 nên ta có thể bắt đầu chọn 0 và bắt đầu tăng số đó lên 5 đơn vị miễn sao số được cộng phải bé hơn hoặc bằng N. Hoặc ta có thể bắt đầu từ số chia hết cho 5 gần N nhất sau đó giảm dần đi 5 đơn vị cho đến khi về 0. Đây là đệ quy trực tiếp.

Bài giải: Ví dụ 1 đệ quy

Bài giải ví dụ đệ quy 1

Ví dụ 2

Đề: In ra n phần tử đầu tiên của dãy Fibonancci (1 1 2 3 5 8 13 21 34 …)

Input và Output ví dụ 2 đệ quy

Phân tích đề:

• Hai phần tử đầu của dãy Fibonacci là (1 1) là hai phần tử khởi tạo.
• Từ số 2 trở về sau sẽ tuân theo công thức: Phần tử phía sau sẽ bằng hai phần tử trước nó liền kề nhau cộng lại (ví dụ: 2 = 1 + 1).
• Từ đó suy ra công thức: n = (n – 1) + (n – 2) tuân theo phương pháp đệ quy gián tiếp.

Bài giải: Ví dụ 2 đệ quy

Bài giải ví dụ đệ quy 2

Hy vọng bài viết trên sẽ giúp bạn làm chủ được hàm Đệ quy để ứng dụng nó trong C++ một cách hợp lý nhất nhé.

Nguồn tham khảo: Wikipedia, HowKTeam