KỸ THUẬT LẬP TRÌNH (p7) pps

0

KỸ THUẬT LẬP TRÌNH

KỸ THUẬT PHÁT TRIỂN CHƯƠNG TRÌNH

NỘI DUNG

ƒ Hàm và Thủ tục

ƒ Phát triển chương trình bằng phương pháp tinh

chỉnh dần từng bước.

ƒ Định nghĩa và sử dụng hàm trong ngôn ngữ C

ƒ Hàm đệ quy

1

KHÁI NIỆM ĐỆ QUY

? Sức mạnh của đệ quy là gì?

ƒ Lời giải của bài toán T gọi là đệ quy nếu nó được thực

hiện bằng lời giải của bài toán T’ có dạng giống T

ƒ Giải thuật tương ứng với lời giải đệ quy gọi là giải thuật

đệ quy.

ƒ Biểu diễn giải thuật đệ quy: trong chương trình cần có

thủ tục hay chương trình con.

• Đệ quy trực tiếp: trong thủ tục P có chứa lời gọi đến chính nó

• Đệ quy gián tiếp: trong thủ tục P có lời gọi thủ tục Q và trong Q

có lời gọi đến P.

• Cần xác định tình huống, điều kiện để kết thúc đệ quy.

2

ƒ Ví dụ 1. Hàm tính giai thừa

• 5! = 5 * 4 * 3 * 2 * 1

• Chú ý rằng:

– 5! = 5 * 4!

– 4! = 4 * 3! ...

• Có thể thực hiện gọi đệ qui

• Điều kiện kết thúc gọi đệ qui: 1! = 0! = 1

– 2! = 2 * 1! = 2 * 1 = 2;

– 3! = 3 * 2! = 3 * 2 = 6;

3

ƒ ? Bài toán nào có thể dùng đệ quy?

ƒ Hàm đệ quy thường được viết theo thuật toán sau:

if (trường hợp suy biến) {

Lời giải bài toán trong trường hợp suy biến;

}

else {

Gọi đệ quy tới hàm với giá trị khác của tham số;

}