Bài toán

Viết chương trình tính tổng từ 0 đến một số nguyên bất kỳ, mỗi số cách nhau một 1 đơn vị, xuất kết quả tính tổng ra màn hình. Ví dụ, nếu số nguyên bất kỳ bằng 8, thì tổng cần tính là: 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8

Các em có thể viết thực hiện bài toán bằng vòng lặp for hoặc vòng lặp while mà chúng ta đã học ở những bài trước như sau:

int main() {
  int tong = 0;
  for (int i = 0; i <= 8; i++) {
    tong = tong + i;
  }
  count << tong;
  return 0;
}

Bài toán cũng có thể thực hiện bằng đệ quy như sau

#include <iostream>
using namespace std;

int tinhTong(int x) {
  if (x > 0) {
    return x + tinhTong(x - 1);
  } 
  else {
    return 0;
  }
}

int main() {
  int ketQua = tinhTong(8);
  cout << ketQua;
  return 0;
}

Ở dòng 6, các em có thể thấy bên trong hàm tinhTong, tự gọi chính nó, các bước chạy lần lượt như sau:

Tại dòng 14, hàm tinhTong được gọi, tham số x = 8, thực hiện tinhTong

  1. 8 + tinhTong(8 - 1)
    x lúc này là 8 - 1 = 7
  2. 8 + 7 + tinhTong(7 - 1)
    x lúc này là 7 - 1 = 6
  3. 8 + 7 + 6 + tinhTong(6 - 1)
    x lúc này là 6 - 1 = 5
  4. 8 + 7 + 6 + 5 + tinhTong(5 - 1)
    x lúc này là 5 - 1 = 4
  5. 8 + 7 + 6 + 5 + 4 + tinhTong(4 - 1)
    x lúc này là 4 - 1 = 3
  6. 8 + 7 + 6 + 5 + 4 + 3 + tinhTong(3 - 1)
    x lúc này là 3 - 1 = 2
  7. 8 + 7 + 6 + 5 + 4 + 3 + 2 + tinhTong(2 - 1)
    x lúc này là 2 - 1 = 1
  8. 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + tinhTong(1 - 1)
    x lúc này là 1 - 1 = 0

Tại bước 8 thì x = 0, nên hàm tinhTong dừng thực thi, biến ketQua = 36

Người lập trình cần cẩn thận với đệ quy vì nếu không khéo thì hàm đệ quy sẽ thực thi không bao giờ kết thúc hoặc chiếm quá nhiều tài nguyên hệ thống (RAM, CPU). Tuy nhiên, khi được viết chính xác thì đệ quy có thể là một cách tiếp cận lập trình rất hiệu quả và thanh lịch về mặt toán học.

Đệ quy được ứng dụng rất nhiều trong thực tế đặc biệt là các trò chơi điện tử, Sudoku là một điển hình.

Mấu chốt của đệ quy là các em cần xác định được điều kiện dừng, như trong ví dụ trên là x <= 0