26. Hàm đệ qui

Giả sử ta có bài toán: Cộng 3 số 1,2,3. Ta sẽ giải bằng cách

1 + 2 = 3
3 + 3 = 6

Kết quả là 6.

Nếu cộng 4 số 1,2,3,4. Ta sẽ làm như sau

1 + 2 = 3
3 + 3 = 6
6 + 4 = 10

Kết quả là 10

Nếu cộng 5 số 1,2,3,4,5. Ta sẽ làm như sau

1 + 2 = 3
3 + 3 = 6
6 + 4 = 10
10 + 5 = 15

Kết quả là 15

Nếu là...100 số thì sao? Một công việc...đơn giản, nhưng vô cùng...mệt mỏi!
Quay lại với bài toán trên, giả sử cần tính tổng 3 số 1,2,3. Ta cần viết một hàm để làm công việc đó.

Đầu tiên, chúng ta cho tổng các số cần cộng, trong trường hợp này là 3, một ký tự đại diện ví dụ là k.
Tiếp theo, ta thấy rằng việc lấy tổng của hai số trước cộng với số tiếp theo cứ lặp đi lặp lại, vì vậy tạm cho nó một hàm làm công việc đó là sum(x) với x là một tham số nào đó.
Bắt đầu xét các phép cộng từ dưới lên, ta thử phác họa "hình hài" của hàm tính tổng 3 số 1,2,3 sum(k) như sau :

sum(k){
     k    + sum(x)  = 6
       
}

Coi lại phép toán ta sẽ thấy  kết quả bằng 6 sẽ có bằng cách lấy k=3 cộng với một hàm sum(x) tính tổng các số trước số 3. Rõ ràng về bản chất hàm sum(x) hoạt động giống như hàm sum(k-1) vì nó cũng cộng các số liền nhau chỉ trừ số k mà thôi. Vì vậy ta có thể viết lại

sum(k){
     k    + sum(k-1);
        
}

Giả sử với k=3, khi lời gọi hàm tới, đầu tiên kết quả sẽ là

3 + sum(2);

Tới lượt sum(2), kết quả sẽ là

sum(2) = 2 + sum(1);

Cuối cùng sum(1) sẽ cho kết quả là

sum(1) = 1 + sum(0) =1

Kết quả này trả ngược lại cho sum(2) = 2 + 1 =3, kết quả này tiếp tục trả ngược về cho lời gọi hàm đầu tiên và cho kết quả cuối cùng: 3 + sum(2) = 3 + 3 = 6

Tóm lại ta thấy tham số k bị trừ dần cho đến khi bằng 0, nói cách khác khi nào biến k còn lớn hơn 0 thì hàm sum(k) sẽ gọi chính nó với tham số nhỏ dần cho đến khi có kết quả.
Đây là hàm của chúng ta

int sum(int k) {
  if (k > 0) {
    return k + sum(k - 1);
  } else {
    return 0;
  }
}

Chúng ta sẽ tạo một chương trình hoàn chỉnh cho bài toán vô cùng đơn giản nhưng cũng vô cùng nhức đầu này. Đây là code:

#include <iostream>
using namespace std;
 
 int sum(int k) {
  if (k > 0) {
    return k + sum(k - 1);
  } else {
    return 0;
  }
}

int main() {
  int result = sum(3);
  cout << result;
  return 0;
}

Sử dụng IDE Online, chúng ta chạy thử chương trình

Hàm sum(in k) mà chúng ta vừa "vật vã" viết ở trên chính là một hàm đệ qui.

Khi gọi chạy chương trình sẽ qua những bước như sau

3 + sum(2)
3 + ( 2 + sum(1) )
3 + ( 2 + ( 1 + sum(0) ) )
3 + ( 2 + ( 1 + 0 ) )

 

Định Nghĩa Hàm Đệ Quy

Hàm đệ quy được định nghĩa là hàm gọi lại chính nó. Có rất nhiều thuật toán và cấu trúc dữ liệu dựa trên kỹ thuật đệ quy này : Quick sort, Merge sort, DFS, Cây Phân Đoạn...

Đây là một ví dụ khác rất đơn giản về hàm đệ qui

#include <iostream>
 
using namespace std;
 
static int count = 0;
 
void p() {
    count++;
    if (count <= 5) {
        cout << "Xin Chao " << count << endl;
        p();
    }
}
 
int main() {
    p();
    return 0;
}

Hàm p() là một hàm đệ qui. Mỗi khi hàm được gọi, biến count sẽ cộng thêm 1 cho đến khi bằng 5. Và mỗi lần như vậy sẽ in câu Xin Chao cùng với giá trị của biến count.

Bấm Run để chạy chương trình

Phần tiếp theo

Phần trước