Đệ quy JavaScript

Trong hướng dẫn này, bạn sẽ tìm hiểu về đệ quy trong JavaScript với sự trợ giúp của các ví dụ.

Đệ quy là một quá trình gọi chính nó. Một hàm gọi chính nó được gọi là một hàm đệ quy.

Cú pháp cho hàm đệ quy là:

function recurse() {
    // function code
    recurse();
    // function code
}

recurse();

Ở đây, recurse()hàm là một hàm đệ quy. Nó đang gọi chính nó bên trong hàm.Làm việc của đệ quy trong JavaScript

Một hàm đệ quy phải có một điều kiện để ngừng gọi chính nó. Nếu không, hàm được gọi là vô thời hạn.

Khi điều kiện được đáp ứng, hàm sẽ ngừng gọi chính nó. Đây được gọi là điều kiện cơ bản.

Để ngăn chặn đệ quy vô hạn, bạn có thể sử dụng câu lệnh if … else (hoặc cách tiếp cận tương tự) trong đó một nhánh thực hiện lệnh gọi đệ quy và nhánh kia thì không.

Vì vậy, nó thường trông như thế này.

function recurse() {
    if(condition) {
        recurse();
    }
    else {
        // stop calling recurse()
    }
}

recurse();

Một ví dụ đơn giản về hàm đệ quy là đếm ngược giá trị đến 1.

Ví dụ 1: In số

// program to count down numbers to 1
function countDown(number) {

    // display the number
    console.log(number);

    // decrease the number value
    const newNumber = number - 1;

    // base case
    if (newNumber > 0) {
        countDown(newNumber);
    }
}

countDown(4);

Đầu ra

4
3
2
1

Trong chương trình trên, người dùng chuyển một số làm đối số khi gọi một hàm.

Trong mỗi lần lặp, giá trị số giảm đi 1 và hàm countDown()được gọi cho đến khi số dương. Đây, newNumber > 0là điều kiện cơ bản.

Lời gọi đệ quy này có thể được giải thích theo các bước sau:

countDown(4) prints 4 and calls countDown(3)
countDown(3) prints 3 and calls countDown(2)
countDown(2) prints 2 and calls countDown(1)
countDown(1) prints 1 and calls countDown(0)

Khi số đến 0 , điều kiện cơ bản được đáp ứng và hàm không được gọi nữa.

Ví dụ 2: Tìm giai thừa

// program to find the factorial of a number
function factorial(x) {

    // if number is 0
    if (x === 0) {
        return 1;
    }

    // if number is positive
    else {
        return x * factorial(x - 1);
    }
}

const num = 3;

// calling factorial() if num is non-negative
if (num > 0) {
    let result = factorial(num);
    console.log(`The factorial of ${num} is ${result}`);
}

Đầu ra

The factorial of 3 is 6

Khi bạn gọi hàm factorial()với một số nguyên dương, nó sẽ gọi một cách đệ quy chính nó bằng cách giảm số lượng.

Quá trình này tiếp tục cho đến khi số trở thành 1 . Sau đó, khi con số đạt đến 0 , 1 được trả về.Tính toán giai thừa sử dụng đệ quy

Lời gọi đệ quy này có thể được giải thích theo các bước sau:

factorial(3) returns 3 * factorial(2)
factorial(2) returns 3 * 2 * factorial(1)
factorial(1) returns 3 * 2 * 1 * factorial(0)
factorial(0) returns 3 * 2 * 1 * 1