← Quay lại Blog
✦

Think Like a Programmer #7 — Đệ quy: Khi hàm gọi lại chính mình

• Phong
sachthink-like-a-programmerproblem-solvingsoftware-engineeringrecursion

🧠 Think Like a Programmer #7 — Đệ quy: Khi hàm gọi lại chính mình

Ảnh: ThisIsEngineering — Pexels

Mở đầu

Qua 5 chương rồi, từ Strategies for Problem Solving (chiến lược tổng quát) đến Arrays (cấu trúc dữ liệu cơ bản), Pointers (quản lý bộ nhớ), rồi Classes (thiết kế phần mềm) — mỗi chương là một cấp độ tư duy mới.

Nhưng tới Chương 6: Solving Problems with Recursion, Spraul dừng lại và nói thẳng: "Recursion requires us to think differently than we do with other types of programming."

Không phải "học thêm một syntax mới", không phải "thêm một pattern nữa". Mà là nghĩ khác hẳn.

Nghe ghê vậy thôi, chứ Spraul có cách — ổng gọi đó là Big Recursive Idea (BRI) — và nó làm mình thấy recursion không còn là "ma thuật" nữa.

Đệ quy — Nỗi sợ của lập trình viên

Mình nhớ hồi mới học recursion, ai cũng bảo: "Học cái này là phải tập debugging từng cái stack frame, vẽ cái tree ra giấy, rồi trace từng bước." Mình cũng làm theo — nhưng càng trace càng rối, càng thấy nó như trò ảo thuật.

Spraul nói đúng: cái khó của recursion không nằm ở syntax, mà nằm ở việc não bộ con người không được thiết kế để suy nghĩ đệ quy. Chúng ta suy nghĩ tuần tự — bước A, bước B, bước C — trong khi recursion là "gọi chính mình" theo kiểu vòng tròn. Ép não phải trace từng bước một là một sai lầm.

Vậy giải pháp là gì? Là đừng trace.

Big Recursive Idea — Cách Spraul "lừa" bạn viết recursion

BRI gồm 3 bước cực kỳ đơn giản:

  1. Viết một "dispatcher" — xử lý trường hợp đơn giản nhất (base case), rồi delegate phần còn lại cho một hàm khác
  2. Hàm kia xử lý phiên bản nhỏ hơn của bài toán
  3. Đổi chỗ — thay lời gọi hàm kia bằng lời gọi đến chính dispatcher

Ví dụ kinh điển: tính tổng mảng số nguyên.

Bước 1 — Iterative version:

int iterativeArraySum(int integers[], int size) {
    int sum = 0;
    for (int i = 0; i < size; i++)
        sum += integers[i];
    return sum;
}

Bước 2 — Dispatcher (gọi hàm khác):

int arraySumDelegate(int integers[], int size) {
    if (size == 0) return 0;                           // base case
    int last = integers[size - 1];
    int sumRest = iterativeArraySum(integers, size - 1); // delegate
    return last + sumRest;
}

Bước 3 — Đổi thành self-call:

int arraySumRecursive(int integers[], int size) {
    if (size == 0) return 0;
    int last = integers[size - 1];
    int sumRest = arraySumRecursive(integers, size - 1); // tự gọi
    return last + sumRest;
}

Cái hay của BRI: bạn không cần nghĩ về stack frame, không cần vẽ tree. Bạn chỉ cần viết dispatcher như thể bạn đang gọi một hàm riêng biệt — và "giả vờ" như cái hàm đó đã xử lý xong phần còn lại. Ảo diệu ở chỗ: lúc đổi thành self-call, mọi thứ vẫn chạy y chang.

Head Recursion vs. Tail Recursion

Spraul phân biệt hai loại recursion qua một câu hỏi đơn giản: xử lý trước hay sau khi gọi đệ quy?

  • Tail recursion — xử lý xong, tính toán xong, rồi mới gọi đệ quy. Dữ liệu được truyền xuống (pass down).
  • Head recursion — gọi đệ quy trước, xử lý sau. Kết quả được trả lên (return up).

Mình thích cách Spraul dùng phép ẩn dụ "đếm vẹt" (parrot counting). Mỗi trạm đếm số vẹt của mình — tail recursion thì truyền tổng tích luỹ xuống dưới, head recursion thì trạm dưới tính xong rồi trả lên cho trạm trên cộng dồn.

Thực tế thì head recursion thường gặp hơn với các bài toán dynamic data structures (linked list, tree), vì nó cho phép thông tin "trồi lên" từ dưới đáy của cấu trúc.

Ảnh: Brett Jordan — Pexels

Sai lầm thường gặp

1. Thêm quá nhiều tham số

Một cái bẫy kinh điển: vì quen viết iterative (dùng biến đếm i, biến tổng sum...), nhiều người mang hết mấy biến đó vào tham số của hàm đệ quy:

// Sai — tham số rác
int sumRecursiveBad(int arr[], int size, int sum, int i) {
    if (i == size) return sum;
    sum += arr[i];
    return sumRecursiveBad(arr, size, sum, i + 1);
}

Spraul bảo: "Nếu hàm iterative không cần tham số đó, hàm recursive cũng không cần". Giữ signature đơn giản giống như hàm không đệ quy.

2. Biến global / static

Cái này còn tệ hơn — dùng biến global để đếm thay vì return value. Hàm mất tính "thuần khiết" (pure), side effects khắp nơi, chạy lần hai ra kết quả sai.

// Sai — biến global
int count = 0;
int countZerosGlobal(int arr[], int size) {
    if (size == 0) return count;
    if (arr[size - 1] == 0) count++;
    countZerosGlobal(arr, size - 1);
}

Đúng: dùng head recursion, accumulate kết quả từ dưới lên:

// Đúng — return value
int countZerosPure(int arr[], int size) {
    if (size == 0) return 0;
    int c = countZerosPure(arr, size - 1);
    if (arr[size - 1] == 0) c++;
    return c;
}

Đệ quy với cấu trúc dữ liệu động

Linked List

Một linked list có cấu trúc đệ quy tự nhiên: mỗi node trỏ tới phần "còn lại" của list. Spraul đưa ra ví dụ đếm số âm trong singly linked list — bài toán rất dễ nếu viết iterative, nhưng cách tiếp cận đệ quy mới thấy được vẻ đẹp của nó.

Điểm thú vị: Spraul dùng wrapper functions — một hàm public gọi hàm recursive private với tham số ban đầu. Kỹ thuật này cực kỳ phổ biến trong thực tế: expose interface đẹp, giấu implementation phức tạp.

Binary Tree — Nơi recursion toả sáng

Nếu có một cấu trúc dữ liệu sinh ra để dùng recursion, đó là binary tree. Mỗi node có left child và right child — cũng là một cái tree con. Đệ quy ở đây không còn là "lựa chọn", mà là cách duy nhất để code gọn gàng.

Ví dụ: tìm giá trị lớn nhất trong binary tree.

int maxValue(TreeNode* node) {
    if (node == nullptr) return INT_MIN;
    int leftMax = maxValue(node->left);
    int rightMax = maxValue(node->right);
    int biggest = max(leftMax, rightMax);
    return max(node->value, biggest);
}

Ba dòng — và nó xử lý toàn bộ cái tree, dù có 10 hay 10 triệu node. Viết iterative thì phải tự maintain một cái stack, dễ sai hơn nhiều.

Spraul cũng chỉ ra cách dùng wrapper functions để clean up interface, và bài toán đếm số lá (leaf nodes) — một ứng dụng kinh điển khác của recursion trên tree.

Khi nào dùng recursion?

Cuối chương, Spraul bàn về trade-offs. Ổng không phải dạng "thánh recursion" — ổng chỉ ra cả mặt lợi và hại:

  • Nên dùng: bài toán có cấu trúc đệ quy tự nhiên (tree, graph, chia để trị)
  • Không nên dùng: bài toán đơn giản có thể giải bằng loop (factorial, Fibonacci là ví dụ tồi cho recursion)
  • Chi phí: function call overhead + stack overflow risk

Một câu mình thấy tâm đắc: "Recursion is a tool, not a religion." Dùng đúng chỗ thì tuyệt, lạm dụng thì khổ.

Cảm nhận của mình

Đọc xong chương này, mình nghiệm ra một điều: sự khó của recursion nằm ở chỗ ta cố gắng trace nó. Càng trace càng rối, càng thấy nó là trò ảo thuật.

BRI thay đổi cách mình tiếp cận hoàn toàn. Thay vì "viết recursive function trong đầu", mình viết dispatcher trước — một hàm rất đơn giản, xử lý base case và delegate phần còn lại. Rồi mới đổi thành self-call. Nó giống như "fake it till you make it" trong lập trình vậy.

Cái hay thứ hai là cách Spraul phân tích head vs. tail recursion qua những câu chuyện cụ thể (parrot counting, best customer). Trước giờ mình chỉ biết "có cái gọi là tail call optimization", chứ không hiểu bản chất khác nhau giữa "truyền xuống" và "trả lên".

Một điểm trừ nho nhỏ: ví dụ trong chương chủ yếu là C++ với integer arrays và linked list tự xây — khá khô khan nếu bạn chỉ quen với JavaScript / Python mấy cái array có sẵn. Nhưng cái tư duy (BRI, head vs. tail, wrapper functions) thì apply được everywhere.

Chương này cũng là lần đầu mình thấy Spraul thừa nhận: "Recursion is hard, and that's OK." Cảm giác được tác giả "cho phép" mình thấy nó khó... giải toả thiệt.

Ảnh: Alexandra — Pexels

Kết

Chương 6 là một trong những chương hay nhất mình đọc từ đầu sách tới giờ. Không phải vì nó dạy syntax mới, mà vì nó dạy cách nghĩ khác. Recursion không phải là "ma thuật" — nó là kỹ thuật giải quyết vấn đề bằng cách chia nhỏ thành những vấn đề giống hệt nhưng nhỏ hơn. Biết cách "giả vờ" rằng mình đã có lời giải cho phần còn lại, rồi focus vào base case và bước kết nối.

Tới đây mình đã đi được 6 chương, còn 2 chương nữa là hết cuốn sách. Hẹn mấy bạn ở bài tiếp theo: Chương 7 — Solving Problems with Code Reuse, nơi Spraul nói về tái sử dụng code, thư viện chuẩn, và cách tận dụng những thứ người khác đã viết thay vì tự làm lại từ đầu. Nghe đơn giản mà cũng nhiều bài học lắm! 🚀

📋 Phụ lục thuật ngữ
- Recursion — kỹ thuật lập trình khi hàm gọi lại chính nó (trực tiếp hoặc gián tiếp)
- Base case — trường hợp cơ bản, dừng đệ quy (ví dụ: size == 0)
- Big Recursive Idea (BRI) — phương pháp của Spraul: viết dispatcher trước, rồi đổi thành self-call
- Tail recursion — gọi đệ quy sau khi xử lý; dữ liệu truyền xuống
- Head recursion — gọi đệ quy trước, xử lý sau; kết quả trả lên
- Wrapper function — hàm public gọi hàm recursive private với tham số khởi tạo
- Stack overflow — lỗi tràn stack khi đệ quy quá sâu (không có base case hoặc input quá lớn)
- Binary tree — cấu trúc dữ liệu mỗi node có tối đa 2 con (left & right)
- Leaf node — node không có con (lá cây)

Tags: #sách #thinklikeaprogrammer #problemsolving #recursion #softwareengineering

← Xem các bài viết khác
✦