ĐỆ QUI 1. Khái niệm đệ qui Một hàm gọi đến hàm khác là bình thường, nhưng nếu hàm lại gọi đến chính nó thì ta gọi hàm là đệ qui. Khi thực hiện một hàm đệ qui, hàm sẽ phải chạy rất nhiều lần, trong mỗi lần chạy chương trình sẽ tạo nên một tập biến cục bộ mới trên ngăn xếp (các đối, các biến riêng khai báo trong hàm) độc lập với lần chạy trước đó, từ đó dễ gây tràn ngăn xếp. Vì vậy đối với những bài toán có thể giải được bằng phương pháp lặp. | ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG nGhệ Khoa Công nghệ Thông tin PHẠM HonG thai Bài giảng NGÔN NGỮ LẬP TRÌNH C C tiế p t h e o III. ĐỆ QUI 1. Khái niệm đệ qui Một hàm gọi đến hàm khác là bình thường nhưng nếu hàm lại gọi đến chính nó thì ta gọi hàm là đệ qui. Khi thực hiện một hàm đệ qui hàm sẽ phải chạy rất nhiều lần trong mỗi lần chạy chương trình sẽ tạo nên một tập biến cục bộ mới trên ngăn xếp các đối các biến riêng khai báo trong hàm độc lập với lần chạy trước đó từ đó dễ gây tràn ngăn xếp. Vì vậy đối với những bài toán có thể giải được bằng phương pháp lặp thì không nên dùng đệ qui. Để minh hoạ ta hãy xét hàm tính n giai thừa. Để tính n ta có thể dùng phương pháp lặp như sau main int n doule kq 1 cout n cin n for int i 1 i n i kq i cout n kq Mặt khác n giai thừa cũng được tính thông qua n-1 bởi công thức truy hồi n 1 nếu n 0 n n-1 n nếu n 0 do đó ta có thể xây dựng hàm đệ qui tính n như sau double gt int n Chương 4. Hàm và chương trình if n 0 return 1 else return gt n-1 n main int n cout n cin n cout gt n Trong hàm main giả sử ta nhập 3 cho n khi đó để thực hiện câu lệnh cout gt 3 để in 3 đầu tiên chương trình sẽ gọi chạy hàm gt 3 . Do 3 0 nên hàm gt 3 sẽ trả lại giá trị gt 2 3 tức lại gọi hàm gt với tham đối thực sự ở bước này là n 2. Tương tự gt 2 gt 1 2 và gt 1 gt 0 1. Khi thực hiện gt 0 ta có đối n 0 nên hàm trả lại giá trị 1 từ đó gt 1 1 1 1 và suy ngược trở lại ta có gt 2 gt 1 2 1 2 2 gt 3 gt 2 3 2 3 6 chương trình in ra kết quả 6. Từ ví dụ trên ta thấy hàm đệ qui có đặc điểm - Chương trình viết rất gọn - Việc thực hiện gọi đi gọi lại hàm rất nhiều lần phụ thuộc vào độ lớn của đầu vào. Chẳng hạn trong ví dụ trên hàm được gọi n lần mỗi lần như vậy chương trình sẽ mất thời gian để lưu giữ các thông tin của hàm gọi trước khi chuyển điều khiển đến thực hiện hàm được gọi. Mặt khác các thông tin này được lưu trữ nhiều lần trong ngăn xếp sẽ dẫn đến tràn ngăn xếp nếu n lớn. Tuy nhiên đệ qui là cách viết rất gọn dễ viết và đọc chương trình mặt khác có .
