Đệ quy cho người mới bắt đầu

Giới thiệu

Recursive (đệ quy) là một khái niệm khá đơn giản mà chúng ta đã tiếp xúc từ toán lớp 3:

Bây giờ chắc bạn cũng có thể mường tượng đệ quy là gì rồi phải không? Đây là một quyển sách toán lớp 3, ở trong bìa sách có ba học sinh, trong đó có một học sinh lại cầm một quyển sách toán lớp ba khác. Và trong quyển sách đó lại có ba học sinh, và cũng có một học sinh cầm một quyển sách lớp 3. Đây chính là ví dụ cho một khái niệm rất căn bản trong bất kỳ ngôn ngữ lập trình nào – khái niệm “đệ quy”.

---

Đệ quy là gì?

Trong Khoa học máy tính, hàm đệ quy là hàm gọi chính bản thân nó. Một hàm đệ quy sẽ có dạng như sau:

function foo() {
    dosomething();
    foo(); // gọi chính nó
    maybedosomething();
    return otherthing;
}Code language: JavaScript (javascript)

Để hiểu rõ hơn mình sẽ ví dụ thực tế như sau:

Giáo viên thể dục yêu cầu lớp điểm danh từ 1 đến hết

Trình tự xảy ra sẽ như sau giả sử lớp có có 5 người:

1
2
3
4
5
Hết !!!!

Code:

function diemdanh(n) {
    for (let i = 1; i <= n; i++) {
        console.log(i);
    }
    console.log('Hết !!!!');
}
diemdanh(5);Code language: JavaScript (javascript)

Nếu bạn không biết vị trí mình đang đứng là thứ mấy, bạn hỏi thằng đứng trước và thằng đó cũng không nhớ và tiếp tục hỏi thằng phía trước…. truyền nhau cho đến thằng đầu hàng và nó hô “1” và những đứa sau đó sẽ truyền thứ tự dần tới đến bạn.

Trình tự như sau:

Thằng đứng thứ 3: Ê tao đang đứng thứ mấy thế ????
Thằng đứng thứ 2: Ê tao đang đứng thứ mấy thế ????
Thằng đứng thứ 1: Tao đang đứng thứ 1
Thằng đứng thứ 2: Thế tao đứng thứ 2
Thằng đứng thứ 3: Thế tao đứng thứ 3

Code:

function my_index(n) {
    if (n == 1) {
        console.log(`Thằng đứng thứ ${n}: Tao đang đứng thứ 1`);
    }
    else {
        console.log(`Thằng đứng thứ ${n}: Ê tao đang đứng thứ mấy thế ????`);
        my_index(n - 1);
        console.log(`Thằng đứng thứ ${n}: Thế tao đứng thứ ${n}`);
    }
}
my_index(3);Code language: JavaScript (javascript)

---

Ví dụ về Đệ quy trong toán học

Đệ quy thường được áp dụng trong toán học như tính giá trị của một số trong 1 dãy như Fibonacci, giai thừa …. hoặc có thể số mũ.

Dãy Fibonacci

Mỗi phần tử mới trong dãy Fibonacci được tạo ra bằng cách cộng 2 phần tử trước đó. Bằng cách bắt đầu với 0 và 1, 10 phần tử đầu tiên sẽ là:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…

Nếu muốn tìm số thứ n của dãy này, đơn giản là gán 2 số đầu tiên của dãy là 0, 1 và tính tổng của số thứ n – 1 và số thứ n – 2.

Code:

function fibo(n) {
    if (n <= 1)
        return n;
    return fibo(n - 1) + fibo(n - 2);

console.log(fibo(10));Code language: JavaScript (javascript)

Kết quả:

88

Giai thừa

Giai thừa được định nghĩa như sau:

n! = n * (n – 1) * (n – 2) * … * 1

Ta có thể dễ dàng nhận ra công thức sau:

n! = n * (n – 1)!

Code:

function factorial(n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);

console.log(factorial(5));Code language: JavaScript (javascript)

Kết quả:

120

Số mũ

Công thức vẽ số mũ chắc mọi người đều biết rồi:

a ^ x = tích của x số a

Code:

function pow(a, x) {
    if (a == 0) && (x == 0) {
        return 'Vô nghĩa';
    }
    else if (x == 0) {
        return 1;
    }
    else if (x == 1) {
        return a;
    }
    return a * pow(a, x - 1);

console.log(pow(2, 5));Code language: JavaScript (javascript)

Code chỉ áp dụng trong trường hợp a khác 0 và x thuộc N.

Kết luận

Qua bài viết, chúng ta rút ra bài học gì? Muốn giải 1 bài toán lớn khi lập trình, hãy bắt đầu giải từ những bài toán nhỏ hơn.

Tham khảo:

https://pymi.vn/blog/print-recursively/

https://medium.com/@tung491/recursive-function-v%C3%A0-m%E1%BB%99t-v%C3%A0i-v%C3%AD-d%E1%BB%A5-9a613e6eec27

Các bạn có thể tham khảo các bài viết hay về JavaScript tại đây.

---

Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.