Đệ quy

Trịnh Tấn Đạt

Khoa CNTT - Đại Học Sài Gòn

Email: trinhtandat@sgu.edu.vn

Website: https://sites.google.com/site/ttdat88/

​

​

1

Đệ quy

• Khái niệm
• Một chương trình con có thể gọi một chương trình con khác.
• Nếu gọi chính nó thì được gọi là sự đệ quy.
• Số lần gọi này phải có giới hạn (điểm dừng)

Ví dụ

Tính S(n) = n! = 1*2*…*(n-1)*n

Ta thấy S(n) = S(n-1)*n

Vậy thay vì tính S(n) ta sẽ đi tính S(n-1)

Tương tự tính S(n-2), …, S(2), S(1), S(0) = 1

​

2

*Học sâu hơn ở môn kỹ thuật lập trình

Đệ quy

• Hai yếu tố cần để tiến hành một phương thức đệ quy là:
• Có điều kiện dừng (phần cơ sở, phần neo): Xác định quy luật của phương thức và tìm giá trị cụ thể khi thỏa mãn một điều kiện nhất định.

Nếu hàm đệ quy không có phần này thì hàm sẽ bị lặp vô hạn và sinh lỗi khi thực hiện.

• Phương thức đệ quy: Phương thức đệ quy sẽ gọi lại chính nó nhưng dành cho cấp độ thấp hơn. cho đến khi nó trả về điều kiện dừng ở bước 1.

​

S = 1+2+3+…+n

S(n)= 1+2+…+n

int sum(int n) {

if (n == 1) {

return 1;

}

else {

return sum(n - 1) + n;

}

}

4

Ví dụ

#include <iostream>

using namespace std;

void p() {

cout << "hello" << endl;

p();

}

int main() {

p();

return 0;

}

Vòng lặp vô tận

#include <iostream>

using namespace std;

int factorial(int n) {

if (n == 1) //phần neo

return 1;

else

return (n * factorial(n - 1)); // phần đệ quy

}

int main() {

cout << "Giai thua cua 5 la:" << factorial(5);

return 0;

}

Tính giai thừa n!

Đệ Quy

• Cách viết hàm đệ quy
• Định nghĩa tác vụ đệ quy thế nào thì viết hàm đệ quy như vậy. Xét 2 trường hợp neo (thực hiện không đệ quy) và trường hợp đệ quy.
• Ví dụ: Chuyển các định nghĩa sau về dạng đệ quy:
• S(n) = 1+2 +3+… + n
• S(n) = 1+1/2 + 1/3 + ... + 1/n
• S(n) = 1*2 + 2*3+ 3*4 + 4*5 +.….+ n(n+1)

Bài toán dãy số Fibonacci

• Dãy số Fibonacci:

F(n)= F(n-1)+F(n-2) (phần đệ quy)

F(n)=1 với n<=2 (phần neo).

• Hàm đệ quy tính số thứ n trong dãy số Finbonacci

Khử đệ quy

• Là quá trình chuyển đổi 1 giải thuật đệ quy thành giải thuật không đệ quy.
• Chưa có giải pháp cho việc chuyển đổi này một cách tổng quát. Ta thường khử đệ quy cho đệ quy tuyến tính.
• Cách tiếp cận:
• Dùng quan điểm đệ quy để tìm giải thuật cho bài toán.
• Mã hóa giải thuật đệ quy.
• Khử đệ quy để có giải thuật không-đệ-quy.

​

• Có 2 cách thường dùng :
• Khử đệ quy bằng vòng lặp
• Khử đệ quy dùng Stack

Khử đệ quy bằng vòng lặp

• Ý tương: Lưu lại các trị của các lần tính toán trước làm dữ liệu cho việc tính toán của lần sau.

Bài tập Viết hàm đệ quy cho các bài toán

Bài tập Viết hàm đệ quy cho các bài toán