Đệ quy

Một hàm gọi chính nó được gọi là đệ qui. Đệ qui là một kỹ thuật lập trình tổng quát có thể ứng dụng cho các bài toán mà có thể định nghĩa theo thuật ngữ của chính chúng. Chắng hạn bài toán giai thừa được định nghĩa như sau:

• Giai thừa của 0 là 1.
• Giai thừa của một số « là n lần giai thừa của 77-1.

Hàng thứ hai rõ ràng cho biết giai thừa được định nghĩa theo thuật ngữ của chính nó và vì thế có thế được biểu diễn như một hàm đệ qui:

int Factorial (unsigned int n)

{

return n = 0 ? 1 : n * Factorial(n-1);

}

Một hàm đệ qui phải có ít nhất một điều kiện dừng có thể được thỏa. Ngược lại, hàm sẽ gọi chính nó vô hạn định cho tới khi tràn stack. Ví dụ hàm Factorial có điều kiện dừng là n = 0. (Chú ý đối với trường hợp n là số âm thì điều kiện sẽ không bao giờ thỏa và Factorial sẽ thất bại).