Kỹ thuật lập trình đệ quy

Trường Đại học Khoa học Tự nhiên

Khoa Công nghệ thông tin

Bộ môn Tin học cơ sở

1

Đặng Bình Phương

[email protected]

NHẬP MÔN LẬP TRÌNH

KỸ THUẬT LẬP TRÌNH

ĐỆ QUY

VC

&

BB

2

Nội dung

NMLT - Kỹ thuật lập trình đệ quy

1 Tổng quan về đệ quy

2 Các vấn đề đệ quy thông dụng

3 Phân tích giải thuật & khử đệ quy

4 Các bài toán kinh điển

VC

&

BB

3

Bài toán

Cho S(n) = 1 + 2 + 3 + … + n

=>S(10)? S(11)?

NMLT - Kỹ thuật lập trình đệ quy

1 + 2 + … + 10

1 + 2 + … + 10

= 55

1 + 2 + … + 10 + 11 = 66

=

=

S(10)

S(11)

1 + 2 + … + 10

= S(10) + 11

= 55 + 11 = 66

S(10)

+ 11

55

+ 11

VC

&

BB

4

2 bước giải bài toán

NMLT - Kỹ thuật lập trình đệ quy

S(n) = S(n-1) + n

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

… = … + …

S(1) = S(0) + 1

S(0) = 0

Bước 1. Phân tích

P

hân tích thành bài toán đồng

dạng nhưng đơn giản hơn.

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

 Kết quả cuối cùng.