[Java Basics] Đệ quy trong Java: cách hoạt động và khi nào nên dùng

Một recursive method là method tự gọi chính nó với input nhỏ hơn. Không có cú pháp mới nào cần học: một recursive call là một lời gọi bình thường, nó push một frame bình thường, và nó return theo cách bình thường. Cái mới nằm ở kỷ luật giữ cho nó không chạy mãi.

Bài này nói về đúng kỷ luật đó — base case, bước thu nhỏ input, và hình dạng của stack trong lúc đệ quy chạy — rồi tới hai thứ thực sự làm người mới trả giá: StackOverflowError vì thiếu base case hoặc không bao giờ chạm tới nó, và một Fibonacci naive gọi hàng triệu lần cho một con số có thể tính bằng vài chục lời gọi. Mọi con số và mọi thông báo lỗi bên dưới là output thật từ OpenJDK 21.0.6.

Bài 19 đã xác lập rằng mỗi lời gọi push một frame giữ các local variable của riêng nó, và stack có kích thước hữu hạn. Đệ quy là chỗ sự thật đó không còn là chi tiết bên lề mà trở thành một ràng buộc thiết kế.

Đệ quy thực sự là gì

Một recursive method có đúng hai phần, và cả hai đều bắt buộc:

• một base case: input mà method trả lời trực tiếp, không gọi lại chính nó;
• một recursive case: mọi trường hợp còn lại, gọi lại method với input gần base case hơn input nó nhận được.

Bỏ base case thì lời gọi không bao giờ dừng. Giữ base case nhưng đưa cho recursive call một input không nhỏ đi thì nó không bao giờ tới nơi. Kiểu nào cũng hết stack.

Factorial là ví dụ đầu tiên chuẩn mực vì cả hai phần đều lộ rõ. 0! và 1! bằng 1 theo định nghĩa — đó là base case — còn n! là n * (n - 1)! với mọi giá trị lớn hơn:

static long factorial(int n) {
    if (n <= 1) return 1;          // base case
    return n * factorial(n - 1);   // recursive case, n giảm 1
}

Hãy đọc dòng thứ hai như một lời hứa chứ không phải một vòng lặp. Nó nói: nếu ai đó đưa tôi đáp án cho n - 1, tôi tạo ra được đáp án cho n. Base case là thứ khiến lời hứa đó thu hồi được, vì chuỗi "nếu ai đó đưa tôi..." phải kết thúc ở đâu đó.

Trace factorial theo từng lời gọi

In ra lúc đi vào và lúc đi ra làm hai giai đoạn hiện rõ. Đây là việc hữu ích nhất bạn có thể làm khi một đệ quy chạy sai:

public class Factorial {
    static int factorial(int n) {
        System.out.println("enter factorial(" + n + ")");
        if (n <= 1) {
            System.out.println("exit  factorial(" + n + ") -> 1   (base case)");
            return 1;
        }
        int result = n * factorial(n - 1);
        System.out.println("exit  factorial(" + n + ") -> " + result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println("answer = " + factorial(4));
    }
}

enter factorial(4)
enter factorial(3)
enter factorial(2)
enter factorial(1)
exit  factorial(1) -> 1   (base case)
exit  factorial(2) -> 2
exit  factorial(3) -> 6
exit  factorial(4) -> 24
answer = 24

Bốn dòng enter, rồi bốn dòng exit theo thứ tự ngược lại. Đó không phải trùng hợp — đó chính là call stack. Mỗi enter push một frame và caller dừng lại chờ; mỗi exit pop một frame ra và trao giá trị cho frame bên dưới.

Hai chi tiết trong trace đó đáng gọi tên, vì cả hai đều làm nhiều người bất ngờ:

Không có phép nhân nào xảy ra trên đường đi xuống. n * factorial(n - 1) không thể tính dấu * cho tới khi lời gọi bên phải nó return. Mọi frame từ factorial(4) tới factorial(2) đều đang đứng giữa chừng một biểu thức, giữ n của riêng mình và chờ. Phép tính đầu tiên trong cả lần chạy chỉ xảy ra sau khi factorial(1) return.

Đáp án được lắp ráp trên đường đi lên. 1, rồi 2 * 1, rồi 3 * 2, rồi 4 * 6. Bài 19 cho thấy bốn frame của bốn method khác nhau; ở đây bốn frame là bốn lời gọi của cùng một method, và điều đó không thay đổi gì về cách stack hoạt động. Mỗi lời gọi có n riêng và result riêng, trong frame riêng.

Chuyện gì xảy ra khi thiếu base case

Lỗi này rất dễ mắc và thất bại thì rất ồn ào. Method dưới đây đệ quy mãi mãi vì không có gì dừng nó lại:

public class NoBaseCase {
    static int countdown(int n) {
        System.out.println(n);
        return countdown(n - 1);
    }

    public static void main(String[] args) {
        countdown(3);
    }
}

Nó compile sạch sẽ — javac không có ý kiến gì về việc đệ quy của bạn có dừng hay không. Lúc runtime nó đếm thẳng qua số 0 và tiếp tục:

3
2
1
0
-1
-2
-3

và cuối cùng:

Exception in thread "main" java.lang.StackOverflowError
	at NoBaseCase.countdown(NoBaseCase.java:4)
	at NoBaseCase.countdown(NoBaseCase.java:4)
	at NoBaseCase.countdown(NoBaseCase.java:4)
	at NoBaseCase.countdown(NoBaseCase.java:4)
	at NoBaseCase.countdown(NoBaseCase.java:4)

Một stack trace lặp lại cùng một dòng hàng trăm lần là chữ ký của đệ quy mất kiểm soát. Hãy đọc dòng lặp đó: nó chỉ đúng method và đúng dòng chứa recursive call.

Base case không bao giờ chạm tới

Dạng thứ hai khó chịu hơn, vì base case nằm ngay đó trong code và trông có vẻ đúng:

public class NotShrinking {
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sumTo(n);
    }

    public static void main(String[] args) {
        System.out.println(sumTo(5));
    }
}

Exception in thread "main" java.lang.StackOverflowError
	at NotShrinking.sumTo(NotShrinking.java:6)
	at NotShrinking.sumTo(NotShrinking.java:6)
	at NotShrinking.sumTo(NotShrinking.java:6)
	at NotShrinking.sumTo(NotShrinking.java:6)
	at NotShrinking.sumTo(NotShrinking.java:6)

sumTo(n) gọi sumTo(n) — argument không hề bị giảm, nên n bằng 5 trong tất cả các frame đó và điều kiện n == 0 không bao giờ đúng. Quy tắc bắt được lỗi này trước khi chạy: viết ra thứ gì thay đổi giữa một lời gọi và lời gọi mà nó tạo ra, rồi tự thuyết phục mình rằng nó đang tiến về base case. Nếu không có gì thay đổi, bạn vừa viết một vòng lặp vô hạn theo cách vòng vo hơn.

Đệ quy đi sâu được tới đâu?

Sâu, nhưng không vô hạn, và con số cụ thể không phải là thuộc tính của ngôn ngữ. Cứ đếm frame rồi biết:

public class Depth {
    static int depth = 0;

    static void dig() {
        depth++;
        dig();
    }

    public static void main(String[] args) {
        try {
            dig();
        } catch (StackOverflowError e) {
            System.out.println("depth reached: " + depth);
        }
    }
}

Ba lần chạy liên tiếp trên cùng một máy, không đặt option nào:

depth reached: 44286
depth reached: 45378
depth reached: 59567

Ba đáp án khác nhau. Stack size mặc định của thread thay đổi theo platform và theo bản build của JVM, và ngay trên một máy con số vẫn nhảy giữa các lần chạy. Đừng bao giờ viết code dựa vào việc có sẵn một độ sâu đệ quy cụ thể nào đó.

Bạn có thể làm con số trở nên lặp lại được bằng cách tự đặt stack size với -Xss. Mười lần chạy liên tiếp ở mức 256 KB:

for i in $(seq 10); do java -Xss256k Depth; done

depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479

Mười lần chạy, một đáp án. Stack lớn hơn mua được độ sâu lớn hơn, gần như theo tỉ lệ — -Xss1m đạt 20300, 19808 và 19808 trên cùng máy đó.

Vì sao con số thay đổi giữa các lần chạy

-Xss512k hoàn toàn không ổn định: 7258, 4793, 6839, 6876, 8989, 5882, 6361, 6918, 6774, 4450. Lý do là JIT compiler. dig được gọi hàng chục nghìn lần, nên giữa chừng lần chạy JVM compile lại nó, và một frame do JIT sinh ra không cùng kích thước với frame của interpreter — các frame đã nằm trên stack do một phiên bản tạo ra, còn các frame sắp tới do phiên bản khác. Tắt JIT đi là thấy ngay:

for i in 1 2 3; do java -Xint -Xss512k Depth; done

depth reached: 4210
depth reached: 4210
depth reached: 4210

Ở -Xss256k thì stack hết sạch từ lâu trước khi JIT kịp quan tâm, nên trường hợp đó ổn định mà không cần -Xint. Không con số nào trong đây chuyển được sang máy khác, JDK khác hay method khác — một method có nhiều local variable hơn dùng frame lớn hơn và tràn sớm hơn.

Sáu ví dụ đệ quy kinh điển

Mỗi ví dụ đều ngắn có chủ đích. Điểm cần nhìn là hình dạng, không phải sự khéo léo:

public class Classics {
    static long factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }

    static int sumTo(int n) {
        if (n == 0) return 0;
        return n + sumTo(n - 1);
    }

    static long fib(int n) {
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }

    static String reverse(String s) {
        if (s.length() <= 1) return s;
        return reverse(s.substring(1)) + s.charAt(0);
    }

    static void countdown(int n) {
        if (n == 0) {
            System.out.println("liftoff");
            return;
        }
        System.out.print(n + " ");
        countdown(n - 1);
    }

    static int binarySearch(int[] a, int target, int lo, int hi) {
        if (lo > hi) return -1;
        int mid = (lo + hi) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) return binarySearch(a, target, mid + 1, hi);
        return binarySearch(a, target, lo, mid - 1);
    }

    public static void main(String[] args) {
        System.out.println("factorial(10) = " + factorial(10));
        System.out.println("sumTo(100)    = " + sumTo(100));
        System.out.println("fib(10)       = " + fib(10));
        System.out.println("reverse       = " + reverse("recursion"));
        countdown(5);
        int[] a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        System.out.println("index of 23   = " + binarySearch(a, 23, 0, a.length - 1));
        System.out.println("index of 7    = " + binarySearch(a, 7, 0, a.length - 1));
    }
}

factorial(10) = 3628800
sumTo(100)    = 5050
fib(10)       = 55
reverse       = noisrucer
5 4 3 2 1 liftoff
index of 23   = 5
index of 7    = -1

binarySearch là cái đáng nhìn kỹ. Nó có hai base case — tìm thấy, và khoảng rỗng — còn bước đệ quy vứt đi một nửa khoảng còn lại thay vì một phần tử. Đó là lý do nó chạm base case sau khoảng 20 lời gọi với mảng một triệu phần tử, trong khi sumTo cần một triệu. Hình dạng của bước thu nhỏ quyết định tất cả.

Vì sao Fibonacci đệ quy naive là một cái bẫy

fib ở trên là định nghĩa đệ quy trong sách giáo khoa và nó đúng. Nó cũng là ví dụ chuẩn mực về đệ quy làm sai một cách thảm hoạ, và bạn thấy chính xác vì sao khi đếm số lời gọi:

public class FibCount {
    static long calls = 0;

    static long fib(int n) {
        calls++;
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }

    static long memoCalls = 0;

    static long fibMemo(int n, long[] memo) {
        memoCalls++;
        if (n < 2) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        return memo[n];
    }

    public static void main(String[] args) {
        System.out.println("  n |        fib(n) |   naive calls | memoised calls");
        for (int n : new int[] {10, 20, 30, 40}) {
            calls = 0;
            long v = fib(n);
            memoCalls = 0;
            long m = fibMemo(n, new long[n + 1]);
            System.out.printf("%3d | %13d | %13d | %14d%n", n, v, calls, memoCalls);
            if (v != m) throw new AssertionError("mismatch at " + n);
        }
    }
}

  n |        fib(n) |   naive calls | memoised calls
 10 |            55 |           177 |             19
 20 |          6765 |         21891 |             39
 30 |        832040 |       2692537 |             59
 40 |     102334155 |     331160281 |             79

Đây là số lời gọi chứ không phải thời gian, nên máy bạn cho ra đúng con số như máy tôi. fib(30) trả về một số sáu chữ số sau 2.692.537 lời gọi method. fib(40) cần 331.160.281.

Tốc độ tăng thường được mô tả là "số lời gọi gấp đôi mỗi khi n tăng 1". Không hẳn. Đếm số lời gọi cho mọi n từ 5 tới 30 rồi chia mỗi con số cho con số trước đó, tỉ lệ hội tụ về 1.618 — tỉ lệ vàng — nên số lời gọi hơn gấp đôi sau mỗi hai bước. Năm dòng trích từ lần chạy đó:

n=10  calls=      177  ratio to n-1 = 1.624
n=15  calls=     1973  ratio to n-1 = 1.619
n=20  calls=    21891  ratio to n-1 = 1.618
n=25  calls=   242785  ratio to n-1 = 1.618
n=30  calls=  2692537  ratio to n-1 = 1.618

Nguyên nhân không phải là đệ quy. Nguyên nhân là cùng một subproblem được giải đi giải lại. fib(5) chỉ cần đáp án của sáu subproblem khác nhau, từ fib(0) tới fib(5), mà phải gọi 15 lần để có chúng:

naive fib(5): 15 calls, per node {0=3, 1=5, 2=3, 3=2, 4=1, 5=1}
memo  fib(5): 9 calls

fib(3) được tính hai lần, fib(2) ba lần, fib(1) năm lần. Mỗi lần tính lại như vậy kéo theo cả subtree của nó, và đó là chỗ con số 1.618 sinh ra.

Memoisation: nhớ lại thứ đã tính

Cách sửa gọn trong bốn dòng và một array. Trước khi đệ quy thì kiểm tra xem đáp án đã biết chưa; sau khi tính xong thì ghi lại:

static long fib(int n, long[] memo) {
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

fib(10) = 55                   in 19 calls (2n-1 = 19)
fib(20) = 6765                 in 39 calls (2n-1 = 39)
fib(30) = 832040               in 59 calls (2n-1 = 59)
fib(40) = 102334155            in 79 calls (2n-1 = 79)
fib(90) = 2880067194370816120  in 179 calls (2n-1 = 179)

Đúng 2n - 1 lời gọi, lần nào cũng vậy: mỗi subproblem trong n subproblem được giải một lần và tra cứu một lần. Đặt cạnh nhau:

Điều kiện memo[n] != 0 dùng được ở đây chỉ vì không số Fibonacci nào ngoài fib(0) bằng 0, và fib(0) đã do base case phía trên xử lý. Với bài toán mà 0 là đáp án hợp lệ, hãy dùng thêm một boolean[] đánh dấu "đã tính", hoặc Long[] rồi kiểm tra null.

⚠️ Code đệ quy chậm gần như không bao giờ chậm vì các lời gọi. Nó chậm vì đang giải lại cùng một subproblem. Hãy đếm số lời gọi trước khi viết lại bất cứ thứ gì.

Đệ quy và vòng lặp

Thứ gì viết được bằng đệ quy đều viết được bằng vòng lặp, và ngược lại. Đây là cùng một phép tính tổng theo hai cách, mỗi cách gắn một bộ đếm:

public class RecVsIter {
    static long calls = 0;
    static long steps = 0;

    static long sumRec(int n) {
        calls++;
        if (n == 0) return 0;
        return n + sumRec(n - 1);
    }

    static long sumIter(int n) {
        long total = 0;
        for (int i = 1; i <= n; i++) {
            steps++;
            total += i;
        }
        return total;
    }

    public static void main(String[] args) {
        for (int n : new int[] {5, 100, 10000}) {
            calls = 0;
            steps = 0;
            long r = sumRec(n);
            long it = sumIter(n);
            System.out.printf("n = %-5d  recursive: %5d calls, %5d frames deep -> %d%n", n, calls, calls, r);
            System.out.printf("           iterative: %5d loop steps, 1 frame     -> %d%n", steps, it);
        }
        System.out.println();
        try {
            System.out.println("sumRec(1000000)  = " + sumRec(1000000));
        } catch (StackOverflowError e) {
            System.out.println("sumRec(1000000)  threw " + e);
        }
        System.out.println("sumIter(1000000) = " + sumIter(1000000));
    }
}

n = 5      recursive:     6 calls,     6 frames deep -> 15
           iterative:     5 loop steps, 1 frame     -> 15
n = 100    recursive:   101 calls,   101 frames deep -> 5050
           iterative:   100 loop steps, 1 frame     -> 5050
n = 10000  recursive: 10001 calls, 10001 frames deep -> 50005000
           iterative: 10000 loop steps, 1 frame     -> 50005000

sumRec(1000000)  threw java.lang.StackOverflowError
sumIter(1000000) = 500000500000

Cùng đáp án, và gần như cùng khối lượng phép tính. Khác nhau ở chỗ công việc được giữ ở đâu: bản đệ quy cần n + 1 frame sống cùng lúc, bản vòng lặp cần một frame và hai local variable. Tới một triệu thì khác biệt đó không còn là chuyện thẩm mỹ nữa.

Tóm lại một cách trung thực: với phép đếm thẳng từ 1 tới n, vòng lặp tốt hơn và không có gì để tranh cãi. Với bất cứ thứ gì có hình dạng tree, đệ quy thường là code ngắn hơn và rõ hơn, còn phương án stack tường minh là thứ bạn quay về khi độ sâu thực sự không có giới hạn.

Viết lại đệ quy bằng stack tường minh

"Mọi đệ quy đều viết lại được bằng vòng lặp" là đúng, nhưng nó không có nghĩa là "viết lại thành một vòng for". Việc bạn thực sự làm là ôm lấy phần việc mà call stack đang làm hộ. Đây là một tree walk dùng ArrayDeque thay cho các frame:

import java.io.File;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class WalkIterative {
    record Entry(File file, String indent) {}

    static void walk(File root) {
        Deque<Entry> stack = new ArrayDeque<>();
        stack.push(new Entry(root, ""));
        while (!stack.isEmpty()) {
            Entry e = stack.pop();
            System.out.println(e.indent() + e.file().getName() + (e.file().isDirectory() ? "/" : ""));
            File[] entries = e.file().listFiles();
            if (entries == null) continue;
            Arrays.sort(entries);
            for (int i = entries.length - 1; i >= 0; i--) {
                stack.push(new Entry(entries[i], e.indent() + "    "));
            }
        }
    }

    public static void main(String[] args) {
        walk(new File("project"));
    }
}

Nó cho ra output giống từng byte với bản đệ quy ở phần sau, và nó không thể làm tràn call stack vì phần việc đang chờ nằm trên heap. Nó cũng dài hơn hẳn, và vòng for push các con theo thứ tự ngược tồn tại chỉ để lấy lại đúng thứ tự duyệt. Đánh đổi đó — nhiều code hơn, không giới hạn độ sâu — chính là toàn bộ lý do tồn tại của bản viết lại.

Tail recursion và vì sao Java không tối ưu nó

Một lời gọi ở tail position khi nó là việc cuối cùng method làm: kết quả của nó được return thẳng, không còn phép tính nào chờ. countdown bên dưới là tail recursive; factorial thì không, vì vẫn còn một phép nhân nợ lại khi recursive call return.

Trong các ngôn ngữ đảm bảo tail-call optimisation, compiler có thể biến một tail call thành một lệnh nhảy và tái sử dụng frame, nhờ đó đệ quy chạy trong lượng stack không đổi. Java không đảm bảo điều đó, và HotSpot không làm điều đó. Bytecode nói rất rõ — đây là javap -c trên một countdown tail recursive:

  static void countdown(int);
    Code:
       0: getstatic     #7                  // Field calls:J
       3: lconst_1
       4: ladd
       5: putstatic     #7                  // Field calls:J
       8: iload_0
       9: ifne          13
      12: return
      13: iload_0
      14: iconst_1
      15: isub
      16: invokestatic  #13                 // Method countdown:(I)V
      19: return

Offset 16 là một invokestatic — một lời gọi method thật, push một frame thật — theo sau là return ở offset 19. javac sinh ra một lời gọi, không phải một lệnh nhảy về offset 0. Và JVM hành xử đúng như vậy:

public class TailDepth {
    static long calls = 0;

    static void countdown(int n) {
        calls++;
        if (n == 0) return;
        countdown(n - 1);
    }

    public static void main(String[] args) {
        try {
            countdown(1000000);
            System.out.println("finished, calls = " + calls);
        } catch (StackOverflowError e) {
            System.out.println("StackOverflowError after " + calls + " calls");
        }
    }
}

StackOverflowError after 1267 calls
StackOverflowError after 1267 calls
StackOverflowError after 1267 calls
StackOverflowError after 1267 calls
StackOverflowError after 1267 calls

Đó là năm lần chạy với -Xss256k. Trên stack mặc định, cùng chương trình đó chết sau 31256, 32573 và 32101 lời gọi. Kiểu nào cũng chết: một method tail recursive trong Java tiêu tốn một frame cho mỗi lời gọi y hệt mọi method khác, nên viết đệ quy ở dạng tail không mua được gì trong Java. Nếu độ sâu là vấn đề, cách sửa là vòng lặp, không phải sắp xếp lại recursive call.

Mutual recursion

Đệ quy không nhất thiết phải là một method gọi chính nó trực tiếp. Hai method có thể gọi lẫn nhau, gọi là mutual recursion. Mỗi method vẫn cần base case riêng:

public class EvenOdd {
    static boolean isEven(int n) {
        if (n == 0) return true;
        return isOdd(n - 1);
    }

    static boolean isOdd(int n) {
        if (n == 0) return false;
        return isEven(n - 1);
    }

    public static void main(String[] args) {
        for (int n = 0; n <= 5; n++) {
            System.out.println(n + ": isEven=" + isEven(n) + ", isOdd=" + isOdd(n));
        }
    }
}

0: isEven=true, isOdd=false
1: isEven=false, isOdd=true
2: isEven=true, isOdd=false
3: isEven=false, isOdd=true
4: isEven=true, isOdd=false
5: isEven=false, isOdd=true

Cặp này là minh hoạ chứ không phải lời khuyên — n % 2 == 0 mới là đáp án thật và không tốn frame nào. Mutual recursion đáng đồng tiền trong parser và interpreter, nơi bản thân grammar là đệ quy lẫn nhau: một expression chứa các term, và một term có thể chứa một expression trong ngoặc.

Đệ quy trên cấu trúc dữ liệu, không phải trên số

Mọi ví dụ tới giờ đều thu nhỏ một con số, và với số thì vòng lặp thường là công cụ tốt hơn. Đệ quy trả lại giá trị của nó khi dữ liệu lồng nhau và bạn không biết nó sâu tới đâu. Cây thư mục là trường hợp kinh điển:

import java.io.File;
import java.util.Arrays;

public class WalkTree {
    static void walk(File dir, String indent) {
        File[] entries = dir.listFiles();
        if (entries == null) return;
        Arrays.sort(entries);
        for (File f : entries) {
            System.out.println(indent + f.getName() + (f.isDirectory() ? "/" : ""));
            if (f.isDirectory()) {
                walk(f, indent + "    ");
            }
        }
    }

    public static void main(String[] args) {
        File root = new File("project");
        System.out.println(root.getName() + "/");
        walk(root, "    ");
    }
}

Chạy trên một cây nhỏ gồm project/README.md, project/docs/guide.md, project/src/main/App.java, project/src/main/Util.java và project/src/test/AppTest.java:

project/
    README.md
    docs/
        guide.md
    src/
        main/
            App.java
            Util.java
        test/
            AppTest.java

Hãy để ý thứ không có trong method đó: không stack, không queue, không danh sách thư mục còn phải duyệt, không biến đếm độ sâu. Base case là "một thư mục không có mục nào, hoặc một thứ không phải thư mục" và nó được diễn đạt bằng việc vòng for đơn giản là không chạy. Recursive case là "với mỗi thư mục con, làm đúng việc đó ở mức sâu hơn một bậc".

Thử viết nó thành một vòng lặp thuần và bạn lập tức cần chỗ để giữ những thư mục chưa mở — tức là bản ArrayDeque ở trên, và bản đó chính là call stack được dựng lại bằng tay. Đó là phép thử trung thực để biết đệ quy có phải lựa chọn đúng hay không: nếu bản vòng lặp cần một stack của riêng nó, hãy dùng đệ quy.

Khi nào nên dùng đệ quy và khi nào không

Lập luận về độ sâu là thứ quyết định phần lớn tình huống thực tế. Đệ quy kiểu divide and conquer trên một triệu phần tử chỉ sâu khoảng 20 frame và hoàn toàn an toàn; đệ quy tuyến tính trên một triệu phần tử sâu một triệu frame thì không.

Lỗi thường gặp và output chúng tạo ra

Lỗi thứ ba là thành viên nguy hiểm trong danh sách đó, vì không có gì thất bại cả. 0! bằng 1 chứ không phải 0, và làm sai chỗ đó đầu độc mọi kết quả:

public class BadBaseCase {
    /* Sai: base case trả về 0 cho n = 0, nên mọi tích đều sụp về 0. */
    static long factorialWrong(int n) {
        if (n == 0) return 0;
        return n * factorialWrong(n - 1);
    }

    /* Đúng: 0! là 1, phần tử đơn vị của phép nhân. */
    static long factorialRight(int n) {
        if (n == 0) return 1;
        return n * factorialRight(n - 1);
    }

    public static void main(String[] args) {
        for (int n = 0; n <= 5; n++) {
            System.out.println("n=" + n + "  wrong=" + factorialWrong(n) + "  right=" + factorialRight(n));
        }
    }
}

n=0  wrong=0  right=1
n=1  wrong=0  right=1
n=2  wrong=0  right=2
n=3  wrong=0  right=6
n=4  wrong=0  right=24
n=5  wrong=0  right=120

Mọi đáp án đều bằng 0, vì mọi tích cuối cùng đều nhân với base case. Không exception, không cảnh báo, không stack trace nào để đọc — chỉ có những con số sai. Luôn tự tính base case bằng tay trước khi tin vào phần đệ quy phía trên nó.

FAQ

Đệ quy có chậm hơn vòng lặp trong Java không?

Một lời gọi không miễn phí — nó push một frame, còn một vòng lặp thì không — nhưng chi phí đó nhỏ và JIT có thể inline các recursive call nông. Trên thực tế, code đệ quy chậm thì chậm vì một trong hai lý do chẳng liên quan gì tới chi phí lời gọi: nó đang tính lại subproblem đã giải, hoặc nó làm nhiều việc hơn bản vòng lặp. Hãy đếm số lời gọi trước; con số đó lặp lại được và thường giải thích hết mọi chuyện.

Đệ quy trong Java đi sâu được bao nhiêu?

Không có giới hạn nào do ngôn ngữ định nghĩa. Nó phụ thuộc stack size của thread, kích thước mỗi frame, platform và bản build của JVM. Đo được ở đây: khoảng 44000 tới 59000 frame trên stack mặc định qua ba lần chạy, ổn định ở 1479 với -Xss256k, và khoảng 20000 với -Xss1m. Hãy coi mọi con số cụ thể là phép đo của một máy trong một ngày, không phải một hằng số.

JVM có tối ưu tail recursion không?

Không. Ngôn ngữ Java không đảm bảo tail call và HotSpot không loại bỏ tail call, nên một method tail recursive vẫn push một frame cho mỗi lời gọi và vẫn tràn stack — đã chứng minh ở trên bằng output javap cho thấy một invokestatic ở tail position và một lần chạy chết sau 1267 lời gọi. Nếu bạn cần lượng stack không đổi, hãy viết vòng lặp.

Có bắt được StackOverflowError không?

Về cú pháp thì được: nó là một Throwable, nên catch (StackOverflowError e) compile và chạy được, đúng như chương trình đếm độ sâu ở trên dựa vào. Trong code thật thì đó là ý tồi. Nó là một Error, nghĩa là JVM đang báo một tình huống chương trình của bạn không được kỳ vọng phục hồi, và bạn không có cách nào biết cái stack tháo dở dang để lại trạng thái gì. Hãy bắt nó trong công cụ chẩn đoán, đừng bao giờ bắt trong logic production.

Gặp StackOverflowError thì cứ tăng -Xss có được không?

Thỉnh thoảng đó đúng là đáp án, với một cây thực sự sâu hoặc một thư viện đệ quy theo từng phần tử input. Nhưng phần lớn trường hợp, tràn stack là một bug — thiếu base case, hoặc bước không thu nhỏ — và stack lớn hơn chỉ trì hoãn nó. Hãy nhìn stack trace trước: vài dòng lặp lại hàng nghìn lần nghĩa là bug, còn một trace dài gồm nhiều method khác nhau nghĩa là bạn thực sự đang ở độ sâu đó.

Chuyển đệ quy thành vòng lặp thế nào?

Nếu đệ quy là tuyến tính, như sumTo hay một countdown tail recursive, một vòng for hoặc while với biến cộng dồn là đủ. Nếu nó phân nhánh, như một tree walk, bạn cần một stack tường minh — push node gốc, rồi lặp lại việc pop một phần tử, xử lý nó và push các con của nó, đúng như bản ArrayDeque ở trên. Quy tắc chung: những gì các frame đang nhớ hộ bạn, giờ bạn phải tự nhớ.

Kết luận

Đệ quy là một method tự gọi chính nó với input nhỏ hơn, và nó cần đúng hai thứ để hoạt động: một base case return mà không gọi lại, và một recursive case tiến về phía base case đó. Mọi thứ hỏng đều đến từ việc phá vỡ một trong hai — không có base case, một bước không thu nhỏ, hoặc base case trả về sai giá trị — và hai lỗi đầu tự tố cáo bằng StackOverflowError với một dòng lặp lại suốt trace. Độ sâu bị chặn bởi stack, phụ thuộc máy, và không hề thay đổi khi bạn viết lời gọi ở tail position, vì JVM không loại bỏ tail call. Còn khi một đệ quy chạy chậm, hãy đếm số lời gọi: 2.692.537 cho fib(30) so với 59 khi memoise là toàn bộ câu chuyện vì sao bản naive là một cái bẫy.

Chỗ đệ quy thực sự thắng là dữ liệu có hình dạng lồng nhau và độ sâu không biết trước — một cây thư mục, một parse tree, một tài liệu JSON. Phép thử rất đơn giản: nếu viết vòng lặp buộc bạn phải dựng một stack của riêng mình, thì call stack đã làm sẵn việc đó cho bạn rồi.

Bài tiếp theo rời khỏi Java thủ tục và bắt đầu với object: class là gì, object là gì, new dựng ra một object thế nào, và field, constructor cùng this thực sự nghĩa là gì — đúng chỗ mà chữ static bạn viết trên mọi method từ trước tới giờ cuối cùng cũng có một lựa chọn thay thế.