Hàm gọi lại chính nó được gọi là đệ quy. Hàm đề quy có 4 loại bao gồm:
- Đệ quy tuyến tính => Thân hàm gọi 1 lần chính nó
- Đệ quy nhị phân => Thân hàm gọi 2 lần chính nó
- Đệ quy phi tuyến => Thân hàm lặp gọi 1 số lần chính nó
- Đệ quy hỗ tương => 2 hàm đệ quy gọi nhau
Sau đây chúng ta cũng tìm hiểu những dạng bài nào được viết dạng đệ quy.
Tổng hợp các bài toán về đệ quy trong C
1. Hàm nhập, xuất mảng đệ quy
| void nhapmang(int a[], int n){ if(n==0) return; nhapmang(a, n-1); printf(“\nNhap phan tu %d: “,n-1); scanf(“%d”,&a[n-1]); }void xuatmang(int a[], int n){ if(n == 0) return; xuatmang(a, n-1); printf(“%4d”,a[n-1]); } |
2. Hàm xuất mảng ngược
Vd: Mảng a[5]={2, 4, 5, 3, 9} thì ta có mảng ngược là a[5]={9, 3, 5, 4, 2}
| void xuatmangnguoc(int a[], int n){ if(n == 0) return; printf(“%4d”,a[n-1]); xuatmangnguoc(a, n-1); } |
3. Tính tổng n
Vd: n = 5 thì ta có S = 1 + 2 + 3 + 4 + 5
| //Dung de quy long tong(int n){ if(n==0) return 0; return n + tong(n-1); } |
4. Đếm mảng các số chẵn
Chú thích: Chúng ta sẽ đếm những số chẵn có trong mảng có bao nhiêu số.
| int demchan(int a[], int n){ if(n == 0) return 0; if(n % 2 == 0) return 1 + demchan(a,n-1); return demchan(a,n-1); } |
5. Đếm mảng các số nguyên tố
| bool ktnt(int n){ int d=0; for(int i=1; i< n; i++){ if(n%i==0) d=d+1; } if(d==1) return true; return false; } int demsonguyento(int a[], int n){ if(n==0) return 0; if(ktnt(a[n-1])) return 1 + demsonguyento(a, n-1); return demsonguyento(a, n-1); } |
6. Hàm tổng mảng
| long tongmang(int a[], int n){ if(n==0) return 0; return a[n-1] + tongmang(a,n-1); } |
7. Hàm tổng mảng chẵn
| long tongmangchan(int a[], int n){ if(n==0) return 0; if(a[n-1] % 2 == 0) return a[n-1] + tongmangchan(a, n-1); return tongmangchan(a, n-1); } |
8. Hàm tính tổng các giá trị lớn hơn giá trị đứng trước nó.
Vd: 5, 6, 9, 1, 2 thì ta có S= 6 + 9 + 2 vì 5 < 6 ta lấy 6, 6 < 9 ta lấy 9…
| long tonglhdt(int a[], int n){ if(n==0) return 0; if(a[n-1] > a[n]) return a[n-1] + tonglhdt(a,n-1); return tonglhdt(a, n-1); } |
9. Kiểm tra mảng toàn chẵn
| bool kttoanchan(int a[], int n){ if(n==0) return true; if(a[n-1] % 2 != 0) return false; return kttoanchan(a, n-1); } |
10. Hàm tìm max trong mảng
| int timmax(int a[], int n){ if(n==1) return a[0]; if(a[n-1] > timmax(a,n-1)) return a[n-1]; return timmax(a,n-1); } |
11. Tìm vị trí max trong mảng
| int timvitrimax(int a[], int n){ if(n==1) return 0; if(a[n-1] > a[timmax(a,n-1)]) return n-1; return timmax(a,n-1); } |
12. Hàm xếp tăng mảng
| void sapxeptang(int a[], int n){ if(n==1) return; for(int i=0;i<n;i++){ if(a[i] > a[n-1]){ int tam = a[i]; a[i]=a[n-1]; a[n-1]=tam; } } sapxeptang(a,n-1); } |
13. Giả xử x1=1, x2 =1, xn=x(n-1) + (n-1)*x(n-2)
Viết hàm tính xn bằng đệ quy.
| long tinhdequy(int n){ if(n==1 || n==2) return 1; return tinhdequy(n-1) + (n-1)*tinhdequy(n-2); } |
14. Tính số hạng n của dãy Fibonacci sau.
f1=1
f2=1
fn=fn-1 + fn-2, n>=3
| long Fibonaci(int n){ if(n==1 || n==2) return 1; return Fibonaci(n-1) + Fibonaci(n-2); } |
15. Tìm UCLN của 2 số nguyên dương
| int UCLN(int c, int b){ if (c == b) return c; if (c > b) return UCLN(c – b, b); else return UCLN(c, b – c); } |
