Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 3: Đệ quy (Recursion)

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:39

Thêm vào BST

Báo xấu

45
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 3: Đệ quy (Recursion)" cung cấp những kiến thức về khái niệm về đệ quỵ; ví dụ về đệ quỵ; đệ quy đuôi; bài toán tháp Hanoi. Mời các bạn cùng tham khảo bài giảng để phục vụ cho học tập và nghiên cứu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 3: Đệ quy (Recursion)

Cấu trúc dữ liệu và giải thuật Bài 3. Đệ quy (Recursion) Lecturer: PhD. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com 1 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
Bài 3. Đệ quy Nội dung:  Khái niệm về đệ quy.  Ví dụ về đệ quy.  Đệ quy đuôi (Tail Recursion)  Bài toán tháp Hanoi. Tham khảo: 1. Kyle Loudon – Mastering Algorithms with C Chapter 3 – Recursion 2. Hanoi Tower (Web page) 2 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
3.1. Khái niệm về đệ quy (1/6)  Với phần lập trình viên, để giải quyết bài toán lớn, có thể sử dụng 1 quá trình dạng đệ quy.  Ta nói m ột đối tượng là đệ qui nếu đối tượng này bao gồm chính nó như một bộ phận hoặc đối tượng được định nghĩa dưới dạng của chính nó. 3 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
3.1. Khái niệm về đệ quy (2/6)  Nguyên lý đệ quy cho phép hình thành bài toán từ chính nó.  Trong tính toán, để giải quyết vấn đề sử dụng hàm đệ quy (hàm gọi chính nó với tham số thay đổi).  Như vậy, hàm đệ quy là hàm gọi lại chính nó.  Với mỗi bước, hàm thay đổi thông tin đầu vào và cho kết quả ngày càng gần với mục tiêu của bài toán. 4 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
3.1. Khái niệm về đệ quy (3/6) • Giả sử cần tính giai thừa của một số nguyên dương n. • Giai thừa của n được viết: n!, tích các phần tử từ n đến 1. • Ví dụ, 5! = (5)(4)(3)(2)(1). • Có thể thực hiện tính giai thừa bằng vòng lặp thông thường để tính tích. • Một cách tiếp cận khác, sử dụng đệ quy, khi đó công thức tính giai thừa được viết dạng: n! = (n)(n - 1)(n - 2) . . . (1) 5 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
3.1. Khái niệm về đệ quy (4/6) • Có thể định nghĩa n! theo cách khác, là tích của n và giai thừa nhỏ hơn. • Như vậy, ta có n! = n * (n – 1)!. • Ta x ử lý (n - 1)! giống như n!, với tham số nhỏ hơn. • Ta có, (n - 1)! = (n – 1) * (n - 2)!, • Tương tự, (n - 2)! = (n – 2) * (n - 3)!, quá trình trên kết thúc khi n=1. • Với cách tiếp cận dạng đệ quy, có thể định nghĩa lại cách tính giai thừa dạng: n! = iif(n=0, 1, n * (n-1)!) 6 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
3.1. Khái niệm về đệ quy (5/6)  Có thể hình dung đệ quy qua 2 bước chính: quay xuôi (winding) và quay ngược (unwinding). ⁪ Tại bước winding, lời giải bài toán gọi lại chính nó.  Với bước winding, lời gọi chính nó dừng khi thỏa mãn điều kiện dừng.  Điều kiện dừng thông thường được định nghĩa là tại bước đó đã đến bài toán cơ sở, có thể giải trực tiếp được.  Với mỗi hàm đệ quy cần có ít nhất một điều kiện dừng, nếu không sẽ lặp vô hạn. 7 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
3.1. Khái niệm về đệ quy (6/6)  Khi bước winding kết thúc, bước unwinding sẽ được thực hiện, các bài toán nhỏ trên được xem xét theo thứ tự ngược lại.  Bước này dừng lại khi quá trình đến bài toán gốc. Quá trình đệ quy kết thúc. 8 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
3.2. Ví dụ về đệ quy (1/6) Ví dụ 1: Tính n!. F(n) = n* F(n-1) nếu n > 1 F(n) = 1 nếu n = 1 hoặc n = 0 Tính F(4) = ? Bước Winding Bước UnWinding F(4) = 4 * F(3) F(4) = 4 * 6 = 24 F(3) = 3 * F(2) F(3) = 3 * 2 = 6 F(2) = 2 * F(1) F(2) = 2 * 1 = 2 F(1) = 1 F(1) = 1 9 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
Ví dụ 1: Tính n! Ví dụ 1: Tính n! bằng đệ quy. long factorial(int n) #include { #include if((n==0)||(n==1)) return 1; long factorial(int); else return n*factorial(n-1); void main() } { int n; printf("Nhap vao mot so: "); scanf("%d",&n); printf("Gia tri cua giai thua: %ld",factorial(n)); getch(); } 10 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
3.2. Ví dụ về đệ quy (2/6) Ví dụ 2: Tìm max của một dãy số. F(a,1) = a[1], F(a,2) = max(a[1],a[2]) F(a,n) = max(F(a,n-1),a[n]) if n > 2 Cho a[] = [3,2,5,7,1]. Tính F(a,5) = ? Bước Winding UnWinding Phase F(a,5) = max(F(a,4),a[5]) F(a,5) = max(7,1) = 7 F(a,4) = max(F(a,3),a[4]) F(a,4) = max(5,7) = 7 F(a,3) = max(F(a,2),a[3]) F(a,3) = max(3,5) = 5 F(a,2) = max(a[1],a[2]) F(a,2) = max(3,2)=3 11 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
Ví dụ 2: Tìm max của một dãy số Ví dụ 2: Tìm max. int F(int *a, int n) #include { #include if (n==1) return a[0]; int F(int *, int); if (n==2) return max(a[0],a[1]); int max(int, int); if (n>2) return max(F(a,n-1),a[n-1]); void main() } { int max(int a, int b) int n; int a[100]; { printf("Nhap vao so phan tu: "); if(a>b) return a; scanf("%d",&n); else return b; for(int i=0;i
3.2. Ví dụ về đệ quy (3/6) Ví dụ 3: Tính tổng của một dãy số. F(a,1) = a[1] F(a,n) = F(a,n-1)+a[n] if n > 1 Cho a[] = [1,7,3,5], Tính F(a,4) = ? Bước Winding Bước UnWinding F(a,4) = F(a,3) + a[4] F(a,4) = 11 + 5 = 16 F(a,3) = F(a,2) + a[3] F(a,3) = 8 + 3 = 11 F(a,2) = F(a,1) + a[2] F(a,2) = 1 + 7 = 8 F(a,1) = a[1] F(a,1) = 1 13 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
Ví dụ 3: Tính tổng của một dãy số Ví dụ 3: Tính tổng một dãy số. long sum(int * a, int n) #include { #include if(n==1) return a[0]; long sum(int*, int); else return sum(a,n-1)+a[n-1]; void main() } { int n; int a[100]; printf("Nhap vao so pt: "); scanf("%d",&n); for(int i=0;i
3.2. Ví dụ về đệ quy (4/6) Ví dụ 4: Dãy số Fibonacci. F(n) = 1 nếu n = 1 hoặc n = 2 F(n) = F(n-1) + F(n-2) nếu n > 2 Tính F(4) = ? Bước Winding Bước UnWinding F(4) = F(3) + F(2) F(4) = 2 + 1 = 3 F(3) = F(2) + F(1) F(3) = 1 + 1 = 2 F(2) = 1 F(2) = 1 F(1) = 1 F(1) = 1 15 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
Ví dụ 4: Tính số Fibonacci Ví dụ 4: Tính số fibonacci. long fibonacci(int n) #include { #include if((n==1) || (n==2)) return 1; long fibonacci( int); else return fibonacci(n-1)+fibonacci(n-2); } void main() { int n; printf("Nhap vao n: "); scanf("%d",&n); printf("Fibonacci cua %d: %ld",n,fibonacci(n)); getch(); } 16 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
3.2. Ví dụ về đệ quy (5/6) Ví dụ 5: Hàm Ackermann. F(m,0) = m + 1 nếu m >= 0 F(0,n) = F(1,n-1) nếu n > 0 F(m,n) = F(F(m-1,n),n-1) nếu m >= 1 và n > 0 Tính F(2,1) = ? Bước Winding Bước UnWinding F(2,1) = F(F(1,1),0) F(2,1) = F(3,0) = 4 F(1,1) = F(F(0,1),0) F(1,1) = F(2,0) = 3 F(0,1) = F(1,0) F(0,1) = 2 F(1,0) = 2 F(1,0) = 2 17 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
Ví dụ 5: Hàm Ackermann Ví dụ 5: Hàm Ackermann int Ackermann(int m, int n) #include { #include if((m>=0) && (n==0)) return m+1; int Ackermann(int, int); if((n>0) && (m==0)) return Ackermann(1,n-1); if((m>=1) && (n>0)) return void main() Ackermann(Ackermann(m-1,n), n-1); { } int m, n; printf("Nhap vao m= "); scanf("%d",&m); printf("Nhap vao n= "); scanf("%d",&n); printf("Ackermann cua %d va %d: %d",m,n,Ackermann(m,n)); getch(); } 18 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
3.2. Ví dụ về đệ quy (6/6) Ví dụ 6: Pascal Identifier Definition Character Character Digit Identifiers: Name of Constants, Variables, Functions, Procedure, Programs, Labels, … 19 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University
3.3. Đệ quy đuôi - Tail Recursion (1/6)  Hàm đệ quy được gọi là đệ quy đuôi - tail recursive – nếu các lời gọi đệ quy trong hàm là công việc cuối cùng của quá trình đệ quy.  Trong quá trình đệ quy, các trạng thái của quá trình trước được lưu cho quá trình sau. Tuy vậy, với đệ quy đuôi, việc lưu trên là không cần thiết.  Hàm đệ quy đuôi không có bước quay ngược.  Tính chất trên không quá quan trọng vì phần lớn các bộ xử lý hiện nay thực hiện được điều này tự động. 20 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University