Đệ 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