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

1

Data Structure and Algorithm

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

2

Data Structure and Algorithm

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));

}

3

}

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

4

}

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

5

}

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

6

}

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 2 fact(2)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

7

}

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 2 fact(2)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

8

}

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 2 fact(2)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

9

}

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 2 fact(2)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 1 fact(1)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

10

}

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 2 fact(2)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 1 fact(1)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

11

}

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 2 fact(2)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 1 fact(1)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

12

}

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 2 fact(2)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 1 fact(1)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 0 fact(0)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

13

}

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 2 fact(2)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 1 fact(1)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 0 fact(0)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

14

}

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 2 fact(2)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 1 fact(1)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

1

environment

} n = 0 fact(0)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

15

}

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 2 fact(2)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 1 fact(1)

1

16

} static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); 1

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 2 fact(2)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

1

environment

} n = 1 fact(1)

1

17

} static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); 1

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

environment

} n = 2 fact(2)

1

18

} static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); 2

Data Structure and Algorithm

environment

n = 3 fact(3)

static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1);

2

environment

} n = 2 fact(2)

1

19

} static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); 2

Data Structure and Algorithm

environment

n = 3 fact(3)

2

20

} static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); 3

Data Structure and Algorithm

environment

n = 3 fact(3)

2

} static int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); 3

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 }

21

6 }

Data Structure and Algorithm