Đệ quy (recursion) là quá trình lặp lại các mục (item) theo cách tương tự của chính nó. Trong ngôn ngữ lập trình, nếu một chương trình cho phép bạn gọi một hàm bên trong chính hàm đó, thì nó được gọi là lệnh gọi đệ quy của hàm.

void recursion() {
   recursion(); /* function calls itself */
}

int main() {
   recursion();
}

Ngôn ngữ lập trình C có hỗ trợ đệ quy, tức là, một hàm để gọi chính nó. Nhưng trong khi sử dụng đệ quy, người lập trình cần phải cẩn thận định nghĩa một điều kiện thoát (exit condition) khỏi hàm, nếu không nó sẽ đi vào một vòng lặp vô hạn.

Các hàm đệ quy rất hữu ích để giải quyết nhiều vấn đề toán học, chẳng hạn như tính giai thừa của một số, tạo chuỗi Fibonacci, v.v.

Tính Giai Thừa Số (Number Factorial)

Trước tiên, hãy xem ví dụ sau đây về phép tính giai thừa của một số nhất định bằng cách sử dụng một hàm đệ quy:

#include <stdio.h>

unsigned long long int factorial(unsigned int i) {
   if(i <= 1) {
      return 1;
   }
   return i * factorial(i - 1);
}

int  main() {
   int i = 12;
   printf("Factorial of %d is %d\n", i, factorial(i));
   return 0;
}

Khi đoạn code trên được biên dịch và thực thi, nó sẽ cho kết quả như sau.

Factorial of 12 is 479001600

Dãy Fibonacci (Fibonacci Series)

Tiếp theo, ví dụ sau tạo chuỗi Fibonacci cho một số nhất định bằng cách sử dụng một hàm đệ quy:

#include <stdio.h>

int fibonacci(int i) {

   if(i == 0) {
      return 0;
   }

   if(i == 1) {
      return 1;
   }
   return fibonacci(i-1) + fibonacci(i-2);
}

int  main() {

   int i;

   for (i = 0; i < 10; i++) {
      printf("%d\t\n", fibonacci(i));
   }

   return 0;
}

Khi đoạn code trên được biên dịch và thực thi, nó sẽ cho kết quả như sau.

0	
1	
1	
2	
3	
5	
8	
13	
21	
34

Xem thêm Recursion (computer science) của Wikipedia.

(Tiếp theo)