So sánh đệ quy với lặp năm 2024
Nơi căn tủ nhỏ ở phòng khách nhà tôi, có bày một con búp bê Matryoshka nhỏ nhắn với những nét vẽ mềm mại, đáng yêu. Khi còn nhỏ tôi thường đem ra khoe với chúng bạn và đố xem sâu trong thân búp bê mẹ, sẽ là bao nhiêu búp bê con khác. Con búp bê Matryoshka vẫn còn đó, nom trông cũ đi nhiều, nhưng sự thích thú của tôi lại không hề giảm. Giờ, thay vì đem ra nghịch chơi, tôi lại lấy nó làm ví dụ cho một khái niệm rất căn bản trong bất kỳ ngôn ngữ lập trình nào – khái niệm “đệ quy”. Show Trong bài dịch này ta hãy cùng tìm hiểu về các đặc điểm của đệ quy và học cách sử dụng đệ quy để giải quyết vấn đề với ngôn ngữ lập trình Java. 1. Hiểu đơn giản đệ quy là gì?Trước tiên ta cần hiểu phương thức trước, trong lập trình, phương thức là tập hợp các lệnh với tham số truyền vào để máy tính thao tác lệnh theo ý muốn của người viết, đệ quy xảy ra khi người viết các phương thức tự gọi (hoạc định nghĩa lại) chính nó. Xem ví dụ đơn giản sau nhé. Đề bài: Tính lũy tiến từ 0 đến n.
Giải thích:
Như vậy, hai yếu tố cần để tiến hành một phương thức đệ quy là:
Tưởng tượng, mỗi lần bạn sử dụng đệ quy, chương trình chạy một vòng và bộ nhớ Stack sẽ được chồng thêm một lớp dữ liệu, tình trạng lãng phí bộ nhớ rất dễ xảy ra nếu bạn không phân tích kỹ các vòng chạy đệ quy để có tính toán hợp lý. Vấn đề trên có thể giải quyết bằng cách “tối ưu hóa đòn bẩy đệ quy đuôi”. Viết code bất cẩn, sẽ có n số khung đệ quy ghi đè lên bộ nhớ Stack2. Đệ quy đuôi và đệ quy đầuVậy câu hỏi đặt ra là đệ quy đuôi khác với đệ quy đầu ở đâu. Chúng ta gọi là đệ quy đuôi khi phương thức đệ quy được đặt ở cuối, sau khi chương trình chạy qua điều kiện dừng. Còn lại thì ta gọi đó là đệ quy đầu. Ví dụ, phương thức ở phần 2 là đệ quy đầu, giờ hãy cùng tiếp tục biến đổi một chút và ta có phương thức đệ quy đuôi tính lũy tiến từ currentSum đến n:
Như vậy với phương thức đệ quy đuôi, phương thức đệ quy sẽ được chương trình ưu tiên xử lý dứt điểm. Chương trình sẽ không phải chạy nhiều vòng xử lý điều kiện như phương thức đệ quy đầu, nên theo logic, nguy cơ tràn bộ nhớ Stack sẽ được giảm thiểu. 3. So sánh giữa đệ quy và vòng lặpƯu điểm lớn nhất của phép đệ quy là tiếp cận xử lý vấn đề bằng những đoạn code sạch, gọn gàng, dễ đọc, dễ hiểu. Nhược điểm rõ ràng là nguy cơ cao tràn bộ nhớ Stack như đã giải thích ở trên. Cùng giải quyết một bài toán nhưng một phương án khác để thay thế đệ quy là sử dụng vòng lặp. Đề bài giống với bài toán tính lũy tiến n ở trên, ta có cách giải quyết với vòng lặp như sau:
Dù vòng lặp có một ưu điểm là chỉ có một vòng duy nhất được gọi ra và ta sẽ không phải lo nghĩ gì về vấn đề tràn bộ nhớ Stack. Nhưng vòng lặp cũng có một nhược điểm so với đệ quy là code xử lý sẽ viết dài và phức tạp hơn. 4. Các ví dụ mở rộng của đệ quySức mạnh thật sự của đệ quy là thay vì bạn phải thiết kế các thuật toán dài dòng với vòng lặp, đệ quy cho phép ta áp dụng các tư duy toán học trực tiếp vào thuật toán một cách dễ dàng. Đề bài: Nhập giá trị n và tìm đơn vị của 10n Lũy thừa100101102103…10n-110nĐơn vị1101001000……… Để giải quyết bài toán, ta tiến hành các bước sau:
5. Dãy Fibonacci và đệ quyDãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1, dãy được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó, ta có dãy Fibonacci sau: 0 1 1 2 3 5 8 13 21 34 55 … Dãy số Fibonacci0112358……Số thứ tự1234567…n Tìm số Fibonacci tương ứng với số thứ tự n, để sử dụng đệ quy tìm được số Fibonacci tương ứng, ta sẽ cần xác định quy luật và điều kiện dừng trước của dãy số Fibonacci.
6. Biểu diễn số thập phân dưới dạng nhị phân với đệ quyThử đặt ra đề bài với tình huống khi ta muốn chuyển một số từ dạng thập phân n sang dạng nhị phân, tương tự như các bước trên ta thực hiện:
7. Kết luậnĐệ quy là một khái niệm căn bản trong lập trình và đầy hiệu quả trong tư duy giải quyết vấn đề. Rất nhiều bài toán sau khi được phân tích có thể được giải quyết bằng đệ quy và đồng thời nhiều bài toán khác nếu tiếp cận với đệ quy sẽ tiết kiệm được rất nhiều đoạn code dài dòng. Thường xuyên rèn luyện giải quyết vấn đề với đệ quy sẽ trợ giúp là rất hữu ích cho tư duy thuật toán của những lập trình viên mới vào nghề, khi mà họ nên học phương pháp tiếp cận và xử lý vấn đề một cách logic và gọn gàng nhất có thể. |