Recursion: base case and recursive case · ⁨Đệ quy: trường hợp cơ bản và trường hợp đệ quy⁩

English

A method that calls itself

Recursion is when a method calls itself to solve a smaller piece of the same problem.
On the AP CSA exam you mostly trace recursion (follow the calls by hand). Writing small recursive methods helps you trace well.
Every recursive method needs two parts: a base case and a recursive case.

Tiếng Việt

Một phương thức gọi chính nó

Đệ quy là khi một phương thức gọi chính nó để giải quyết một phần nhỏ hơn của cùng vấn đề.
Trong kỳ thi AP CSA, bạn chủ yếu vẽ sơ đồ (trace) đệ quy (theo dõi các lời gọi bằng tay). Viết các phương thức đệ quy nhỏ giúp bạn vẽ sơ đồ tốt hơn.
Mọi phương thức đệ quy đều cần hai phần: một trường hợp cơ sở và một trường hợp đệ quy.

English

Base case and recursive case

Base case: the simplest input, where you return an answer without calling yourself. This stops the recursion.
Recursive case: you call the same method with a smaller input, then build the answer.
Without a base case, the method calls forever and crashes (a stack overflow).

Tiếng Việt

Trường hợp cơ sở và trường hợp đệ quy

Trường hợp cơ sở: đầu vào đơn giản nhất, nơi bạn trả về kết quả không gọi chính mình. Điều này dừng quá trình đệ quy.
Trường hợp đệ quy: bạn gọi chính phương thức đó với đầu vào nhỏ hơn, sau đó xây dựng kết quả.
Nếu không có trường hợp cơ sở, phương thức sẽ gọi mãi mãi và gây lỗi (quá tải stack - stack overflow).

English

Example: factorial

factorial(n) means n * (n-1) * ... * 1. For example factorial(4) = 24.
Base case: factorial(1) is 1.
Recursive case: factorial(n) is n * factorial(n - 1).

Tiếng Việt

Ví dụ: Giai thừa

factorial(n) biểu thị n * (n-1) * ... * 1. Ví dụ như factorial(4) = 24.
Trường hợp cơ sở: factorial(1) là 1.
Trường hợp quy hồi: factorial(n) là n * factorial(n - 1).

public class Recursion {
    public static int factorial(int n) {
        if (n <= 1) {                  // base case
            return 1;
        }
        return n * factorial(n - 1);   // recursive case
    }
}

English

How the calls unwind

Each call waits for the smaller call to finish. Then it multiplies and returns.
Trace factorial(3). Calls go down, then answers come back up.

Tiếng Việt

Cách các cuộc gọi hoàn tác

Mỗi cuộc gọi chờ cuộc gọi nhỏ hơn hoàn thành. Sau đó nhân và trả về kết quả.
Theo dõi factorial(3). Các cuộc gọi đi xuống, sau đó các câu trả lời quay lại lên trên.

factorial(3) = 3 * factorial(2)        <- waits
  factorial(2) = 2 * factorial(1)      <- waits
    factorial(1) = 1                   <- base case, returns 1
  factorial(2) = 2 * 1 = 2             <- returns 2
factorial(3) = 3 * 2 = 6               <- returns 6

English

Example: sum to n

sumTo(n) adds 1 + 2 + ... + n. For example sumTo(4) = 10.
Base case: sumTo(0) is 0 (nothing to add).
Recursive case: sumTo(n) is n + sumTo(n - 1).

Tiếng Việt

Ví dụ: tổng đến n

sumTo(n) cộng 1 + 2 + ... + n. Ví dụ sumTo(4) = 10.
Trường hợp cơ sở: sumTo(0) là 0 (không có gì để cộng).
Trường hợp quy hồi: sumTo(n) là n + sumTo(n - 1).

public class Recursion {
    public static int sumTo(int n) {
        if (n <= 0) {                  // base case
            return 0;
        }
        return n + sumTo(n - 1);       // recursive case
    }
}

English

Recursion over an array

We can also recurse with an index that moves toward the end.
Base case: when the index is past the last spot, return 0.
Recursive case: add a[i] to the sum of the rest, arraySum(a, i + 1).

Tiếng Việt

Quy hồi qua mảng

Chúng ta cũng có thể thực hiện quy hồi với một chỉ số di chuyển về phía cuối.
Trường hợp cơ sở: khi chỉ số ở quá vị trí cuối cùng, trả về 0.
Trường hợp quy hồi: cộng a[i] vào tổng của phần còn lại, arraySum(a, i + 1).

English

To sum the whole array you start at index 0: arraySum(a, 0).
Each call handles one value and trusts the next call for the rest.

Tiếng Việt

public class Recursion {
    public static int arraySum(int[] a, int i) {
        if (i >= a.length) {           // base case: past the end
            return 0;
        }
        return a[i] + arraySum(a, i + 1);
    }
}

Để tính tổng toàn bộ mảng, bạn bắt đầu từ chỉ số 0: arraySum(a, 0).
Mỗi cuộc gọi xử lý một giá trị và tin tưởng cuộc gọi tiếp theo cho phần còn lại.

English

Common mistakes

Recursion needs a base case, or it throws StackOverflowError.
Each call must move closer to the base case.

Tiếng Việt

Lỗi thường gặp

Quy hồi cần một trường hợp cơ sở, nếu không sẽ gây ra StackOverflowError.
Mỗi lần gọi phải tiến gần hơn đến trường hợp cơ sở.

English

Now you try

Each task gives you a method skeleton with a TODO. Write the base case and the recursive case.
A hidden Harness calls your method with several values and checks the result.
Press Run to compile, then Check answer.

Tiếng Việt

Bây giờ bạn thử

Mỗi bài tập cung cấp cho bạn một khung phương thức có TODO. Viết cả trường hợp cơ sở và trường hợp quy hồi.
Một ** Harness** ẩn gọi phương thức của bạn với nhiều giá trị và kiểm tra kết quả.
Nhấn Run để biên dịch, sau đó nhấn Check answer.

Explore · ⁨Khám phá⁩

Recursion: base + recursive case · ⁨Đệ quy: trường hợp cơ bản + trường hợp đệ quy⁩

Calls split until a base case, then answers return up. · ⁨Các lời gọi tách ra cho đến khi đạt đến một trường hợp cơ bản, sau đó các kết quả sẽ được trả ngược lên trên.⁩

Complete factorial(int n) so it returns n * (n-1) * ... * 1 using recursion. Use a base case for n <= 1. The checker tests several values. · ⁨Hoàn thiện factorial(int n) sao cho trả về n * (n-1) * ... * 1 bằng đệ quy. Sử dụng trường hợp cơ sở cho n <= 1. Bộ kiểm tra sẽ thử nhiều giá trị khác nhau.⁩

public class Recursion {
    // Return n! = n * (n-1) * ... * 1, using recursion.
    public static int factorial(int n) {
        // TODO: base case for n <= 1, then n * factorial(n - 1)
        return 0;
    }
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

Complete sumTo(int n) so it returns 1 + 2 + ... + n using recursion. Use a base case for n <= 0. The checker tests several values. · ⁨Hoàn thiện sumTo(int n) sao cho trả về 1 + 2 + ... + n bằng đệ quy. Sử dụng trường hợp cơ sở cho n <= 0. Bộ kiểm tra sẽ thử nhiều giá trị khác nhau.⁩

public class Recursion {
    // Return 1 + 2 + ... + n, using recursion.
    public static int sumTo(int n) {
        // TODO: base case for n <= 0, then n + sumTo(n - 1)
        return 0;
    }
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

Complete arraySum(int[] a, int i) so it returns the sum of a[i] to the end, using recursion. Base case: when i is past the last spot, return 0. The checker tests several arrays. · ⁨Hoàn thành arraySum(int[] a, int i) để trả về tổng từ a[i] đến cuối, sử dụng đệ quy. Trường hợp cơ bản: khi i vượt qua vị trí cuối cùng, hãy trả về 0. Bộ kiểm tra sẽ thử nghiệm với nhiều mảng.⁩

public class Recursion {
    // Return a[i] + a[i+1] + ... + a[last], using recursion.
    public static int arraySum(int[] a, int i) {
        // TODO: base case when i >= a.length, then a[i] + arraySum(a, i + 1)
        return 0;
    }
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

Recursion: base case and recursive case · ⁨Đệ quy: trường hợp cơ bản và trường hợp đệ quy⁩

A method that calls itself

Một phương thức gọi chính nó

Base case and recursive case

Trường hợp cơ sở và trường hợp đệ quy

Example: factorial

Ví dụ: Giai thừa

How the calls unwind

Cách các cuộc gọi hoàn tác

Example: sum to n

Ví dụ: tổng đến n

Recursion over an array

Quy hồi qua mảng

Common mistakes

Lỗi thường gặp

Now you try

Bây giờ bạn thử

Recursion: base + recursive case · ⁨Đệ quy: trường hợp cơ bản + trường hợp đệ quy⁩

Handout · ⁨Tài liệu⁩

Log in or create account · ⁨Đăng nhập hoặc tạo tài khoản⁩

Your subject · ⁨Môn học của bạn⁩

All sections · ⁨Tất cả các mục⁩

Feedback & help · ⁨Phản hồi & hỗ trợ⁩