Đệ Quy Trong Lập Trình C

Khái niêm chung về đệ quy

C không những cho phép hàm này gọi tới hàm khác, mà nó còn cho phép từ một điểm trong thân của một hàm gọi chính hàm đó. Hàm như vậy gọi là đệ quy. Vậy một chương trình sẽ chạy thế nào nếu như áp dụng đệ quy ? Cùng tham khảo ở phần dưới đây nhé

Cách dùng đệ quy

Phương pháp đệ quy thường áp dụng cho các bài toán phụ thuộc tham số có 2 đặc điểm sau :

• Bài toán dễ dàng giải quyết trong một số trường hợp riêng ứng với các giá trị đặc biệt của tham số. Ta gọi đây là trường hợp suy biến.
• Trong trường hợp tổng quát, bài toán có thể quy về một bài toán cùng dạng nhưng giá trị tham số thì bị thay đổi. Và saiu một số hữu hạn các bước biến đổi đệ quy, sẽ dẫn đến trường hợp suy biến.

Các ví dụ về đệ quy

Mục này sẽ trình bày một số ví dụ đơn giản nhằm minh họa một cách dễ hiểu hàm đệ quy Ví dụ 1 : Xét bài toán tìm USCLN của 2 số nguyên dương a,b+ Trường hợp suy biến là trường hợp a=b USCLN(a,b)=a. + Trường hợp x khác y thì có thể đệ quy như sau :USCLN(a,b)=USCLN(a-b,b) nếu a>b USCLN(a,b)=USCLN(a,b-a) nếu a<b Hàm tìm USCLN áp dụng đệ quy được viết như sau :

int USCLN(int a, int b) { if (a==b) return a; else if (a>b) return USCLN(a-b,b); else return USCLN(a,b-a); }

Ví dụ 2 : Tính giai thừa của NTa nhận thấy rằng N! có thể tính theo công thức đệ quy như sau :n!=1 nếu n=0n!=n*(n-1)! nếu n>0Dựa vào công thức trên ta có thể xây dựng hàm tính n! bằng cách đệ quy như sau :

long GT(int n) { if (n==0 || n == 1) return(1); else return(n*GT(n-1)); }

Cơ chế hoạt động

Lần gọi đầu tiên tới hàm GT sẽ được gọi từ hàm main. Máy sẽ tạo ra một tập các biến tự động của hàm GT. Máy sẽ tạo ra một tập các biến tự động của hàm . Giá trị của tham số được gáng cho n thứ nhất có giá trị là n . Kiểm tra lệnh if nếu khác 1 và khác 0 thì bắt đầu lựa câu lệnh dưới else . Theo câu lệnh này máy sẽ tính biểu thức x*(GT(x-1))Để tính biểu thức, ta gọi lại chính hàm GT, lần thứ 2 này giá trị sẽ giảm đi và có giá trị mới là n-1, tiếp tục kiểm tra điều kiện cho đến khi lệnh if thỏa mãn thì return(1) Bắt đầu từ đây, máy sẽ lần lượt thực hiện n lần ra khỏi vòng lặp. Lần ra thứ nhất tương ứng với lần vào thứ n, hàm cho giá trị GT(1)=1 máy trở về xét biểu thức n*GT(1)n hiểu là n thứ n-1 . Biểu thức trên có giá trị 2*1=2 sau đó máy trả về với biểu thức n*GT(2) Ta để ý rằng lần ra thứ n tương ứng với lần vào thứ 1. Tiếp tục tính biểu thức rồi trả vê cho đến khi thoát khỏi vòng lặp.Nhận xét : Qua ví dụ trên ta thấy một hàm đệ quy dùng nhiều vùng nhớ trên ngăn xếp và có thể dẫn dến tràn ngăn xếp. Vì vậy với một bài toán có cách giải lập thì nên chọn cách giải này . 2 ví dụ trên là những bài đơn giản giúp chúng ta dễ dàng hiểu về đệ quy, ngoài ra các bạn cũng có thể tìm hiểu thêm 1 số bài từ cơ bản đến nâng cao để hiểu sâu hơn nhé ( Tháp đồng hồ, tổ hợp, chỉnh hợp,…)

Chia sẻ:

• X
• Facebook

Thích Đang tải...

Có liên quan