tailieunhanh - Kỹ thuật đệ qui

Nội dung của tài liệu trình bày về kỹ thuật lập trình đệ qui, khái niệm về chương trình đệ qui, các dạng chương trình đệ qui, theo dõi hoạt động của chương trình đệ qui, một số bài toán đệ qui thông dụng và một số ứng dụng khác. | KYÕ THUAÄT ÑEÄ QUI Kyõ thuaät laäp trình ñeä qui coù yù nghóa raát lôùn trong khoa hoïc maùy tính, coù raát nhieàu thuaät toaùn ñoøi hoûi caøi ñaët raát phöùc taïp vaø caàu kyø neáu khoâng duøng kyõ thuaät ñeä qui. Ñoái vôùi moät soá thuaät toaùn do baûn chaát töï nhieân cuûa chuùng ñaõ mang tính ñeä qui, vieäc caøi ñaët ñeä qui laø goïn vaø ñeïp nhaát. Khuyeát ñieåm lôùn nhaát cuûa kyõ thuaät ñeä qui laø: lôøi giaûi ñeä qui cho moät soá baøi toaùn coù theå bò chaïy raát chaäm do söï buøng noã toå hôïp. I. KHAÙI NIEÄM VEÀ CHÖÔNG TRÌNH ÑEÄ QUI Moät thuû tuïc (hay haøm) ñöôïc goïi laø coù tính ñeä qui neáu trong thaân cuûa thuû tuïc (hay haøm) ñoù coù leänh goïi laïi chính noù moät caùch töôøng minh hay tieàm aån. Ví duï 1. Vôùi n laø soá nguyeân khoâng aâm, ta ñònh nghóa n! nhö sau: 0!=1, n!=n.(n-1)! neáu n≥1. Haõy caøi ñaët chöông trình tính n!. Ñaây laø moät ví duï coù theå caøi ñaët deã daøng baèng phöông phaùp thoâng thöôøng, tuy nhieân neáu döïa vaøo ñònh nghóa cuûa n! chuùng ta coù theå caøi ñaët moät caùch töï nhieân baèng phöông phaùp ñeä qui nhö sau. long GiaiThua(int n) /* n >= 0 */ { long ret; /* gia tri traû veà cuûa haøm */ if(n==0) /* ñieàu kieän kieän döøng */ ret = 1; else ret = n*GiaiThua(n-1); /* goïi laïi chính noù */ return ret; } Ñoái vôùi ví duï naày, caùch caøi ñaët baèng ñeä qui raát töï nhieân vaø ñôn giaûn nhöng khoâng phaûi laø caùch caøi ñaët hay nhaát. Chuù yù raèng baát kyø haøm ñeä qui naøo cuõng phaûi coù ñieàu kieän döøng, ñieàu kieän naày seõ keát thuùc quaù trình ñeä qui baèng moät ñoaïn maõ chöông trình ñöôïc vieát theo loái thoâng thöôøng. Caâu leänh if(n==0). trong ví duï treân laø ñieàu kieän döøng cuûa haøm GiaiThua. Ví duï 2. Haøm tính caên baäc 3 cuûa moät soá thöïc coù theå caøi ñaët ñeä qui theo hai haøm exp vaø log (haøm logarithm ln(x)) nhôø vaøo nhaän xeùt sau ñaây: x > 0 : 3 x = e ln ( x ) / 3 x = 0: 3 x = 0 x #include double sqrt3(double x) { double ret; if(x==0) /* ñieàu kieän döøng */ ret = .