Ý tưởng của đệ quy:

Đôi khi một bài toán lớn nếu bạn cứ để nguyên như vậy mà giải thì sẽ rất là khó, nếu chúng ta có thể đưa nó trở về những mảnh bài toán con nhỏ hơn mà vẫn giữ nguyên được bản chất ban đầu của nó thì thật là tuyệt vời.

Từ việc giải quyết bài toán con dễ nhất, sử dụng kết quả của bài toán con dễ nhất để chuyển sang giải quyết bài toán con dễ nhì, rồi sử dụng tiếp kết quả sang bài toán dễ thứ ba, cứ như vậy cho đến khi bạn giải quyết cả một bài toán lớn (bài toán ở tầng cao nhất và khó nhất).

Minh họa ý tưởng đệ quy:

Giả sử bạn có tòa nhà 5 tầng, bạn biết rằng tầng đầu tiên (tầng 1) cao 5 mét và mỗi tầng cao bằng nhau, vậy để tính tổng chiều cao của tòa nhà này bạn phải làm thế nào? (tất nhiên ví dụ này quá đơn giản không thể thấy được sức mạnh của đệ quy nhưng đã là dân học lớp 13 trở lên hết rồi, hãy làm vấn đề trở nên phức tạp hơn một chút nào :D)

Rõ ràng ta có thể thấy rằng chiều cao của tòa nhà = tổng chiều cao của 5 tầng, cũng là chiều cao khi bạn ở tầng thứ 5 đúng không nào, do đó, ta có thể viết lại:

• Chiều cao ở tầng thứ 5 = chiều cao của chính nó + chiều cao của 4 tầng bên dưới.
• Chiều cao ở tầng thứ 4 = chiều cao của chính nó + chiều cao của 3 tầng bên dưới.
• Chiều cao ở tầng thứ 3 = chiều cao của chính nó + chiều cao của 2 tầng bên dưới.
• Chiều cao ở tầng thứ 2 = chiều cao của chính nó + chiều cao của 1 tầng bên dưới (tức tầng 1).
• Chiều cao của tầng 1 đã biết là bằng 5 mét.

Khi trở về tầng 1, ta đã có được thông tin tầng 1 cao 5 mét, bây giờ cầm thông tin này quay ngược lại giải quyết bài toán như sau:

• Chiều cao ở tầng 1 = 5 mét.
• Chiều cao ở tầng 2 = chiều cao chính nó (5 mét) + chiều cao tầng 1 (5 mét) = 10 mét.
• Chiều cao ở tầng 3 = chiều cao của chính nó (5 mét) + chiều cao ở tầng 2 (10 mét) = 15 mét.
• Chiều cao ở tầng 4 = chiều cao của chính nó (5 mét) + chiều cao ở tầng 3 (15 mét) = 20 mét.
• Chiều cao ở tầng 5 = chiều cao của chính nó (5 mét) + chiều cao ở tầng 4 (20 mét) = 25 mét.

Minh họa bài toán trên bằng mã nguồn C++ sử dụng đệ quy:

#include <iostream>
using namespace std;

int tongChieuCaoToaNha(int Tang){ // Tang: tầng

    if (Tang == 1)// Nếu là tầng 1 thì đã biết nó cao 5 mét
        return 5;

    return 5 + tongChieuCaoToaNha(Tang - 1); // Nếu là tầng n trở lên thì chiều cao ở tầng n
                                                                   // bằng chiều cao của chính nó (5 mét) + chiều cao
                                                                   // của (n - 1) tầng còn lại.
}

int main(){

    int soTang = 5; // Tòa nhà 5 tầng
    int tongChieuCao = tongChieuCaoToaNha(5);
    cout <<"Tong chieu cao cua toa nha " << soTang << " tang = " <<  tongChieuCao << endl;
    // Kết quả là: 25
}

Lưu ý nhỏ khi bạn lập trình sử dụng kĩ thuật đệ quy:

Như mình đã nói lúc đầu, muốn bài toán mà giữ nguyên được bản chất ban đầu khi đưa về dạng đơn giản hơn thì chỉ có một cách đó là bài toán đó phải có dạng đệ quy, cho nên muốn áp dụng kĩ thuật đệ quy trong lập trình bạn phải xét xem bài toán đó có dạng đệ quy hay không?

Thứ hai, bạn phải tự hỏi có cần thiết phải sử dụng kĩ thuật đệ quy cho vấn đề đó hay không? Bởi vì khi áp dụng kĩ thuật đệ quy, máy tính phải lưu vết lại quá trình tìm về bài toán con dễ nhất (ở ví dụ minh họa trên mình đã thực hiện rất nhiều bước), cho nên rất tốn bộ nhớ, đối với những bài toán phức tạp, có thể gây tràn bộ nhớ RAM nếu bạn kiểm soát không hiệu quả.