Giáo trình Tin học cơ sở - Kỹ thuật lập trình đệ quy cơ bản

Link tải luận văn miễn phí cho ae Kết Nối
1. Tổng quan về đệ quy
1.1. Khái niệm
Vấn đề đệ quy là vấn đề được định nghĩa bằng chính nó. Ngoài ra, hai điều kiện quan trọng để có
thể giải bài toán bằng đệ quy là bài toán tồn tại bước đệ quy và phải có điều kiện dừng.
Ví dụ: Tính S(n) = 1 + 2 + 3 + … + (n – 1) + n
Ta nhận thấy: 1 + 2 + 3 + … + (n – 1) = S(n – 1)  S(n) = S(n – 1) + n
Hơn nữa, S(0) = 0.
Vậy, bài toán tồn tại bước đệ quy và có điều kiện dừng.
1.2. Hai bước giải bài toán đệ quy
Bước 1 – Phân tích: Phân tích bài toán thành bài toán đồng dạng nhưng đơn giản hơn và dừng
lại ở bài toán đồng dạng đơn giản nhất có thể xác định ngay kết quả.
Bước 2 – Thế ngược: Xác định kết quả bài toán đồng dạng từ đơn giản đến phức tạp để có kết
quả cuối cùng.
2. Hàm đệ quy trong ngôn ngữ lập trình C
2.1. Khái niệm
Một hàm được gọi là đệ quy nếu bên trong thân của hàm đó có lời gọi hàm lại chính nó một cách
trực tiếp hay gián tiếp.
Đệ quy trực tiếp Đê quy gián tiếpTrang 2 NHẬP MÔN LẬP TRÌNH
Bộ môn Tin học cơ sở Tháng 10 – 2009
2.2. Cấu trúc hàm đệ quy
Một hàm thông thường gồm 2 phần sau:
()
{
if (<Điều kiện dừng>)
{
… return ;
}

Phần dừng (base step): phần khởi tính
toán hay điểm kết thúc của thuật toán và
không chứa phần đang định nghĩa.
… Lời gọi hàm
…

Phần đệ quy (recursion step): phần sử
dụng thuật toán đang được định nghĩa.
}
2.3. Phân loại
2.3.1. Đệ quy tuyến tính
Trong thân hàm có duy nhất một lời gọi hàm gọi lại chính nó một cách tường minh.
Cấu trúc hàm:
()
{
if (<Điều kiện dừng>)
{
… return ;
} …
(<Đối số>); …
}
Ví dụ:
Tính S(n) = 1 + 2 + … + n
 S(n) = S(n – 1) + n
 Điều kiện dừng: S(0) = 0
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiTrang 3 NHẬP MÔN LẬP TRÌNH
Bộ môn Tin học cơ sở Tháng 10 – 2009
long Tong(int n)
{
if (n == 0)
return 0;
return Tong(n–1) + n;
}
2.3.2. Đệ quy nhị phân
Trong thân hàm có hai lời gọi hàm gọi lại chính nó một cách tường minh.
Cấu trúc hàm:
()
{
if (<Điều kiện dừng>)
{
… return ;
} …
(<Đối số>); …
… (<Đối số>); …
}
Ví dụ:
Tính số hạng thứ n của dãy Fibonacy
 f(0) = f(1) = 1 và f(n) = f(n – 1) + f(n – 2) n > 1
 Điều kiện dừng: f(0) = 1 và f(1) = 1
long Fibo(int n)
{
if (n == 0 || n == 1)
return 1;
return Fibo(n–1)+Fibo(n–2);
}Trang 4 NHẬP MÔN LẬP TRÌNH
Bộ môn Tin học cơ sở Tháng 10 – 2009
2.3.3. Đệ quy hỗ tương
Trong thân hàm này có lời gọi hàm tới hàm kia và bên trong thân hàm kia có lời gọi hàm tới hàm
này.
Cấu trúc hàm:
()
{
if (<Điều kiện dừng>)
{
… return ;
} …
(<Đối số>); …
}
()
{
if (<Điều kiện dừng>)
{
… return ;
} …
(<Đối số>); …
}
Ví dụ:
Tính số hạng thứ n của dãy sau:
x(0) = 1, y(0) = 0
x(n) = x(n – 1) + y(n – 1)
y(n) = 3*x(n – 1) + 2*y(n – 1)
 Điều kiện dừng: x(0) = 1, y(0) = 0


Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:

You must be registered for see links

Admin ơi, cho mình xin tài liệu này với,

Download miễn phí Giáo trình Tin học cơ sở - Kỹ thuật lập trình đệ quy cơ bản, [email protected]​

Trích dẫn từ dqtuan88:

Admin ơi, cho mình xin tài liệu này với,

Download miễn phí Giáo trình Tin học cơ sở - Kỹ thuật lập trình đệ quy cơ bản, [email protected]​

Click to expand...

Link mới update, mời bạn xem lại bài đầu