Đệ quy

Việc gọi cùng một hàm từ các câu lệnh bên trong hàm là được phép. Những lời gọi như vậy được gọi là đệ quy.

Hãy quay lại ví dụ về tính toán các số Fibonacci. Theo công thức tính mỗi số là tổng của hai số trước đó (trừ hai số đầu tiên, đều bằng 1), dễ dàng viết một hàm đệ quy để tính các số Fibonacci.

int Fibo(const int n)
{
   if(n <= 1) return 1;
   
   return Fibo(n - 1) + Fibo(n - 2);
}

Một hàm đệ quy phải có khả năng trả lại quyền điều khiển mà không cần đệ quy, như trong trường hợp của chúng ta bên trong câu lệnh điều kiện if cho các chỉ số 0 và 1. Nếu không, chuỗi các lời gọi hàm có thể tiếp tục vô hạn. Trong thực tế, vì các lời gọi hàm chưa hoàn thành tích lũy trong một vùng bộ nhớ giới hạn gọi là ngăn xếp (xem phần Câu lệnh khai báo/định nghĩa và thanh bên "Heap" và "Stack" trong phần Mô tả mảng), sớm hay muộn hàm sẽ kết thúc với lỗi thời gian chạy "Stack overflow" (tràn ngăn xếp). Vấn đề này được thể hiện trong hàm FiboEndless.

int FiboEndless(const int n)
{
   return FiboEndless(n - 1) + FiboEndless(n - 2);
}

Lưu ý rằng đây không phải là lỗi biên dịch. Trong trường hợp như vậy, trình biên dịch thậm chí sẽ không tạo ra cảnh báo (mặc dù về mặt kỹ thuật nó có thể). Lỗi xảy ra trong quá trình thực thi script. Nó sẽ được in vào nhật ký Experts trong terminal.

Đệ quy không chỉ xảy ra khi một hàm được gọi từ chính nó. Ví dụ, nếu hàm F gọi hàm G, mà hàm G lại gọi hàm F, thì trường hợp này là đệ quy gián tiếp. Do đó, đệ quy có thể xảy ra do các lời gọi vòng tròn ở bất kỳ độ sâu nào.