Code C++: Đệ quy Tuyến tính

Đệ quy tuyến tính: Thân hàm gọi 1 lần chính nó


Ví dụ:

double U(int n, double a, double r){
      if (n==1) return a;
      return r + U(n-1,a,r);    //Gọi 1 lần chính tên hàm đang định nghĩa
}

Bài toán 1: Tính X lũy thừa n

Viết chương trình tính X^n với X là số thực được xác định như sau:


Mã nguồn:

#include<conio.h>
#include<iostream>
using namespace std;
/* Hàm đệ quy trả về số thực tính giá trị X^n*/
float Mu(float X, int n){
if(n==0)
return 1;
else
return X*Mu(X,n-1);  // Gọi đệ quy hàm Mu
}
/* Chương trình chính */
int main(){
int n;
float X;
cout<<"Nhap vao gia tri cua n = ";
cin>>n;
cout<<"Nhap vao gia tri cua X = ";
cin>>X;
cout<<X<<"^"<<n<<" = "<<Mu(X,n);
getch();
return 0;
}

Bài toán 2: Thuật toán Euclide tìm ước chung lớn nhất

Viết chương trình tìm ước chung lớn nhất của 2 số nguyên dương a, b bằng thuật toán Euclide được định nghĩa đệ quy như sau:


Mã nguồn:

#include<conio.h>
#include<iostream>
using namespace std;
/* Hàm đệ quy trả về ước chung lớn nhất của 2 số a,b */
int UCLN(int a, int b) {
if(a==b)
return a;
else if(a>b)
return UCLN(a-b,b);  //Gọi hàm đệ quy UCLN
else
return UCLN(a,b-a);  //Gọi hàm đệ quy UCLN
}
/* Chương trình chính */
int main(){
int a,b;
cout<<"Nhap a = ";
cin>>a;
cout<<"Nhap b = ";
cin>>b;
cout<<"Uoc chung lon nhat cua "<<a<<" va "<<b<<" la "<<UCLN(a,b);
getch();
return 0;
}

Bài toán 3: Tính n giai thừa
Viết chương trình tính n! được định nghĩa đệ quy như sau:
Mã nguồn:
#include<conio.h>
#include<iostream>
using namespace std;
/* Hàm đệ quy trả về giai thừa của n */
int GiaiThua(int n){
if(n==0)
return 1;
else
return n*GiaiThua(n-1);
}
/* Chương trình chính */
int main(){
int n;
cout<<"Nhap n = "; cin>>n;
cout<<n<<"!= "<<GiaiThua(n);
getch();
return 0;
}
Tag: C, C++, Đệ quy tuyến tính, Đệ quy, Khử đệ quy, recursive

Related Posts
Previous
« Prev Post