Recursion - Đệ quy là gì

"Recursion is when a function calls itself until it doesn't"

Là một hàm gọi chính nó cho tới khi dừng.

Vậy khi nào nó dừng?

Khi nó thỏa điều kiện và không gọi chính nó nữa! (Duh? I'm I a joke to you)

Vâng đúng là như vậy.

Trong Recursion nó hai phần chính:

- Base case: Trường hợp cơ bản - Tại case này, hàm sẽ không gọi lại chính nó nữa => Recursion sẽ dừng lại.

- Recursive case: Trường hợp recursive - Như tên gọi, case này thì hàm sẽ tiếp tục gọi (recursive) chính nó tiếp.

Ví dụ: Bằng bài toàn tìm giai thừa (factorial)

function factorial(num) {

if (num === 1) return 1 // Base case

return num * factorial(num - 1) // Recursive case

}

console.log(factorial(4)) // 24

Để hiểu hơn, hãy xem Call stack của hàm trên:

4. factorial(1) | return 1

3. factorial(2) | return 2 * factorial(1)

2. factorial(3) | return 3 * factorial(2)

1. factorial(4) | return 4 * factorial(3)

Như vậy sau khi hàm dừng recursive thì Call stack sẽ được dỡ ra và các giá trị sẽ lần lượt được return vào nơi đã gọi nó.

Ta sẽ có:

4. return 1

3. 1 >> return 2 * factorial(1) tức 2 * 1 = 2

2. 2 >> return 3 * factorial(2) tức 3 * 2 = 6

1. 6 >> return 4 * factorial(3) tức 4 * 6 = 24

Hãy tìm một vài bài toán về recursive tự làm thử, bạn sẽ dần hiểu ngay thôi