Mục lục bài họcĐang ở d07-b1
Recursion and binary trees
What makes a recursive routine work
Every recursive routine needs two things: a base case that stops the recursion, and a general case that calls itself with a value moving towards the base case. Missing either one gives infinite recursion, which fills the stack and crashes — that is why the stack matters here.
How the stack makes it possible
Each call pushes the return address and local variables onto the call stack. The calls unwind in reverse order, so the deepest call returns first. This is also the cost: recursion uses more memory than an equivalent loop, and deep recursion can cause stack overflow.
Recursion versus iteration
Recursion produces shorter, clearer code for problems that are naturally self-similar — tree traversal, directory structures, divide-and-conquer sorts. Iteration is faster and uses constant memory. For factorial or a simple sum, a loop is the better answer, and saying so shows judgement rather than enthusiasm.
Binary trees
A node holds data plus a left pointer and a right pointer. In a binary search tree, everything in the left subtree is smaller than the node and everything in the right subtree is larger. Searching therefore discards half the tree at each step, giving $O(\log_2 n)$ on a balanced tree — but $O(n)$ if items are inserted already sorted, because the tree degenerates into a list.
The three traversals
Pre-order: root, left, right — used to copy a tree. In-order: left, root, right — on a binary search tree this outputs the data in sorted order, which is the fact examiners test. Post-order: left, right, root — used to delete a tree safely and to evaluate expression trees.
Điều gì làm một thủ tục đệ quy chạy được
Mọi thủ tục đệ quy cần hai thứ: một trường hợp cơ sở để dừng đệ quy, và một trường hợp tổng quát gọi lại chính nó với giá trị tiến về phía trường hợp cơ sở. Thiếu một trong hai là đệ quy vô hạn, làm đầy ngăn xếp và treo chương trình — đó là lý do ngăn xếp quan trọng ở đây.
Ngăn xếp làm cho đệ quy khả thi thế nào
Mỗi lời gọi đẩy địa chỉ quay về và các biến cục bộ vào ngăn xếp lời gọi. Các lời gọi được tháo ngược trở lại, nên lời gọi sâu nhất trả về đầu tiên. Đây cũng là cái giá: đệ quy tốn bộ nhớ hơn một vòng lặp tương đương, và đệ quy quá sâu gây tràn ngăn xếp.
Đệ quy so với vòng lặp
Đệ quy cho mã ngắn và sáng hơn với những bài toán tự thân giống nhau — duyệt cây, cấu trúc thư mục, các thuật toán chia để trị. Vòng lặp nhanh hơn và dùng bộ nhớ cố định. Với giai thừa hay một phép cộng dồn đơn giản, vòng lặp mới là đáp án tốt hơn, và nói ra được điều đó thể hiện khả năng phán đoán chứ không phải sự hào hứng.
Cây nhị phân
Một nút chứa dữ liệu cùng một con trỏ trái và một con trỏ phải. Trong cây nhị phân tìm kiếm, mọi giá trị ở cây con trái nhỏ hơn nút gốc và mọi giá trị ở cây con phải lớn hơn. Vì vậy mỗi bước tìm kiếm loại bỏ được một nửa cây, cho $O(\log_2 n)$ trên cây cân bằng — nhưng thành $O(n)$ nếu dữ liệu được chèn vào theo thứ tự đã sắp, vì cây suy biến thành một danh sách.
Ba cách duyệt
Duyệt trước: gốc, trái, phải — dùng để sao chép cây. Duyệt giữa: trái, gốc, phải — trên cây nhị phân tìm kiếm, cách này in ra dữ liệu theo đúng thứ tự đã sắp, và đó là điều giám khảo hay kiểm tra. Duyệt sau: trái, phải, gốc — dùng để xoá cây an toàn và để tính giá trị cây biểu thức.
(a) Truy vết hàm sau với $n=4$:
FUNCTION F(n)
IF n <= 1 THEN RETURN 1
ELSE RETURN n * F(n - 1)
ENDIF
ENDFUNCTION
(b) Cho cây nhị phân tìm kiếm được tạo bằng cách chèn lần lượt: $40, 25, 60, 15, 30, 55, 75$. Cho biết kết quả duyệt trước, duyệt giữa và duyệt sau.
(a) Truy vết — chú ý các lời gọi ĐI XUỐNG trước, rồi mới trả về ĐI LÊN.
$F(4)$: $4>1$ nên gọi $4\times F(3)$ — chưa tính được, phải chờ.
$F(3)$: gọi $3\times F(2)$
$F(2)$: gọi $2\times F(1)$
$F(1)$: $1\le1$ ⇒ trường hợp cơ sở, trả về $1$
Bây giờ tháo ngược:
$F(2)=2\times1=2$
$F(3)=3\times2=6$
$F(4)=4\times6=\mathbf{24}$
Ngăn xếp lúc sâu nhất chứa bốn lời gọi cùng lúc. Đây chính là lý do đệ quy tốn bộ nhớ hơn vòng lặp: một vòng FOR tính giai thừa chỉ dùng một biến duy nhất.
(b) Dựng cây. $40$ là gốc. $25<40$ nên sang trái; $60>40$ sang phải; $15<25$ nên trái của $25$; $30>25$ nên phải của $25$; $55<60$ nên trái của $60$; $75>60$ nên phải của $60$.
Cấu trúc: gốc $40$, con trái $25$ (với $15$ và $30$), con phải $60$ (với $55$ và $75$).
Duyệt trước (gốc – trái – phải): $40,\ 25,\ 15,\ 30,\ 60,\ 55,\ 75$
Duyệt giữa (trái – gốc – phải): $15,\ 25,\ 30,\ 40,\ 55,\ 60,\ 75$
Duyệt sau (trái – phải – gốc): $15,\ 30,\ 25,\ 55,\ 75,\ 60,\ 40$
Phép kiểm nhanh: duyệt giữa phải cho dãy tăng dần — ở đây đúng là như vậy. Nếu kết quả duyệt giữa của bạn không tăng dần thì hoặc cây dựng sai, hoặc thứ tự duyệt sai; không cần kiểm gì thêm.
F(n) thay vì F(n-1)). Kết quả là đệ quy vô hạn và tràn ngăn xếp. Biểu điểm luôn có một điểm riêng cho trường hợp cơ sở.Đọc xong rồi — làm thử ngay
Bài tập của chương Recursion, OOP and File Handling gồm 14 câu trắc nghiệm và 3 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.