Đệ quy phi tuyến: Thân hàm đệ quy lặp gọi 1 số lần chính nó.

long U (int n){ 

    if (n<6) return n;
    long S= 0;
    for (int i = 5; i>0; i--) 

          S+= U(n-i);
    return S;
}

Bài toán 1: Tính tổng n phần tử trong danh sách

Viết chương trình tính tổng n phần tử a0,...,an-1 được định nghĩa đệ quy như sau:

Mã nguồn:

#include<conio.h>

#include<iostream>

using namespace std;

long int S(int a[], int n) {

if(n==1)

return a[0];

else

return a[n-1]+S(a,n-1);

}

int main(){

int *a,n;

cout<<"n = ";

cin>>n;

a = new int[n];

cout<<"Nhap vao "<<n<<" phan tu\n";

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

cout<<"a["<<i<<"] = ";

cin>>a[i];

}

cout<<"Tong "<<n<<" phan tu trong mang A la "<<S(a,n);

getch();

return 0;

}

Bài toán 2: Tính tích n phần tử trong danh sách

Viết chương trình tính tổng n phần tử a0,...,an-1 được định nghĩa đệ quy như sau:

Mã nguồn:

#include<conio.h>

#include<iostream>

using namespace std;

long int S(int a[], int n) {

if(n==1)

return a[0];

else

return a[n-1]*S(a,n-1);

}

int main(){

int *a,n;

cout<<"n = ";

cin>>n;

a = new int[n];

cout<<"Nhap vao "<<n<<" phan tu\n";

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

cout<<"a["<<i<<"] = ";

cin>>a[i];

}

cout<<"Tich "<<n<<" phan tu trong mang A la "<<S(a,n);

getch();

return 0;

}

Bài toán 3: Đếm số lần xuất hiện của phần tử x trong danh sách

Viết  chương  trình  đếm  số  lần  xuất  hiện  của  số  nguyên  x  trong  danh  sách A={a0,...,an-1} với n phần tử. Thuật toán đệ quy được thể hiện như sau:

Mã nguồn:

#include<conio.h>

#include<iostream>

using namespace std;

/*Ham tra ve so lan xuat hien cua x trong danh sachA*/

int Find(int a[], int n, int x) {

if(n==0)

return 0;

else if(a[n-1]==x)

return 1+Find(a,n-1,x);

else

return Find(a,n-1,x);

}

int main(){

int *a,n,x;

cout<<"n = ";

cin>>n;

a = new int[n];

cout<<"Nhap vao danh sach "<<n<<" phan tu\n";

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

cout<<"a["<<i<<"] = ";

cin>>a[i];

}

cout<<"x = ";

cin>>x;

cout<<"So lan xuat hien cua "<<x<<" trong danh sach la "<<Find(a,n,x);

getch();

return 0;

}
Tag: C, C++, Đệ quy tuyến tính, Đệ quy, Khử đệ quy, recursive, đệ quy nhị phân, đệ quy hỗ tương, Đệ quy phi tuyến