1 of 35

Hàm đệ quy

Lập trình nâng cao

2 of 35

Hàm đệ quy

Hàm gọi chính nó

2

long factorial(long x) {

if (x > 1)

return (x * factorial(x-1));

else

return 1;

}

int main() {

long number = 9;

cout << number << "! = " << factorial(number);

return 0;

}

N! = N * (N-1)!

3 of 35

Hàm đệ quy

Trường hợp cơ bản: a<=1: f(x) = 1
Trường hợp thường: a>1�Công thức đệ quy: f(x) = x * f(x-1)

3

long factorial(long x) {

if (x > 1)

return (x * factorial(x-1));

else

return 1;

}

4 of 35

Hàm đệ quy

Đưa f(x) về f(x-1)
Đưa f(x-1) về f(x-2)
…
Hội tụ về một trong các trường hợp cơ bản

4

long factorial(long x) {

if (x > 1)

return (x * factorial(x-1));

else

return 1;

}

5 of 35

5

long factorial(long x) {

if (x > 1)

return (x * factorial(x-1));

else

return 1;

}

int main() {

long res = factorial(4);

return 0;

}

Đỉnh stack

main()

6 of 35

6

long factorial(long x) {

if (x > 1)

return (x * factorial(x-1));

else

return 1;

}

int main() {

long res = factorial(4);

return 0;

}

Đáy stack

Đỉnh stack

main()

factorial(4)

x = 4

7 of 35

7

long factorial(long x) {

if (x > 1)

return (x * factorial(x-1));

else

return 1;

}

int main() {

long res = factorial(4);

return 0;

}

Đáy stack

Đỉnh stack

main()

factorial(4)

x = 4

factorial(3)

x = 3

8 of 35

8

long factorial(long x) {

if (x > 1)

return (x * factorial(x-1));

else

return 1;

}

int main() {

long res = factorial(4);

return 0;

}

Đáy stack

Đỉnh stack

main()

factorial(4)

x = 4

factorial(3)

x = 3

factorial(2)

x = 2

9 of 35

9

long factorial(long x) {

if (x > 1)

return (x * factorial(x-1));

else

return 1;

}

int main() {

long res = factorial(4);

return 0;

}

Đáy stack

Đỉnh stack

main()

factorial(4)

x = 4

factorial(3)

x = 3

factorial(2)

x = 2

factorial(1)

x = 1

10 of 35

10

long factorial(long x) {

if (x > 1)

return (x * factorial(x-1));

else

return 1;

}

int main() {

long res = factorial(4);

return 0;

}

Đáy stack

Đỉnh stack

Return 1

main()

factorial(4)

x = 4

factorial(3)

x = 3

factorial(2)

x = 2

11 of 35

11

long factorial(long x) {

if (x > 1)

return (x * factorial(x-1));

else

return 1;

}

int main() {

long res = factorial(4);

return 0;

}

Đáy stack

Đỉnh stack

main()

factorial(4)

x = 4

factorial(3)

x = 3

Return 2

12 of 35

12

long factorial(long x) {

if (x > 1)

return (x * factorial(x-1));

else

return 1;

}

int main() {

long res = factorial(4);

return 0;

}

Đáy stack

Đỉnh stack

main()

factorial(4)

x = 4

Return 6

13 of 35

13

long factorial(long x) {

if (x > 1)

return (x * factorial(x-1));

else

return 1;

}

int main() {

long res = factorial(4);

return 0;

}

Đỉnh stack

main()

res = 24

Return 24

14 of 35

Tìm kiếm nhị phân đệ quy

14

15 of 35

Tìm kiếm nhị phân đệ quy

Tìm từ 0 đến 8
Tìm từ 5 đến 8
Tìm từ 5 đến 6
Tìm từ 5 đến 5

15

16 of 35

Tìm kiếm nhị phân đệ quy

Tìm từ 0 đến 8
Do a[4]< 44 nên tìm từ 5 đến 8
Do a[7]>44 nên tìm từ 5 đến 6
Do a[6]>44 nên tìm từ 5 đến 5
Trường hợp cơ bản: a[5] = 44

16

17 of 35

Tìm kiếm nhị phân đệ quy

Công thức đệ quy:

if a[mid] < key : search(mid+1, high)
if a[mid] > key : search(low, mid-1)

Trường hợp cơ bản #1:

a[mid] == key: tìm thấy

Trường hợp cơ bản #2:

low>high: không tìm thấy

17

18 of 35

Tìm kiếm nhị phân đệ quy

Công thức đệ quy:

if a[mid] < key : search(mid+1, high)
if a[mid] > key : search(low, mid-1)

Trường hợp cơ bản #1: a[mid] == key: tìm thấy
Trường hợp cơ bản #2: low>high: không tìm thấy

18

int search(int key, int a[], int low, int high) {

if (low > high) return -1;

int mid = (low + high) / 2;

if (a[mid] == key) return mid;

if (a[mid] > key)

return search(key, a, low, mid-1);

return search(key, a, mid+1, high);

}

19 of 35

Đọc thêm

http://www.drdobbs.com/security/anatomy-of-a-stack-smashing-attack-and-h/240001832

19

20 of 35

Công thức đệ quy

factorial(n) = factorial(n-1) * n
f(n): số bước chuyển n đĩa từ cọc này -> cọc khác sao cho không bao giờ đặt một đĩa lên trên đĩa nhỏ hơn

20

21 of 35

factorial(n) = factorial(n-1) * n

Tháp Hà Nội

21

22 of 35

factorial(n) = factorial(n-1) * n

Tháp Hà Nội move(n, 1, 3)

22

23 of 35

factorial(n) = factorial(n-1) * n

Tháp Hà Nội f(n) = f(n-1) …..

move(n-1, 1, 2)

23

24 of 35

factorial(n) = factorial(n-1) * n

Tháp Hà Nội f(n) = f(n-1) + 1 …..

Output(move n from 1 to 3)

24

25 of 35

factorial(n) = factorial(n-1) * n

Tháp Hà Nội f(n) = f(n-1) + 1 + f(n-1)

move(n-1, 2, 3)

25

26 of 35

Thuật toán chuyển n đĩa

Chuyển n-1 đĩa từ cọc nguồn tới cọc trung gian
Chuyển đĩa số n từ cọc nguồn đến cọc đích
Chuyển n-1 đĩa từ cọc trung gian tới cọc đích

26

27 of 35

Thuật toán chuyển n đĩa

Chuyển n-1 đĩa từ cọc nguồn tới cọc trung gian
Chuyển đĩa số n từ cọc nguồn đến cọc đích
Chuyển n-1 đĩa từ cọc trung gian tới cọc đích

27

28 of 35

Thuật toán chuyển n đĩa

Chuyển n-1 đĩa từ cọc nguồn tới cọc trung gian
Chuyển đĩa số n từ cọc nguồn đến cọc đích
Chuyển n-1 đĩa từ cọc trung gian tới cọc đích

28

29 of 35

Thuật toán chuyển n đĩa

Chuyển n-1 đĩa từ cọc nguồn tới cọc trung gian
Chuyển đĩa số n từ cọc nguồn đến cọc đích
Chuyển n-1 đĩa từ cọc trung gian tới cọc đích

29

move(n, source, dest):

move(n-1, source, temp)

output(“move disc n from source to dest”);

move(n-1, temp, dest)

30 of 35

void move(int n, int source, int dest) {

temp = other(source, dest);

move(n - 1, source, temp);

output(“ move disc n from ‘source’ to ‘dest’ ”);

move(n - 1, temp, dest);

}

30

move(n, source, dest):

move(n-1, source, temp)

output(“move disc n from source to dest”);

move(n-1, temp, dest)

31 of 35

Thuật toán hoàn chỉnh

void move(int n, int source, int dest)

{

if (n < 1) return; // basic case

temp = other(source, dest);

move(n - 1, source, temp);

output(“ move disc n from ‘source’ to ‘dest’ ”);

move(n - 1, temp, dest);

}

31

32 of 35

Duyệt hoán vị

32

Duyệt hoán vị (abc)

tách a

tách b

tách c

Duyệt (bc)

Duyệt (ac)

Duyệt (ab)

tách b

tách c

Duyệt (c)

Duyệt (b)

Tìm được hoán vị abc

Tìm được hoán vị acb

…

33 of 35

Duyệt hoán vị

P(abcdef) danh sách tất cả các hoán vị của abcdef

P(abcdef) = a + P(bcdef)

b + P(acdef)

…..

permutation(s[], lo, hi): liệt kê tất cả hoán vị

if (lo == hi) { output(s) ; return;}

for i: lo-> hi {

swap(s, lo, i); // tách lấy phần tử đứng đầu

permutation(s, lo+1, hi) // đệ quy phần còn lại

swap(s, lo, i); // quay lui về như cũ để thử cách khác

}

33

34 of 35

Duyệt tổ hợp

Liệt kê các tập con của [a,b,c]

Có a: abc, ab, ac, a
Không có a: bc, b, c, []

C(N) là tập của các tập con của [1…N]

Thì

C(N) = C(N-1) + ([N] + s), với mọi s thuộc C(N-1)

34

35 of 35

Duyệt tổ hợp

C(N) = C(N-1) + ([N] + s), với mọi s thuộc C(N-1)

Combination(“abc”, 3) -> in ra 8 kết quả

void combination(k) {

if (k<1) {

output(); return;

}

member[k] = true;

combination(k-1);

member[k] = false;

combination(k-1);

}

35