Ninja IT

Hàm đệ quy

Hàm đệ quy

Hàm đệ quy là hàm gọi chính nó nhưng nhưng mỗi lần gọi lại là những tham số khác nhau. Hãy xem các ví dụ hàm tính giai thừa sau:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int factorial(int i) {
  if (n <= 1) {
    return 1;
  }
  return i * factorial(i - 1);
}

int main() {
  printf("%d", factorial(5)); // -> 5 * 4 * 3 * 2 * 1
}

Giải thích cách hoạt động của đệ quy

Khi hàm factorial(5) được gọi nó gọi hàm factorial(4). Và cứ tiếp tục như vậy đến khi factorial(2) gọi hàm factorial(1). Cuối cùng factorial(1) trả về 1 và không gọi hàm nào nữa. Và lúc đó hàm factorial(2) sẽ trả về 2 * 1, tiếp tục hàm factorial(3), factorial(4) và hàm factorial(5) sẽ trả về.

Chi tiết sẽ thực hiện như sau:

Hàm Gọi hàm Trả về Call stack
factorial(5) factorial(4) 5 * factorial(4) push
factorial(4) factorial(3) 4 * factorial(3) push
factorial(3) factorial(2) 3 * factorial(2) push
factorial(2) factorial(1) 2 * factorial(1) push
factorial(1) 1
factorial(2) 2 * 1 = 2 pop
factorial(3) 3 * 2 = 6 pop
factorial(4) 4 * 6 = 24 pop
factorial(5) 5 * 24 = 120 pop

Call Stack

Khi hàm factorial(5) gọi hàm factorial(4) thì hàm này sẽ lưu các biến của nó vào một stack được gọi là call stack. Tiếp tục với các hàm factorial(4), factorial(3), factorial(2), factorial(1). Khi hàm factorial(1) thực thi xong sẽ pop stack này ra.

Tiếp tục tới hàm factorial(2), factorial(3), factorial(4), factorial(5) thực thi sẽ pop stack ra theo thứ tự.

Lưu ý khi gọi đệ quy

  • Khi gọi đệ quy với số lớn thì lúc đó call stack cũng lên lớn tương ứng. Nếu call stack vượt quá một mốc nào đó thì sẽ bị lỗi.
  • Luôn luôn có điều kiện dừng, ở ví dụ trên là trường hợp n bằng 1. Nếu không có điểm dừng thì hàm đệ quy sẽ chạy vô tận. Lúc đó call stack quá lớn và cũng sẽ bị lỗi.

Có thể sử dụng hàm dưới đây để tính giai thừa mà không sử dụng đệ quy như sau:

1
2
3
4
5
6
7

int factorial(int n) {
  int fac = 1;
  for (int i = 2; i <= n; i++) {
    fac *= i;
  }
  return fac;
}

Chương trình không sử dụng đệ quy này có thể chạy với số lớn mà không sợ call stack bị đầy. Đồng thời cũng không mất thời gian push, pop stack nên chương trình sẽ chạy nhanh hơn. Nên nếu khi nào có thể, hãy khử chương trình có hàm đệ quy thành hàm không đệ quy.