Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 7: Tìm giai thừa bằng đệ qui - Đào Nam Anh

pdf 21 trang ngocly 2770
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 7: Tìm giai thừa bằng đệ qui - Đào Nam Anh", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_bai_7_tim_giai_thua.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 7: Tìm giai thừa bằng đệ qui - Đào Nam Anh

  1. DATA STRUCTURE AND ALGORITHM Recursive Factorial CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Tìm giai thừa bằng đệ qui Dr. Dao Nam Anh Data Structure and Algorithm 1
  2. Resource - Reference Slides adapted from Robert Sedgewick, and Kevin Wayne, edit by Dao Nam Anh. Major Reference: • Robert Sedgewick, and Kevin Wayne, “Algorithms” Princeton University, 2011, Addison Wesley • Algorithm in C (Parts 1-5 Bundle)- Third Edition by Robert Sedgewick, Addison-Wesley • Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường. • Giải thuật và lập trình, Lê Minh Hoàng, Đại Học Sư Phạm, 2002 Data Structure and Algorithm 2
  3. Recursive Factorial Tính giai thừa, dùng đệ qui pubic class Factorial { public static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } public static void main(String[] args) { System.out.println(fact(3)); } } Data Structure and Algorithm 3
  4. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Data Structure and Algorithm 4
  5. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Data Structure and Algorithm 5
  6. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Data Structure and Algorithm 6
  7. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 2 fact(2) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Data Structure and Algorithm 7
  8. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 2 fact(2) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Data Structure and Algorithm 8
  9. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 2 fact(2) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Data Structure and Algorithm 9
  10. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 2 fact(2) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 1 fact(1) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Data Structure and Algorithm 10
  11. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 2 fact(2) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 1 fact(1) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Data Structure and Algorithm 11
  12. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 2 fact(2) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 1 fact(1) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Data Structure and Algorithm 12
  13. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 2 fact(2) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 1 fact(1) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 0 fact(0) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Data Structure and Algorithm 13
  14. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 2 fact(2) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 1 fact(1) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 0 fact(0) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Data Structure and Algorithm 14
  15. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 2 fact(2) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 1 fact(1) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 0 1 fact(0) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Data Structure and Algorithm 15
  16. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 2 fact(2) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 1 fact(1) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } 1 1 Data Structure and Algorithm 16
  17. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 2 fact(2) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } 1 n = 1 fact(1) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } 1 1 Data Structure and Algorithm 17
  18. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 2 fact(2) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } 2 1 Data Structure and Algorithm 18
  19. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } n = 2 2 fact(2) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } 2 1 Data Structure and Algorithm 19
  20. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } 3 2 Data Structure and Algorithm 20
  21. n = 3 fact(3) environment static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } 3 2 public class Factorial { public static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } public static void main(String[] args) { System.out.println(fact(3)); } 6 % java Factorial } 6 Data Structure and Algorithm 21