Recursion (đệ quy) hiểu đơn giản là một phương pháp quy nạp toán học, sử dụng hình thức gọi là chính bản thân nó (calling itself).

Một thuật toán đệ quy bao gồm 2 phần:

• Base condition (Anchor): đây được xem là điểm neo, đánh giá bài toán nhỏ nhất của bài toán đệ quy đó.
• Recursive formula (main): đây là phần thử hiện sự đệ quy.

Các loại đệ quy thường gặp

Tail Recursion

Chỉ có một lần gọi đệ quy ở cuối chương trình.

class Main 
  {static void tail(int n)
     {if(n >0)
        { System.out.print(n + "  ");	
           **tail(n-1); // recursion here**
        }
     } 
   public static void main(String [] args)
     {tail(10);
      System.out.println();
     }
  }

Non-tail Recursion

Đệ quy có thể được gọi ở bất cứ đâu trong chương trình

public class Main
 {public static void reverse() throws Exception
   {char ch = (char) System.in.read();
    if(ch != '\\n') 
     {reverse(); **// recursion here**
      System.out.print(ch);
     }
   }
  public static void main(String [] args) throws Exception
   {System.out.println("\\nEnter a string to be reversed:");
    reverse(); **// recursion here**
    System.out.println("\\n");
   }
 }

Indirect recursion

Giả sử có 2 hàm f(x) và g(x), nếu f(x) gọi g(x) và g(x) gọi lại f(x), chúng ta gọi đó là indirection recursion (đệ quy gián tiếp)

Nested recursion

Một hàm không chỉ định nghĩa bản thân nó mà còn có thể sử dụng chính nó để làm parameter.

Excessive recursion

Loại đệ quy này thể hiện sự không hiệu quả của thuật toán.