Lập trình C: Đệ quy (Recursion)


Đăng ký nhận thông báo về những video mới nhất

Ngôn ngữ C cho phép hàm gọi đến chính nó, người ta gọi phương pháp này là phương pháp đệ quy hoặc quay lui (xem thêm bài viết Đệ quy và giải thuật đệ quy).

Cú pháp:

Kiểu_trả_về  Tên_hàm(Danh_sách_tham_số){
    if(Điều_kiện_dừng_thỏa)
        return Giá_trị;
    else
        return Tên_hàm(Danh_sách_đối_số) Phép_toán Tên_đối_số;
}

* Thường những hàm có kiểu dữ liệu trả về khác kiểu void mới sử dụng được đệ quy (trừ trường hợp ta muốn lặp lại các lệnh tuần tự của hàm thì ta mới dùng đến kiểu void).

* Trong giải thuật này phải có một Điều_kiện_dừng_thỏa để đệ quy kết thúc (dừng quay lui).

* Phép_toán ở đây là một phép toán bất kỳ phù hợp với bài toán của bạn.

* Chương trình sử dụng đệ quy thì dễ hiểu nhưng hao tốn tài nguyên CPU, dẫn đến làm giảm thời gian chạy chương trình đi nhiều nếu số lần đệ quy của hàm lớn.

Ví dụ 1:

Tính tổng các số chia hết cho 5 nằm trong đoạn [0,N] với N được nhập từ bàn phím.

Phân tích: Điều kiện dừng thỏa ở đây ta có thể thấy được ngay là khi giá trị của đối số bằng 0 (nếu ta chạy ngược giảm dần từ N) hoặc bằng N (nếu ta chạy xuôi tăng dần từ 0). Vì chỉ tính tổng các số chia hết cho 5 nên cứ mỗi lần đệ quy thì ta lại giảm (hoặc tăng) giá trị của đối số 5 đơn vị rồi tiến hành cộng dồn.

Chương trình được viết như sau:

#include<stdio.h>

long tinhTong(int N) {
  if(N<=0) //nếu N==0
  return 0; //thì dng đ quy
  else //nếu không thì

  return tinhTong(N-1) + N; //tiếp tc đ quy
}

main() {
  int N;
  do { //tiến hành nhp N
    printf("\nMoi nhap N: ");
    scanf("%d", &N);
  }while(N<1); //N phi là t 1 tr lên mi hp l  printf("\nTong cac so tu 1 den %d la: %ld", N, tinhTong(N)); //tiến hành đ quy

  return 0;
}

Kết quả:

Đệ quy - tổng các số chia hết cho 5 

Ví dụ 2:

Ta có thể lập trình tính giai thừa theo phương pháp đệ quy, vì n!=1*2*3*…(n-1)*n  hay n!=n*(n-1)*(n-2)*…*1 --> Giá trị sau chính là giá trị trước cộng thêm 1 (hoặc là giá trị trước trừ đi 1), giá trị kết thúc =1.

Sau đây là phần demo:

#include <stdio.h>

long giaiThua(int n) {
  if(n==0)    //điu kin dng tha
    return 1; //vì 0!=1 nên n==0 là v trí kết thúc ca đ quy
  return n*giaiThua(n - 1); //kiu n*(n-1)*(n-2)…*1
  }                 //hoc: giaiThua(n-1)*n vi kiu 1*2*3*…*n

main() {
  int n;
  printf("Nhap n: ");
  scanf("%d", &n);
  printf("Giai thua cua %d la %ld", n, giaiThua(n));

  return 0;
}

Ví dụ 3:

In ra n phần tử đầu tiên của dãy Fibonanci (1 1 2 3 5 8 13 21 34 …).

Phân tích: Hai phần tử đầu tiên của dãy là hai phần tử khởi tạo (1 1), bắt đầu từ phần tử thứ ba trở đi sẽ tuân theo quy tắc là phần tử sau bằng tổng của hai phần tử ngay trước nó cộng lại (ví dụ 13=5+8). Công thức: n= (n-1) + (n-2). Như vậy có nghĩa ta sẽ sử dụng được phương pháp đệ quy vì nó tuân theo cú pháp đệ quy.

Chương trình được viết như sau:

#include<stdio.h>

int fibo(int n) {
  if(n==0 || n==1) //nếu là hai phn t đu tiên ca dãy (điu kin dng tha)
    return 1;      //thì s có giá tr là 1
  return fibo(n-1) + fibo(n-2); //nếu không thì tính giá tr ca phn t đó
}

main() {
  int n, i;
  float;
  printf("\nNhap so phan tu can xem cua day Fibonacci: ");
  scanf("%d", &n);
  printf("\n%d phan tu dau tien cua day la:\n\n", n);
  for(i=0; i<n; i++)
    printf("%d ", fibo(i));

  return 0;
}

Kết quả:

Đệ quy - Fibonancy


Nếu bạn có điều thắc mắc, bạn hãy comment cho V1Study để được giải đáp.
Bài viết này được chia sẻ bởi LongDT. Nếu bạn muốn chia sẻ bài viết, bạn hãy Đăng ký làm thành viên!
« Prev
Next »
Copied !!!