Lặp và Đệ quy¶

Trong thuật toán, việc thực thi lặp lại một tác vụ là rất phổ biến và liên quan chặt chẽ đến phân tích độ phức tạp. Do đó, trước khi giới thiệu về độ phức tạp thời gian và độ phức tạp không gian, trước tiên chúng ta hãy cùng tìm hiểu cách triển khai việc thực thi lặp lại tác vụ trong chương trình, cụ thể là hai cấu trúc điều khiển chương trình cơ bản: vòng lặp (iteration) và đệ quy (recursion).

Vòng lặp¶

Vòng lặp (Iteration) là một cấu trúc điều khiển để thực thi lặp lại một tác vụ. Trong vòng lặp, chương trình sẽ thực thi lặp đi lặp lại một đoạn mã dưới những điều kiện nhất định cho đến khi các điều kiện đó không còn được thỏa mãn nữa.

Vòng lặp For¶

Vòng lặp for là một trong những dạng vòng lặp phổ biến nhất, thích hợp sử dụng khi số lần lặp đã được biết trước.

Hàm dưới đây triển khai phép tính tổng \(1 + 2 + \dots + n\) bằng cách sử dụng vòng lặp for, với kết quả được lưu trữ trong biến res. Lưu ý rằng trong Python, range(a, b) tương ứng với một khoảng "đóng trái, mở phải" (nửa khoảng), với phạm vi duyệt là \(a, a + 1, \dots, b-1\):

[file]{iteration}-[class]{}-[func]{for_loop}

Hình bên dưới thể hiện lưu đồ (flowchart) của hàm tính tổng này.

Số lượng thao tác trong hàm tính tổng này tỉ lệ thuận với kích thước dữ liệu đầu vào \(n\), hay nói cách khác là có "quan hệ tuyến tính". Trên thực tế, độ phức tạp thời gian mô tả chính xác "quan hệ tuyến tính" này. Các nội dung liên quan sẽ được giới thiệu chi tiết ở phần tiếp theo.

Vòng lặp While¶

Tương tự như vòng lặp for, vòng lặp while cũng là một phương pháp để triển khai vòng lặp. Trong vòng lặp while, chương trình trước tiên sẽ kiểm tra điều kiện ở mỗi vòng; nếu điều kiện đúng (true), chương trình sẽ tiếp tục thực thi, ngược lại sẽ kết thúc vòng lặp.

Dưới đây chúng ta sử dụng vòng lặp while để thực hiện phép tính tổng \(1 + 2 + \dots + n\):

[file]{iteration}-[class]{}-[func]{while_loop}

Vòng lặp while có tính linh hoạt cao hơn vòng lặp for. Trong vòng lặp while, chúng ta có thể tự do thiết kế các bước khởi tạo và cập nhật của biến điều kiện.

Ví dụ, trong đoạn mã dưới đây, biến điều kiện \(i\) được cập nhật hai lần mỗi vòng, điều này không thuận tiện để triển khai bằng vòng lặp for:

[file]{iteration}-[class]{}-[func]{while_loop_ii}

Tổng quan lại, vòng lặp for có mã nguồn gọn gàng hơn, trong khi vòng lặp while linh hoạt hơn; cả hai đều có thể triển khai cấu trúc lặp. Việc lựa chọn sử dụng loại nào nên được quyết định dựa trên yêu cầu của bài toán cụ thể.

Vòng lặp lồng nhau¶

Chúng ta có thể lồng cấu trúc vòng lặp này bên trong một cấu trúc vòng lặp khác. Dưới đây là một ví dụ sử dụng vòng lặp for:

[file]{iteration}-[class]{}-[func]{nested_for_loop}

Hình bên dưới thể hiện lưu đồ của vòng lặp lồng nhau này.

Trong trường hợp này, số lượng thao tác của hàm tỉ lệ thuận với \(n^2\), hay thời gian chạy của thuật toán có "quan hệ bậc hai" với kích thước dữ liệu đầu vào \(n\).

Chúng ta có thể tiếp tục thêm các vòng lặp lồng nhau, trong đó mỗi cấp độ lồng nhau thêm vào có thể được xem như một sự tăng chiều dữ liệu (nâng số chiều), làm tăng độ phức tạp thời gian lên "quan hệ bậc ba", "quan hệ bậc bốn", v.v.

Đệ quy¶

Đệ quy (Recursion) là một chiến lược thuật toán giải quyết vấn đề bằng cách cho hàm gọi chính nó. Nó chủ yếu bao gồm hai giai đoạn:

Đệ (Đi xuống/Gọi đệ quy): Chương trình liên tục gọi lại chính nó sâu hơn, thường truyền vào các tham số nhỏ hơn hoặc đơn giản hơn, cho đến khi đạt đến "điều kiện dừng".
Quy (Đi lên/Trả về kết quả): Sau khi kích hoạt "điều kiện dừng", chương trình sẽ quay trở về từng tầng từ hàm đệ quy sâu nhất, tổng hợp kết quả của mỗi tầng.

Từ góc độ triển khai, mã nguồn đệ quy chủ yếu gồm ba yếu tố:

Điều kiện dừng (Termination condition): Được sử dụng để quyết định thời điểm chuyển từ giai đoạn "đệ" sang "quy" (từ đi xuống sang đi lên).
Gọi đệ quy (Recursive call): Tương ứng với giai đoạn "đệ" (đi xuống), trong đó hàm tự gọi chính nó, thường là với các tham số nhỏ hơn hoặc đơn giản hơn.
Trả về kết quả (Return result): Tương ứng với giai đoạn "quy" (đi lên), trả về kết quả của cấp độ đệ quy hiện tại cho tầng trước đó.

Quan sát đoạn mã dưới đây. Chúng ta chỉ cần gọi hàm recur(n) để hoàn thành việc tính toán \(1 + 2 + \dots + n\):

[file]{recursion}-[class]{}-[func]{recur}

Hình bên dưới thể hiện quá trình đệ quy của hàm này.

Mặc dù từ góc độ tính toán, vòng lặp và đệ quy có thể đạt được cùng một kết quả, nhưng chúng đại diện cho hai trường phái (paradigm) hoàn toàn khác nhau để tư duy và giải quyết vấn đề.

Vòng lặp (Iteration): Giải quyết vấn đề "từ dưới lên" (bottom-up). Bắt đầu từ những bước cơ bản nhất, các bước này sau đó được thực thi lặp lại hoặc tích lũy cho đến khi hoàn thành tác vụ.
Đệ quy (Recursion): Giải quyết vấn đề "từ trên xuống" (top-down). Vấn đề ban đầu được phân rã thành các bài toán con nhỏ hơn có cùng cấu trúc với vấn đề ban đầu. Các bài toán con này tiếp tục được phân rã thành những bài toán con nhỏ hơn nữa cho đến khi đạt tới trường hợp cơ sở (base case - nơi mà lời giải đã được biết trước).

Lấy hàm tính tổng ở trên làm ví dụ, giả sử bài toán là \(f(n) = 1 + 2 + \dots + n\).

Vòng lặp: Mô phỏng quá trình tính tổng trong một vòng lặp, duyệt từ \(1\) đến \(n\), thực hiện thao tác cộng dồn trong mỗi vòng để thu được \(f(n)\).
Đệ quy: Phân rã bài toán thành bài toán con \(f(n) = n + f(n-1)\), liên tục phân rã (đệ quy) cho đến khi dừng lại ở trường hợp cơ sở \(f(1) = 1\).

Ngăn xếp cuộc gọi (Call Stack)¶

Mỗi lần một hàm đệ quy tự gọi chính nó, hệ thống sẽ cấp phát bộ nhớ cho hàm mới được gọi để lưu trữ các biến cục bộ, địa chỉ cuộc gọi và các thông tin khác. Điều này dẫn đến hai hệ quả:

Dữ liệu ngữ cảnh của hàm được lưu trữ trong một vùng bộ nhớ gọi là "không gian khung ngăn xếp" (stack frame space), vùng bộ nhớ này sẽ không được giải phóng cho đến khi hàm trả về kết quả. Do đó, đệ quy thường tiêu tốn nhiều không gian bộ nhớ hơn vòng lặp.
Việc gọi hàm đệ quy phát sinh thêm chi phí (overhead) phụ trợ. Do đó, đệ quy thường có hiệu suất thời gian kém hơn so với vòng lặp.

Như được hiển thị trong hình bên dưới, trước khi điều kiện dừng được kích hoạt, có \(n\) hàm đệ quy chưa trả về kết quả tồn tại đồng thời, với độ sâu đệ quy là \(n\).

Trong thực tế, độ sâu đệ quy được phép bởi các ngôn ngữ lập trình thường bị giới hạn và đệ quy quá sâu có thể dẫn đến lỗi tràn ngăn xếp (stack overflow).

Đệ quy đuôi (Tail Recursion)¶

Một điều thú vị là nếu một hàm thực hiện lệnh gọi đệ quy như là bước cuối cùng trước khi trả về, trình biên dịch hoặc trình thông dịch có thể tối ưu hóa nó để hiệu suất không gian của nó có thể so sánh được với vòng lặp. Trường hợp này được gọi là đệ quy đuôi (tail recursion).

Đệ quy thông thường: Khi một hàm trả về cấp độ trước đó, nó cần tiếp tục thực thi mã lệnh, vì vậy hệ thống cần lưu lại ngữ cảnh gọi của tầng trước đó.
Đệ quy đuôi: Lệnh gọi đệ quy là thao tác cuối cùng trước khi hàm trả về kết quả, nghĩa là sau khi quay lại cấp độ trước đó, chương trình không cần tiếp tục thực hiện các thao tác khác, do đó hệ thống không cần lưu trữ ngữ cảnh của hàm ở tầng trước.

Lấy phép tính tổng \(1 + 2 + \dots + n\) làm ví dụ, chúng ta có thể đặt biến kết quả res làm một tham số của hàm để triển khai đệ quy đuôi:

[file]{recursion}-[class]{}-[func]{tail_recur}

Quá trình thực thi của đệ quy đuôi được thể hiện ở hình bên dưới. So sánh đệ quy thông thường và đệ quy đuôi, thao tác tính tổng được thực hiện tại các thời điểm khác nhau.

Đệ quy thông thường: Thao tác tính tổng được thực hiện trong quá trình "quy" (đi lên), yêu cầu thêm một phép tính tổng sau khi mỗi tầng trả về.
Đệ quy đuôi: Thao tác tính tổng được thực hiện trong quá trình "đệ" (đi xuống); quá trình "quy" (đi lên) chỉ cần trả về kết quả qua từng tầng.

Tip

Lưu ý rằng nhiều trình biên dịch hoặc trình thông dịch không hỗ trợ tối ưu hóa đệ quy đuôi. Ví dụ, Python không hỗ trợ tối ưu hóa đệ quy đuôi theo mặc định, vì vậy ngay cả khi một hàm ở dạng đệ quy đuôi, nó vẫn có thể gặp phải sự cố tràn ngăn xếp.

Cây đệ quy¶

Khi xử lý các bài toán thuật toán liên quan đến "chia để trị" (divide and conquer), đệ quy thường cung cấp một cách tiếp cận trực quan hơn và mã nguồn dễ đọc hơn so với vòng lặp. Lấy ví dụ về "dãy Fibonacci".

Question

Cho dãy Fibonacci \(0, 1, 1, 2, 3, 5, 8, 13, \dots\), hãy tìm số thứ \(n\) trong dãy.

Giả sử số thứ \(n\) của dãy Fibonacci là \(f(n)\). Có thể dễ dàng rút ra hai kết luận sau:

Hai số đầu tiên của dãy là \(f(1) = 0\) và \(f(2) = 1\).
Mỗi số tiếp theo trong dãy là tổng của hai số trước nó, tức là \(f(n) = f(n - 1) + f(n - 2)\).

Theo hệ thức truy hồi để thực hiện các cuộc gọi đệ quy, lấy hai số đầu tiên làm điều kiện dừng, chúng ta có thể viết mã nguồn đệ quy. Việc gọi fib(n) sẽ cho chúng ta số thứ \(n\) của dãy Fibonacci:

[file]{recursion}-[class]{}-[func]{fib}

Quan sát đoạn mã trên, chúng ta thực hiện hai cuộc gọi đệ quy bên trong hàm, nghĩa là một cuộc gọi sẽ tạo ra hai nhánh gọi. Như được hiển thị trong hình bên dưới, việc lặp lại cuộc gọi đệ quy này cuối cùng sẽ tạo ra một cây đệ quy (recursion tree) có \(n\) tầng.

Về cơ bản, đệ quy thể hiện trường phái tư duy "phân rã một vấn đề thành các bài toán con nhỏ hơn", và chiến lược chia để trị này vô cùng quan trọng.

Từ góc độ thuật toán, nhiều chiến lược thuật toán quan trọng như tìm kiếm, sắp xếp, quay lui (backtracking), chia để trị và quy hoạch động trực tiếp hoặc gián tiếp áp dụng cách tư duy này.
Từ góc độ cấu trúc dữ liệu, đệ quy tự nhiên phù hợp để xử lý các vấn đề liên quan đến danh sách liên kết, cây và đồ thị, bởi vì chúng rất thích hợp để phân tích bằng tư duy chia để trị.

So sánh cả hai¶

Tổng kết nội dung trên, như được hiển thị trong bảng dưới đây, vòng lặp và đệ quy có sự khác biệt về cách triển khai, hiệu suất và khả năng áp dụng.

Bảng So sánh đặc điểm của vòng lặp và đệ quy

	Vòng lặp (Iteration)	Đệ quy (Recursion)
Cách triển khai	Cấu trúc vòng lặp	Hàm tự gọi chính nó
Hiệu suất thời gian	Thường hiệu quả hơn, không tốn chi phí gọi hàm	Mỗi cuộc gọi hàm đều phát sinh thêm chi phí
Sử dụng bộ nhớ	Thường sử dụng một lượng không gian bộ nhớ cố định	Các cuộc gọi hàm tích lũy có thể sử dụng lượng lớn không gian khung ngăn xếp
Bài toán phù hợp	Thích hợp cho các tác vụ lặp đơn giản, với mã nguồn trực quan và dễ đọc	Thích hợp cho việc phân rã bài toán con, như cây, đồ thị, chia để trị, quay lui, v.v., với cấu trúc mã nguồn gọn gàng và rõ ràng

Tip

Nếu bạn thấy nội dung sau đây khó hiểu, bạn có thể xem lại sau khi đọc chương "Ngăn xếp" (Stack).

Mối quan hệ nội tại giữa vòng lặp và đệ quy là gì? Lấy hàm đệ quy ở trên làm ví dụ, thao tác tính tổng được thực hiện trong giai đoạn "quy" (đi lên) của đệ quy. Điều này có nghĩa là hàm được gọi đầu tiên thực tế lại hoàn thành thao tác tính tổng cuối cùng, và cơ chế hoạt động này tương tự như nguyên lý "vào sau, ra trước" (last-in, first-out) của ngăn xếp.

Trên thực tế, các thuật ngữ đệ quy như "ngăn xếp cuộc gọi" (call stack) và "không gian khung ngăn xếp" (stack frame space) đã gợi ý về mối quan hệ chặt chẽ giữa đệ quy và ngăn xếp.

Đệ (Đi xuống): Khi một hàm được gọi, hệ thống sẽ cấp phát một khung ngăn xếp (stack frame) mới trên "ngăn xếp cuộc gọi" cho hàm đó để lưu trữ các biến cục bộ, tham số, địa chỉ trả về và dữ liệu khác của hàm.
Quy (Đi lên): Khi hàm hoàn thành việc thực thi và trả về, khung ngăn xếp tương ứng sẽ bị xóa khỏi "ngăn xếp cuộc gọi", khôi phục môi trường thực thi của hàm trước đó.

Do đó, chúng ta có thể sử dụng một ngăn xếp rõ ràng (explicit stack) để mô phỏng hành vi của ngăn xếp cuộc gọi, từ đó chuyển đổi đệ quy thành dạng vòng lặp (iteration):

[file]{recursion}-[class]{}-[func]{for_loop_recur}

Quan sát đoạn mã trên, khi đệ quy được chuyển đổi thành vòng lặp, mã nguồn trở nên phức tạp hơn. Mặc dù vòng lặp và đệ quy có thể chuyển đổi qua lại trong nhiều trường hợp, nhưng không phải lúc nào cũng đáng để thực hiện vì hai lý do sau:

Mã nguồn sau khi chuyển đổi có thể khó hiểu và khó đọc hơn.
Đối với một số bài toán phức tạp, việc mô phỏng hành vi của ngăn xếp cuộc gọi hệ thống có thể rất khó khăn.

Tóm lại, việc lựa chọn giữa vòng lặp và đệ quy phụ thuộc vào tính chất của từng bài toán cụ thể. Trong thực hành lập trình, việc cân nhắc ưu nhược điểm của cả hai và chọn phương pháp thích hợp dựa trên ngữ cảnh là vô cùng quan trọng.