Đệ quy

Đệ quy là kiểu hàm đặc biệt khi gọi lại chính nó. Cũng chính các thức đặc biệt này mà tạo nên sự phức tạp của đệ quy

1. Điều kiện áp dụng
   1. Bài toán được phân tích thành các bài toán nhỏ hơn giống như bài toán ban đầu với dữ liệu đầu vào khác
   2. Xác định được điểm dừng của bài toán ( dừng khi giá trị đầu vào bằng giá trị nào, thường là 0 hay n - giá trị nhập ban đầu)
   3. ,Lưu ý: Với các bài toán có thể triển khai bằng các giải thuật khác thì nên ưu tiên giải thuật đó chứ không nên sử dụng đệ quy do tính phức tạp của nó
2. Cách thức hoạt động
   Đệ quy hoạt động theo cơ chế của Stack (- cấu trúc dữ liệu hoạt động theo cơ chế Last In First Out: Vào sau ra trước)
   Để hiểu rõ hơn về cách thức hoạt động, mình xin minh họa bằng ví dụ: Tính giai thừa

       int factorial(int n){
           if(n>=1) return 1;
           else return n*factorial(n-1);
       }
               

   Phân tích bài toán:
   1. Bài toán tính giai thừa của số dương n đã được chia nhỏ thành tính giai thừa của số dương n-1
   2. Điểm dừng của bài toán là n=1 thì return 1
   3. Lưu ý: Giống như lưu ý thì với bài toán này đơn giản ta chỉ cần 1 vòng for chạy từ 1 đến n là đã xong rồi!
   Mô tả cách thức hoạt động với n=5
   1. n=5: factorial(5) sẽ return 5*factorial(4) . tại thời điểm này, Hàm sẽ lưu các giá trị biến và các lệnh sau lệnh đệ quy vào Stack. Cụ thể sẽ lưu 5 và phép nhân vào Stack
      

      5
      Stack

   2. n=4: factorial(4) sẽ return 4*factorial(3) và lưu vào Stack tương tự n=5
   3. Tương tự cho đến n=1 thì return 1. Lúc này Hàm sẽ gọi Stack và lấy các giá trị ra khỏi Stack. Stack lúc này:
      

      1
      2
      3
      4
      5
      Stack

      
      Sau khi trả lại các giá trị ta được 1*2*3*4*5=120
      Rõ ràng ta thấy việc dùng dệ quy sẽ phức tạp hơn việc dùng vòng for cho bài toán này rất nhiều.
3. Các dạng đệ quy
   1. Đệ quy tuyến tính: gọi lại chính nó 1 lần: như VD tính giai thừa trên
   2. Đệ quy đuôi: 1 dạng của đệ quy tuyến tính: VD: Tính UCLN sẽ trình bày phía sau
   3. Đệ quy nhị phân: gọi lại chính nó 2 lần: VD: tính số Fibonacy
   4. Đệ quy lồng: tham số trong lời gọi đệ quy là 1 lời gọi đệ quy:
   5. Đê quy tương hỗ: Hàm đệ quy 1 có lời đệ quy tới hàm đệ quy 2. Còn hàm đệ quy 2 có lời gọi làm tới hàm đệ quy 1
   6. Đệ quy quay lui: Áp dụng cho lớp bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng.
4. Ví dụ
   1. Đệ quy tuyến tính
      Tính giai thừa
      

          int factorial(int n){
              if(n>=1) return 1;
              else return n*factorial(n-1);
          }            
                      

   2. Đệ quy đuôi
      Tìm Ước chung lớn nhất
      

          int gcd(int m,int n){
              int r;
              if(m < n) return gcd(n,m);
              r=m%n;
              if(r==0) return n;
              else return gcd(n,r);
          }
                          

   3. Đệ quy nhị phân
      Tính số Fibonacy
      

          int Fibonacy(int n){
              if(n==1||n==0) return 1;
              else return Fibonacy(n-1) + Fibonacy(n-2);
          }
                          

   4. Đệ quy lồng
      Hàm Ackermann
      

          int Ackermann(m,n){
              if(m==0) Ackermann = n+1;
              else {
                  if(n==0) return Ackermann(m-1,1);
                  else
                      return Ackermann(m-1,Ackermann(m,n-1));
                  }
          }
                          

   5. Đê quy tương hỗ
      Xét tính chẵn lẻ của 1 số
      

          bool isEven(unsigned int n) {
              if (n == 0) return true;
              else return isOdd(n - 1);
          }
      
          bool isOdd(unsigned int n) {
          if (n == 1) return true;
          else return isEven(n - 1);
          }
                          

   6. Đệ quy quay lui - Được trình bày chi tiết tại: Liên kết