ĐỆ QUY

Khái niệ m :

Một hàm được gọi là đệ qui nế u bê n trong thân của hàm đó có lời gọi hàm lại chính nó

Phân loại đệ qui :

Đệ quy thường gặp thuộc một trong bốn loại s au :

Đệ qui tuyế n tính

Đê qui nhị phân Đệ qui phi tuyế n Đệ qui hỗ tương

Cấu trúc hàm đệ qui :

Đệ qui tuyế n tính : Cấu trúc của nó giống như định nghĩa :

Kie uDuLieu Te nHam(Thamso)

{

if(Die u Kieu Dung)

{

}

...;

...;

re turn Gia tri tra ve ;

Te nHam(Thams o)

...;

...;

}

Đệ qui nhị phân : Cũng giống như đệ qui tuyế n tính nhưng bên trong thân hàm của nó có thê m một

lời gọi lại chính nó

Kie uDuLieu Te nHam(Thamso)

{

if(Die u Kie u Dung)

{

}

...;

...;

re turn Gia tri tra ve ;

TenHam(Thamso);

...;

...; TenHam(Thamso);

...;

...;

}

Đệ qui tương hỗ : Trong đệ qui tương hỗ thì thường 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 tra về của cả hai hàm có thể giống nhau hoặc khác nhau

Kie uDuLieu Te nHamX(Thams o)

{

if(Die u Kie u Dung)

{

}

...;

...;

re turn Gia tri tra ve ;

re turn Te nHamX(Thams o) <Lie n ket hai ham> TenHamY(Thamso);

}

Kie uDuLieu Te nHamY(Thams o)

{

if(Die u Kieu Dung)

{

...;

re turn Gia tri tra ve ;

}

...;

re turn Te nHamY(Thamso)<Lie n ket hai ham>Te nHamX(Thams o);

}

Đệ qui phi tuyế n : Hàm được gọi là đệ qui phi tuyế n nế u bên trong thân hàm có lời gọi lại chính nó

được đặt bê n trong thân của vòng lặp

Kie uDuLieu Te nHam(Thamso)

{

if(Die u Kie u Dung)

{

...;

re turn Gia tri tra ve ;

}

...;

vonglap(die u kie u lap)

{

...Te nHam(Thamso)...;

}

re turn Gia tri tra ve ;

}

B ài tập đệ qui :

1/Đệ qui tuyế n tính :

B ài tập 730: Tính S(n) = 1 + 2 + 3 + ... + n - 1 + n int Tinh(int n)

{

if (n==1)

re turn 1;

re turn Tinh(n-1) + n;

}

B ài tập 731 : Tính S(n) = 1^2 + 2^2 + 3^2 + ... + (n-1)^2 + n^2

int Tinh(int n)

{

if (n==1)

re turn 1;

re turn Tinh(n-1) + n*n;

}

B ài tập 732 : Tính S(n) = 1 + 1/2 + 1/3 + ... + 1/n

float Tinh(float n)

{

if (n==1)

re turn 1;

re turn Tinh(n-1) + 1/n;

}

B ài tập 733 : Tính S(n) = 1/2 + 1/4 + ... + 1/2n

re turn 0.5;

re turn Tinh(n-1) + 1/(2*n);

}

B ài tập 734 : Tính S(n) = 1 + 1/3 + 1/5 + ... + 1/(2n+1)

float Tinh(float n)

{

if (n==1)

re turn 1;

re turn Tinh(n-1) + 1/(2*n+1);

}

B ài tập 735: Tính S(n) = 1/(1*2) + 1/(2*3) + 1/( n(*n-1) )

float Tinh(float n)

{

if (n==1)

re turn 0.5;

re turn Tinh(n-1) + 1/(n*(n+1));

}

B ài tập 736 : Tính S(n) = 1/2 + 2/3 + 3/4 + ... + n/(n+1)

float Tinh(float n)

{

if (n==1)

re turn 0.5;

re turn Tinh(n-1) + n/(n+1);

}

B ài tập 737 :Tính S(n) = 1/2 + 3/4 + 5/6 + ... + (2n+1)/(2n+2)

float Tinh(float n)

{

if (n==1)

re turn 0.5;

re turn Tinh(n-1) + (2*n+1)/(2*n+2);

}

B ài tập 738 :Tính T(n) = 1*2*3*.....*n

float Tinh(float n)

{

if (n==1)

re turn 1;

re turn Tinh(n-1)*n;

}

B ài tập 739 :Tính T(x,n) = x^n

float LuyThua( float x , int n)

{

if(n == 0)

{

re turn 1;

}

if(n < 0)

re turn LuyThua(x,n+1) * 1/x;

}

re turn LuyThua(x,n-1) * x;

}

B ài tập 740 :Tính S(n) = 1 + 1.2 + 1.2.3 + .... + 1.2.3....n

long GiaiThua(int n)

{

if(n==1)

{

re turn 1;

}

re turn GiaiThua(n-1)*n;

}

long Tong(int n)

{

if(n == 1)

{

re turn 1;

}

re turn Tong(n-1) + GiaiThua(n-1)*n;

}

B ài tập 741 :Tính S(x,n) = x + x^2 + x^3 + ... + x^n

float LuyThua( float x , int n)

{

if(n == 0)

{

re turn 1;

}

re turn LuyThua(x,n-1)*x;

}

float Tong(float x , int n)

{

if(n == 1)

{

re turn x;

}

re turn Tong(x,n-1) + LuyThua(x,n-1)*x;

}

B ài tập 742 :Tính S(x,n) = x^2 + x^4 +.... + x^2n

double bai742(int x, int n)

{

if (n==1)

{

re turn pow(x,2*n);

}

re turn bai742(x,n-1) + pow(x,2*n);

}

B ài tập 743 :Tính S(x,n) = x + x^3 + x^5 +....+ x^(2n+1)

{

re turn pow(x,n);

}

re turn tinh(x,n-1) + pow(x,n+1);

}

B ài tập 744 :Tính S(n) = 1 + 1/(1+2) + 1/(1+2+3) + ... + 1/(1+2+3+...+n)

float Tong(float n)

{

if(n == 1)

{

re turn (float)1;

}

re turn Tong(n-1) + n;

}

float TongChia(float n)

{

if(n == 1)

{

re turn (float)1;

}

re turn TongChia(n-1) + 1/(Tong(n-1) + n);

}

B ài tập 745 :Tính S(x,n) = x + (x^2)/2! + (x^3)/3! + ... + (x^n)/n!

float LuyThua(float x , float n)

{

if(n == 1)

{

re turn x;

}

re turn LuyThua(x,n-1)*x;

}

float GiaiThua( float n)

{

if(n == 1)

{

re turn (float)1;

}

re turn GiaiThua(n-1)*n;

}

float LTChiaGT(float x , float n)

{

if(n == 1)

{

re turn x;

}

re turn LTChiaGT(x,n-1) + ((LuyThua(x,n-1)*x) / (GiaiThua(n-1)*n));

}

B ài tập 746 :Tính S(x,n) = 1 + (x^2)/2! + (x^4)/4! + ... + (x^2n)/(2n)!

float LuyThua(float x , float n)

{

if(n == 0)

re turn (float)1;

}

re turn LuyThua(x,n-1) *x*x;

}

float GiaiThua( float n)

{

if(n == 0)

{

re turn (float)1;

}

re turn GiaiThua(n-1)*n;

}

float LTChiaGT(float x , float n)

{

if(n == 0)

{

re turn (float)1;

}

re turn LTChiaGT(x,n-1) + ( (LuyThua(x,n-1)*x*x) / ((GiaiThua (2*n - 1) *2*n)));

}

B ài tập 747 :Tìm ước số lẻ lớn nhất của số nguyê n dương n . Ví dụ : n = 100 ước lẻ lớn nhất của 100

là 25

int UocLeMax(int n)

{

if(n % 2 == 1)

{

re turn n;

}

re turn UocLeMax(n/2);

}

B ài tập 748 :Tính S(n) = s qrt(2 + s qrt (2 + ... s qrt ( 2 + s qrt(2) ) ) )

#include <math.h>

float Function(float n)

{

if(n == 1)

{

re turn s qrt(2);

}

re turn s qrt(2 + Function(n-1));

}

B ài tập 749 :Tính S(n) = s qrt(n + s qrt (n-1 + s qrt(n-2 + ...s qrt(2 + s qrt (1) ) ) ) )

#include <math.h>

long double Function(long double n)

{

if(n == 1)

{

re turn 1;

}

re turn s qrt(n + Function(n-1));

}

B ài tập 750 :Tính S(n) = s qrt(1 + s qrt(2 + sqrt (3 + ...s qrt (n-1 + s qrt (n)))))

[FONT="]#include <math.h>[/FONT]

[FONT="]float Function(float i, float n) //bắt đầu: i=1[/FONT]

[FONT="]{[/FONT]

[FONT="] if(n == i)[/FONT]

[FONT="] {[/FONT]

[FONT="] re turn s qrt(n);[/FONT]

[FONT="] }[/FONT]

[FONT="] re turn s qrt( i + Function(i+1,n));[/FONT]

[FONT="]}[/FONT

]

B ài tập 751 :S(n) = 1/(1 + 1/(1 + 1/(1 + 1/(... 1 /(1/(1 + 1/(1 + 1 )))))))

long double Thuong(int n)

{

if(n == 1)

{

re turn 1.0 / (1.0 + 1.0);

}

re turn 1 / (1 + Thuong(n-1));

}

B ài tập 752 :Hãy đế m số lượng chữ số của số nguyê n dương n

int De mSoLuongChuSo(int n)

{

if(n == 0)

{

re turn 0;

}

re turn De mSoLuongChuSo(n/10) + 1;

}

B ài tập 753 :Hãy tính tổng các chữ số của số nguyê n dương n

int TongChuSo(int n)

{

if(n == 0)

{

re turn 0;

}

re turn TongChuSo(n/10) + n % 10;

}

B ài tập 754 :Hãy tính tích các chữ số của số nguyê n dương n

int Tich(int n)

{

if(n == 0)

{

re turn 1;

}

re turn Tich(n/10) * (n%10);

}

B ài tập 755 :Hãy đế m số lượng chữ số lẻ của s ố nguyê n dương n

int De mLe(int n)

{

if(n == 0)

{

re turn 0;

}

if(n%2 == 1)

{

re turn De mLe(n/10) + 1;

}

re turn De mLe(n/10);

}

B ài tập 756 :Hãy tính tổng các chữ số chẵn của số nguyê n dương n

int TongChuSoChan(int n)

{

if(n == 0)

{

re turn 0;

}

if(n%2 == 0)

{

re turn TongChuSoChan(n/10) + (n%10);

}

re turn TongChuSoChan(n/10);

}

B ài tập 757 :Hãy tính tích các chữ số lẻ của số nguyê n dương n

int TichChuSoLe (int n)

{

if(n == 0)

{

re turn 0;

}

if(n % 2 == 1)

{

re turn TichChuSoLe(n/10) * (n%10);

}

re turn TichChuSoLe(n/10);

}

B ài tập 758 :Cho số nguyê n dương n . Hãy tìm chữ s ố đầu tiê n của n

int ChuSoDauTie n(int n)

{

if(n/10 == 0)

{

re turn n;

}

re turn ChuSoDauTie n(n/10);

}

B ài tập 759 :Hãy tìm chữ số đảo ngược của số nguyê n dương n

int De mSoLuongChuSo(int n)

{

if(n == 0)

{

re turn 0;

}

re turn De mSoLuongChuSo(n/10)+1;

}

int DoiChuSo(int H , int De m)

{

if(De m > 0)

{

re turn DoiChuSo(H*10,De m-1);

}

re turn H;

}

int ChuSoDaoNguoc(int n)

{

if(n == 0)

{

re turn 0;

}

int Dem = De mSoLuongChuSo(n);

int H = n%10;

int T = DoiChuSo(H,Dem-1);

re turn ChuSoDaoNguoc(n/10) + T;

}

B ài tập 760 :Tìm chữ số lớn nhất của số nguyê n dương n

int ChuSoLonNhat(int Max,int n) //Max bắt đầu là n%10

{

if (n%10==0)

{

re turn Max;

}

Max=(Max>n%10)?Max:n%10;

re turn ChuSoLonNhat(Max,n/10);

}

B ài tập 761 :Tìm chữ số nhỏ nhất của số nguyê n dương n

int ChuSoNhoNhat(int Min,int n) //Min bắt đầu là n%10

{

if (n%10==0)

{

re turn Min;

}

Min=(Min<n%10) ? Min : n%10;

re turn ChuSoLonNhat(Min,n/10);

}

B ài tập 762 :Hãy kiể m tra số nguyê n dương n có toàn chữ s ố lẻ hay không ?

int KTToanLe (int n)

{

if (n%2==0 && n!= 0)

{

re turn 0;

}

if (n%2==1)

{

re turn KTToanLe (n/10);

}

re turn 1;

}

B ài tập 763 : Hãy kiể m tra số nguyê n dương n có toàn chữ số chẵn hay không ?

int KTToanChan(int n)

{

if(n == 0)

{

re turn 1;

}

if(n % 2 == 1)

{

re turn 0;

}

if(n % 2 == 0)

{

re turn KTToanChan(n/10);

}

re turn 1;

}

Làm thê m đệ qui cho mảng 1 chiề u, ma trận nhé !

--------Hết đệ qui------