Tổng hợp một số bài tập về Đệ quy trong C – VietTuts

Đệ quy là gì?

Đệ quy trong C là quá trình trong đó một phương thức gọi lại chính nó một cách liên tiếp. Một phương thức trong C gọi lại chính nó được gọi là phương thức đệ quy.

Cú pháp:

Ngôn ngữ lập trình C hỗ trợ đệ quy, ví dụ, một hàm có thể gọi đến chính nó. Nhưng khi bạn sử dụng hàm đệ quy, lập trình viên cần phải cẩn thận định nghĩa điều kiện thoát khỏi hàm, phòng khi gặp phải vòng lặp vô hạn.

Hàm đệ quy rất hữu dụng để giải quyết các vấn đề trong toán học như tính toán giai thừa, tạo dãy Fibonacci, …

Bài tập Đệ quy trong C

Dưới đây là các bài tập C giúp bạn hiểu kiến thức cơ bản về Đệ quy trong C:

Tính dãy số Fibonacci sử dụng đệ quy

Ví dụ chương trình C tìm 10 số Fibonacci đầu tiên sử dụng phương pháp đệ quy:

Chạy chương trình C trên cho kết quả như sau:

Tính giai thừa sử dụng đệ quy

Ví dụ chương trình tính giai thừa trong C có sử dụng phương pháp đệ quy:

Chạy chương trình C trên cho kết quả như sau:

Tìm USCLN và BSCNN của 2 số a và b sử dụng đệ quy

Ví dụ dưới đây sử dụng giải thuật Euclid để giải quyết bài toán tìm ước số chung lớn nhất (USCLN) và bội số chung nhỏ nhất (BSCNN) của hai số nguyên dương a và b:

Chạy chương trình C trên cho kết quả như sau:

Tính tổng n số sử dụng đệ quy

Ví dụ chương trình tổng của n số trong C có sử dụng phương pháp đệ quy:

Chạy chương trình C trên cho kết quả như sau:

Bài toán Tháp Hà Nội (Tower of Hanoi) sử dụng đệ quy

Trước khi tìm hiểu lời giải cho bài toán Tháp Hà Nội (Tower of Hanoi), mình xin nhắc lại một số qui tắc của trò chơi toán Tháp Hà Nội này:

Tháp Hà Nội (Tower of Hanoi) là gì ?

Bài toán Tháp Hà Nội (Tower of Hanoi) là một trò chơi toán học bao gồm 3 cột và với số đĩa nhiều hơn 1.

Dưới đây là hình minh họa bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.

Các đĩa có kích cỡ khác nhau và xếp theo tự tự tăng dần về kích cỡ từ trên xuống: đĩa nhỏ hơn ở trên đĩa lớn hơn. Với số đĩa khác nhau thì ta có các bài toán Tháp Hà Nội (Tower of Hanoi) khác nhau, tuy nhiên lời giải cho các bài toán này là tương tự nhau. Lời giải tối ưu cho bài toán Tháp Hà Nội (Tower of Hanoi) là khi trò chơi chỉ có 3 cọc. Với số cọc lớn hơn thì lời giải bài toán vẫn chưa được khẳng định.

Qui tắc trò chơi toán học Tháp Hà Nội (Tower of Hanoi)

Nhiệm vụ của trò chơi là di chuyển các đĩa có kích cỡ khác nhau sang cột khác sao cho vẫn đảm bảo thứ tự ban đầu của các đĩa: đĩa nhỏ nằm trên đĩa lớn. Dưới đây là một số qui tắc cho trò chơi toán học Tháp Hà Nội (Tower of Hanoi):

• Mỗi lần chỉ có thể di chuyển một đĩa từ cột này sang cột khác.
• Chỉ được di chuyển đĩa nằm trên cùng (không được di chuyển các đĩa nằm giữa).
• Đĩa có kích thước lớn hơn không thể được đặt trên đĩa có kích thước nhỏ hơn.

Dưới đây là hình minh họa cách giải bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.

Bài toán Tháp Hà Nội (Tower of Hanoi) với số đĩa là n có thể được giải với số bước tối thiểu là 2n−1. Do đó, với trường hợp 3 đĩa, bài toán Tháp Hà Nội (Tower of Hanoi) có thể được giải sau 23−1 = 7 bước.

Chương trình C: sử dụng đệ quy

Dưới đây là chương trình C để giải bài toán Tháp Hà Nội (Tower of Hanoi) sử dụng đệ quy trong C trong C:

Chạy chương trình C trên cho kết quả như sau: