Hàm đệ quy là gì? Hoạt động ra sao? – Freetuts

Posted on by adminChuyên mục:Kiến thức Internet

Trong bài này mình sẽ giới thiệu đến các bạn hàm đệ quy, đây là một hàm rất căn bản và được sử dụng rất nhiều trong lập trình.

test php

banquyen png

Bài viết này được đăng tại

freetuts.net

, không được copy dưới mọi hình thức.

Chúng ta sẽ cùng nhau tìm hiểu và khám phá về hàm đệ quy là gì ? Cơ chế hoạt động giải trí của nó như thế nào ? Và làm một vài ví dụ trình diễn trong ngôn từ lập trình C + + .

1. Hàm đệ quy là gì?

Một hàm được gọi là hàm đệ quy nếu trong thân hàm có một hoặc nhiều lệnh gọi đến chính hàm đó .
Đệ quy giúp xử lý bài toán theo cách nghĩ thường thì một cách tự nhiên .Bài viết này được đăng tại [ không lấy phí tuts. net ]

Đệ quy cũng tương tự như các vòng lặp, nó phải xác định được điểm dừng. Nếu không xác định chính xác điểm dừng, bài toán có thể lặp vĩnh cửu (Stack Overhead).

Ví dụ: Chúng ta có định nghĩa giai thừa của một số nguyên dương n như sau:

5! = 5 * 4!
4! = 4 * 3!
…
1! = 1 * 0!

Theo quy luật ở trên, nếu ta biết được ( n-1 ) giai thừa thì ta sẽ tính được n giai thừa : n ! = n * ( n-1 ) !

Ta thấy n = 0 hoặc n = 1 thì giai thừa luôn bằng 1, vì vậy đây chính là điểm dừng.

Công thức tổng quát của n ! như sau :

n! = 1 * 2 * 3 *…* (n-1) * n = (n-1)! * n với (0! = 1).

Áp dụng công thức trên, ta hoàn toàn có thể viết một hàm tính giai thừa của 1 số ít nguyên dương n trong C + + .

Int giaiThua(int n){
	If(n<=1) return 1;
	return n * giaiThua(n-1);
}

Điểm dừng của hàm đệ quy trên chính là n <= 1.

* Lưu ý: Bản chất của hàm đệ quy là lặp vô hạn, vì vậy nếu không có điểm dừng thì chương trình sẽ chạy liên tục và dẫn đến tràn tài nguyên.

Có rất nhiều hàm đệ quy như :

  • Đệ quy tuyến tính.
  • Đệ quy đuôi.
  • Đệ quy nhị phân.
  • Đệ quy đa tuyến.
  • Đệ quy lồng.
  • Đệ quy tương hỗ.

2. Cơ chế hoạt động của đệ quy

Cơ chế hoạt động của đệ quy tuân thủ theo LIFO (Last In First Out), hay còn được gọi là cơ chế Stack.

last in first out png

Cơ chế Stack được hiểu đơn giản là vào sau – ra trước.

Ví dụ tất cả chúng ta muốn lắp một chiếc bánh xe, thì việc tiên phong sẽ lắp bánh xe, rồi đến lắp lồng đền và sau cuối mới lắp ốc. Nhưng khi tháo ra, ta lại tháo ốc trước rồi tới lồng đền và sau cuối mới tháo bánh xe. Đây là một ví dụ thực tiễn cho những bạn dễ tưởng tượng chính sách Stack hoạt động giải trí như thế nào .
Ở những bài sau mình sẽ lý giải cụ thể chính sách hoạt động giải trí của từng hàm đệ quy, vì tất cả chúng ta có rất nhiều hàm đệ quy khác nhau. Các bạn chỉ cần hiểu đơn thuần rằng hàm đệ quy thực thi theo chính sách Stack .

Lời kết

Như vậy trong bài này tất cả chúng ta sẽ học tổng số 6 hàm đệ quy. Đây là một trong những chương cơ bản trong học phần cấu trúc tài liệu và giải thuật. Khi những bạn nắm được thực chất và cố lõi của nó, thì việc chuyển sang những ngôn từ lập trình khác là điều rất thuận tiện. Đây cũng chỉ là bài cơ bản về đệ quy, những bạn hãy xem hết những bài sau để hoàn toàn có thể nắm rõ hết toàn bộ những hàm đệ quy nhé .

admin