Hàm tính tổng trong Javascript

Đây chỉ là ví dụ minh họa về hàm đệ quy trong JavaScript. Thực tế, bạn có thể sử dụng vòng lặp

function sayHello(count) {
  // phần cơ sở: điều kiện thoát đệ quy là biến count <= 0
  if (count <= 0) {
    return;
  }

  // xử lý logic cơ bản
  console.log("Hello world!");

  // phần đệ quy: gọi lại chính hàm sayHello
  sayHello(count - 1);
}
4 để giải quyết bài toán trên:

function sayHello(count) {
  for (let i = 0; i < count; i++) {
    console.log("Hello world!");
  }
}

sayHello(5);

Kết quả hoàn toàn tương đương. Tuy nhiên, có rất nhiều trường hợp việc sử dụng hàm đệ quy lại giúp code trở nên ngắn gọn, rõ ràng và dễ bảo trì hơn sử dụng vòng lặp.

Vì vậy, mình hãy cùng tìm hiểu về hàm đệ quy trong JavaScript để biết cách áp dụng khi cần thiết.

Các thành phần cơ bản của hàm đệ quy


Hàm đệ quy nói chung và hàm đệ quy trong JavaScript nói riêng, có hai thành phần đặc trưng:

  • Phần cơ sở: điều kiện để thoát đệ quy.
  • Phần đệ quy: gọi lại chính nó.

function sayHello(count) {
  // phần cơ sở: điều kiện thoát đệ quy là biến count <= 0
  if (count <= 0) {
    return;
  }

  // xử lý logic cơ bản
  console.log("Hello world!");

  // phần đệ quy: gọi lại chính hàm sayHello
  sayHello(count - 1);
}

Cũng tương tự như điều kiện để thoát vòng lặp, nếu không có điều kiện cơ sở thì hàm đệ quy sẽ không bao giờ dừng lại (đệ quy vô hạn), dẫn đến tràn stack.

Ví dụ bỏ qua điều kiện cơ cở của hàm đệ quy trên:

function sayHello(count) {
  // // phần cơ sở: điều kiện thoát đệ quy là biến count <= 0
  // if (count <= 0) {
  //   return;
  // }

  console.log("Hello world!");

  // phần đệ quy: gọi lại chính hàm sayHello
  sayHello(count - 1);
}

sayHello();

Kết quả là Hello world! được in ra khoảng hơn

function sayHello(count) {
  // phần cơ sở: điều kiện thoát đệ quy là biến count <= 0
  if (count <= 0) {
    return;
  }

  // xử lý logic cơ bản
  console.log("Hello world!");

  // phần đệ quy: gọi lại chính hàm sayHello
  sayHello(count - 1);
}
5 lần thì bị lỗi tràn stack, cụ thể: Uncaught RangeError: Maximum call stack size exceeded.

Kết quả

Hello world! Hello world! ... Hello world!

Uncaught RangeError: Maximum call stack size exceeded

Chú ý: con số

function sayHello(count) {
  // phần cơ sở: điều kiện thoát đệ quy là biến count <= 0
  if (count <= 0) {
    return;
  }

  // xử lý logic cơ bản
  console.log("Hello world!");

  // phần đệ quy: gọi lại chính hàm sayHello
  sayHello(count - 1);
}
5 trên chỉ là tương đối, phụ thuộc vào từng JavaScript Engine

Call stack là gì?

  • Call: là lời gọi hàm.
  • Stack: là ngăn xếp, hoạt động theo nguyên tắc "vào sau ra trước", tiếng anh là Last In First Out - LIFO.

Khi gọi hàm, JavaScript Engine đưa các lời gọi hàm vào trong một ngăn xếp.

  • Hàm gọi sau được đưa lên đầu ngăn xếp, đến khi gọi xong thì đưa hàm ra khỏi ngăn xếp.
  • Cứ như vậy đến khi ngăn xếp trống thì nghĩa là đã gọi xong hàm.

Việc lưu lời gọi hàm vào ngăn xếp là tốn bộ nhớ. Vì vậy, JavaScript Engine sẽ giới hạn kích thước của ngăn xếp (khoảng

function sayHello(count) {
  // phần cơ sở: điều kiện thoát đệ quy là biến count <= 0
  if (count <= 0) {
    return;
  }

  // xử lý logic cơ bản
  console.log("Hello world!");

  // phần đệ quy: gọi lại chính hàm sayHello
  sayHello(count - 1);
}
5 hoặc hơn, tùy thuộc vào engine).

Khi sử dụng hàm đệ quy trong JavaScript, bạn cần chú ý đến điều kiện cơ sở để thoát đệ quy, tránh đệ quy vô hạn dẫn đến tràn stack như ví dụ trên.

Sử dụng hàm đệ quy khi nào?

Khi một bài toán có thể chia ra thành nhiều bài toán con và bài toán con có dạng tương tự như bài toán cha thì bạn có thể sử dụng hàm đệ quy.

Ví dụ bài toán tính giá trị của lũy thừa

function sayHello(count) {
  // phần cơ sở: điều kiện thoát đệ quy là biến count <= 0
  if (count <= 0) {
    return;
  }

  // xử lý logic cơ bản
  console.log("Hello world!");

  // phần đệ quy: gọi lại chính hàm sayHello
  sayHello(count - 1);
}
8 (a mũ b) với định nghĩa toán học là:

a^b = 1, nếu b = 0
a^b = a * a^(b-1), nếu b > 0

Theo định nghĩa trên, bài toán cha là tính

function sayHello(count) {
  // phần cơ sở: điều kiện thoát đệ quy là biến count <= 0
  if (count <= 0) {
    return;
  }

  // xử lý logic cơ bản
  console.log("Hello world!");

  // phần đệ quy: gọi lại chính hàm sayHello
  sayHello(count - 1);
}
8 lại dựa trên bài toán con
function sayHello(count) {
  // // phần cơ sở: điều kiện thoát đệ quy là biến count <= 0
  // if (count <= 0) {
  //   return;
  // }

  console.log("Hello world!");

  // phần đệ quy: gọi lại chính hàm sayHello
  sayHello(count - 1);
}

sayHello();
0. Vì vậy, bạn có thể áp dụng hàm đệ quy để tính giá trị
function sayHello(count) {
  // phần cơ sở: điều kiện thoát đệ quy là biến count <= 0
  if (count <= 0) {
    return;
  }

  // xử lý logic cơ bản
  console.log("Hello world!");

  // phần đệ quy: gọi lại chính hàm sayHello
  sayHello(count - 1);
}
8 như sau:

function power(a, b) {
  // điều kiện dừng đệ quy
  if (b === 0) {
    return 1;
  }

  // gọi lại chính nó
  return a * power(a, b - 1);
}

console.log(power(2, 0)); // 1
console.log(power(2, 1)); // 2
console.log(power(2, 2)); // 4
console.log(power(2, 3)); // 8

So sánh hàm đệ quy và vòng lặp

Bài toán tính lũy thừa trên có thể giải quyết bằng cách sử dụng vòng lặp:

function power(a, b) {
  let ret = 1;

  for (let i = 0; i < b; i++) {
    ret *= a;
  }

  return ret;
}

console.log(power(2, 0)); // 1
console.log(power(2, 1)); // 2
console.log(power(2, 2)); // 4
console.log(power(2, 3)); // 8

Đa số các bài toán có thể sử dụng hàm đệ quy thì đều có thể giải bằng cách sử dụng vòng lặp. Tùy thuộc vào yêu cầu của từng bài toán mà bạn lựa chọn cách làm phù hợp: