Phương pháp thiết kế giải thuật đệ qui:
B1: Tham số hóa bài toán
B2: Tìm trường hợp suy biến
B3: Phân tích các trường hợp chung(Tổng quát)
Vd1: Tìm giai thừa n!
Ta có n=1*2*3*...*n
tức n=1*2*3*...*(n-1)*n
B1: GT(n)
B2: Nếu n=0 => GT(0)=1
B3: GT(n) = n*GT(n-1)
=> GT(n) = 1, n=0
n*GT(n-1), n>0
Chương trình:
int GT(int n){
if(n==0) return 1;
else
return n*GT(n-1);
}
Vd2: Đếm số chữ số của số nguyên dương n
B1: F(n)
B2: n<10 => F(n)=1
B3: F(n) = 1+F(n/10)
Chương trình:
int F(int n){
if(n<10) return 1;
else
return 1+F(n/10);
}
Vd3: Cho dãy các số nguyên a1, a2, ... , an
Kiểm tra dãy đó đã sắp xếp tăng dần chưa?
B1: Tangdan(n,a[])
B2: n<=1 => tăng dần
B3: a[n]<a[n-1] => không tăng
Ngược lại Tangdan(n-1,a)
Chương trình:
bool Tangdan(int n, int a[]){
if(n<=1) return true;
else if(a[n]<a[n-1]) return false;
else return Tangdan(n-1,a);
}
Vd4: Tháp HaNoi
B1: ThapHN(n,A,B,C)
B2: n=1 => Chuyển từ A->C
B3: n=2
ThapHN(1,A,B,C)
ThapHN(1,A,C,B)
ThapHN(1,B,A,C)
n>2
ThapHN(n-1,A,B,C)
ThapHN(1,A,B,C)
ThapHN(n-1,A,B,C)
Chương trình:
void ThapHN(int n, char A, char B, char C){
if(n==1) printf("Chuyen tu A->C");
else
{
ThapHN(n-1,A,B,C)
ThapHN(1,A,B,C)
ThapHN(n-1,A,B,C)
}
}
Bài tập:
1/ Tìm USCLN(a,b)
2/ Kiểm tra mảng a1, ..., an có đối xứng