Tham khảo tài liệu 'kỹ thuật lập trình - khái niệm đệ quy', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 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 Ví dụ 1. Hàm tính giai thừa 51 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 r 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. I __11 i 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ố 3 ví DỤ VỀ CHƯƠNG TRÌNH ĐỆ QUY Ví dụ 1. Hàm giai thừa Facin 1 if n 0 n Facfi -1 if n 0 function Fac i integer integer begin if i 1 then Fac 1 else Fac i Fac i - 1 end J 1 4 1 Fig. 2 Recursive factorial function 3 include 4 5 long factorial long number function prototype 6 7 function main begins program execution 8 int mainO 9 10 int i counter 11 12 loop 10 times. During each iteration calculate 13 factor al i and display result 14 for 1 i 10 15 printfC 2d ld n i factor al 16 end for 17 18 return 0 indicates successful termination 19 20 end main 21 II 5 ị iizillll p4 Il L__I1 . Fin a I value 120 I 5 5 5 24 120 is returned 5 y Ị j 4 4 6 24 is returned Ị-ỷv-yy 5 3 3 2 6 is re tu med ịỷ vyy -----2 2 1 2 is returned 1T 1 returned a Sequence of recursive calls b Values returned from each recursive call. 22 recursive definition of function .
