Bài giảng Kỹ thuật lập trình - Bài: Kỹ thuật đệ quy

Kỹ thuật đệ quy

Nhắc lại kỹ thuật Đệ quy

Recursive

Mô tả đệ quy

Recursive

Mô tả theo cách phân tích

đối tượng thành nhiều

thành phần mà trong số

các thành phần có thành

phần mang tính chất của

chính đối tượng được mô

tả

Mô tả đối tượng

thông qua chính nó

Mô tả đệ quy tập số tự nhiên N

. Số 1 là số tự nhiên (1-N).

Ví dụ

. Số tự nhiên bằng số tự nhiên cộng 1.

Mô tả đệ quy cấu trúc danh sách kiểu T

. Cấu trúc rỗng là một danh sách kiểu T.

. Ghép nối một thành phần kiểu T (nút kiểu

T) với một danh sách kiểu T ta có một

danh sách kiểu T.

Mô tả đệ quy cây gia phả

. Gia phả của một người bao gồm người đó

và gia phả của cha và gia phả của mẹ

Tính giai thừa của n

Ví dụ

. Định nghĩa không đệ quy n!

n! = n * (n-1) * … * 1

. Định nghĩa đệ quy:

n! = 1

nếu n=0

n * (n-1)! nếu n>0

Mã C++

int factorial(int n) {

if (n==0) return 1;

else

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

}

Thực hiện tính

giai thừa

factorial (3)

n=3

factorial (2)

…

n=2

3*factorial(2)

…

factorial (1)

6

n=1

2*factorial(1)

…

2

factorial (0)

n=0

1*factorial(0)

…

1

return 1;

1

Trạng thái hệ thống

khi tính giai thừa

Stack hệ thống

factorial(0)

factorial(1) factorial(1) factorial(1)

factorial(2) factorial(2) factorial(2) factorial(2) factorial(2)

factorial(3) factorial(3) factorial(3) factorial(3) factorial(3) factorial(3) factorial(3)

t

Thời gian hệ thống

Trả về từ Trả về từ

hàm hàm

factorial(0 factorial(1 factorial(2 factorial(3

Trả về từ

hàm

Trả về từ

hàm

Gọi hàm

factorial(3) factorial(2) factorial(1) factorial(0)

)

t

Thành phần của

mô tả đệ quy

▪ Phần neo: trường hợp suy biến của đối tượng

▫ Ví dụ: 1 là số tự nhiên, cấu trúc rỗng là danh sách kiểu T, 0!=1,

SM (a[x:x]) là thao tác rỗng.

▪ Phần qui nạp: mô tả đối tượng (giải thuật) thông qua chính

đối tượng (giải thuật) đó một cách trực tiếp hoặc gián tiếp.

Ví dụ:

▫ n! = n * (n –1)!

▫ SM (a[m:n]) ≡Merge (SM (a[m:( m+n) div 2] , SM (a[(m+n) div 2

+1 : n]) )

Phân loại

đệ quy

Đệ quy trực tiếp

Đệ quy gián tiếp

▸Đệ quy tuyến tính ▸Đệ quy hỗ tương

▸Đê qui nhị phân

▸Đệ quy phi tuyến

KieuDuLieu TenHam(Thamso)

{

if(Dieu Kien Dung)

{

...;

Đệ quy

tuyến tính

return Gia tri tra ve;

}

...;

TenHam(Thamso)

...;

}

▪ Là đệ quy có dạng

P( ) {

If (B) thực hiện S;

else { thực hiện S* ; gọi P }

}

Với S , S* là các thao tác không đệ quy.

▪ VD: Hàm FAC(n) tính số hạng n của dãy n!

int FAC( int n )

{

if ( n == 0 ) return 1 ;

else return ( n * FAC(n-1 )) ;

}

Tính

Ví dụ

S(n) = 1/(1*2) + 1/(2*3) + ... + 1/( n*(n+1) )

S(n) = 1/2 khi n==1

= S(n-1)+1/(n*(n+1))

float S(int n) {

if ( n==1) return 0.5;

else return S(n-1)+1.0/(n*(n+1));

}

KieuDuLieu TenHam(Thamso)

{

if(Dieu Kien Dung)

{

...;

Đệ quy

nhị phân

return Gia tri tra ve;

}

...;

TenHam(Thamso);

...;

▪ Là đệ quy có dạng

TenHam(Thamso);

...;

}

P ( ) {

If (B) thực hiện S;

else {

thực hiện S*;

gọi P ; gọi P;

}

Với S , S* là các thao tác không đệ quy.

▪ Ví dụ: Hàm FIBO(n) tính số hạng n của dãy FIBONACCI

int F(int n) {

if ( n < 2 ) return 1;

else

return (F(n -1) + F(n -2));

}

Tính tổng các giá trị của dãy số H(n), biết

H(n) = n khi n<3

Ví dụ

= 2*H(n-1)*H(n-2) khi n>2

long H(int n) {

if (n<3) return n;

else return 2*H(n-1)*H(n-2);

}

long Tong(int n) {

long tg=0;

for( int i=1; i<=n;i++)

tg+=H(i);

return tg;

}

KieuDuLieu TenHam(Thamso)

{

if(Dieu Kien Dung)

{

...;

Đệ quy

phi tuyến

return Gia tri tra ve;

}

...;

vonglap(dieu kien lap)

{

...TenHam(Thamso)...;

}

return Gia tri tra ve;

}

▪ Là đệ quy mà lời gọi đệ quy được thực hiện bên trong vòng

lặp.

P ( ) {

for (<giá tri đầu> to <giátrịcuối>) {

thực hiện S ;

if (điều kiện dừng) then thực hiện S*;

else gọi P;

}

Với S , S* là các thao tác không đệ quy.

Đệ quy

phi tuyến

▪ Ví dụ: Cho dãy { An } xác định theo công thức truy hồi :

A₀= 1 ;

A_n= n²A₀+(n-1)²A₁+ . . . + 2²A_n-2+ 1²A_n-1

int A( int n ) {

if (n==0) return 1 ;

else {

int tg = 0 ;

for (int i=0; i<n; i++)

tg = tg + sqr(n-i) *A(i);

return tg;

}

KieuDuLieu TenHamX(Thamso)

{

if(Dieu Kien Dung)

{

...;

Đệ quy

tương hỗ

return Gia tri tra ve;

}

...;

return TenHamX(Thamso) <Lien

ket hai ham> TenHamY(Thamso);

▪ Là một loại đệ quy gián

}

tiếp

KieuDuLieu TenHamY(Thamso)

{

▪ Trong đệ quy tương hỗ

có 2 hàm, và trong thân

của hàm này có lời gọi

của hàm kia, điều kiện

dừng và giá tri trả về

của cả hai hàm có thể

giống nhau hoặc khác

nhau

if(Dieu Kien Dung)

{

...;

return Gia tri tra ve;

}

...;

return TenHamY(Thamso)<Lien

ket hai ham>TenHamX(Thamso);

}

X(n) = 1,2,3,5,11,41……

Y(n) = 1,1,2,6,30,330 …..

Ví dụ

void main() {

int n;

printf("\n Nhap n = ");

scanf("%d",&n);

printf( "\n X = %d " ,X(n));

printf( "\n Y = %d " , Y(n));

getch();

}

long Y(int n); //prototype cua ham y

long X(int n) {

if(n==0)

return 1;

else

return X(n-1) + Y(n-1);

}

long Y(int n) {

if(n==0)

return 1;

else

return X(n-1)*Y(n-1);

}

Tìm giải thuật

đệ quy

1. Thông số hóa bài toán .

▫ Tổng quát hóa bài toán cụ thể cần giải thành bài toán tổng

quát (một họ các bài toán chứa bài toán cần giải )

▫ Tìm ra các thông số cho bài toán tổng quát

▸các thông số điều khiển: các thông số mà độ lớn của chúng đặc

trưng cho độ phức tạp của bài toán , và giảm đi qua mỗi lần gọi đệ

quy.

▸Vídụ

▸n trong hàm FAC(n) ;

▸a , b trong hàm USCLN(a,b) .

Tìm giải thuật

đệ quy

2. Tìm các trường hợp neo cùng giải thuật giải tương ứng

▫ trường hợp suy biến của bài toán tổng quát

▫ các trường hợp tương ứng với các gía trị biên của các biến điều

khiển

▫ VD:

FAC(1) =1

USCLN(a,0) = a

3. Tìm giải thuật giải trong trường hợp tổng quát bằng phân

rã bài toán theo kiểu đệ quy

Tìm giải thuật

đệ quy

▪ Phân rã bài toán tổng quát theo phương thức đệ quy

▫ Tìm phương án (giải thuật ) giải bài toán trong trường hợp

tổng quát phân chia nó thành các thành phần

▸giải thuật không đệ quy

▸bài toán trên nhưng có kích thước nhỏ hơn.

▫ Vídụ

FAC(n) = n * FAC(n -1) .

Tmax(a[1:n]) = max(Tmax(a[1:(n-1)]) , a[n] )