{"id":23528,"date":"2023-01-28T14:19:08","date_gmt":"2023-01-28T07:19:08","guid":{"rendered":"https:\/\/kiencang.net\/?p=23528"},"modified":"2023-08-26T18:08:39","modified_gmt":"2023-08-26T11:08:39","slug":"de-quy-trong-lap-trinh","status":"publish","type":"post","link":"https:\/\/kiencang.net\/de-quy-trong-lap-trinh\/","title":{"rendered":"Hi\u1ec3u th\u00eam v\u1ec1 \u0111\u1ec7 quy th\u00f4ng qua m\u1ed9t s\u1ed1 v\u00ed d\u1ee5 [serial v\u1ec1 c\u00e1c thu\u1eadt to\u00e1n c\u01a1 b\u1ea3n trong l\u1eadp tr\u00ecnh]"},"content":{"rendered":"\n
\u1ede trong hai b\u00e0i vi\u1ebft tr\u01b0\u1edbc v\u1ec1 s\u1eafp x\u1ebfp tr\u1ed9n (merge sort)<\/a> v\u00e0 s\u1eafp x\u1ebfp nhanh (quick sort)<\/a>, ch\u00fang ta \u0111\u00e3 th\u1ea5y \u0111\u01b0\u1ee3c s\u1ee9c m\u1ea1nh c\u1ee7a \u0111\u1ec7 quy (recursion), \u0111\u1eb7c bi\u1ec7t l\u00e0 v\u1edbi s\u1eafp x\u1ebfp nhanh, khi hi\u1ec7u su\u1ea5t c\u1ee7a n\u00f3 l\u00e0 v\u01b0\u1ee3t tr\u1ed9i, \u0111i\u1ec1u r\u1ea5t quan tr\u1ecdng khi x\u1eed l\u00fd d\u1eef li\u1ec7u l\u1edbn.<\/p>\n\n\n\n Tuy nhi\u00ean \u0111\u1ec7 quy kh\u00f4ng qu\u00e1 d\u1ec5 hi\u1ec3u, v\u00e0 t\u00f4i hy v\u1ecdng qua b\u00e0i vi\u1ebft n\u00e0y ch\u00fang ta s\u1ebd nh\u00ecn r\u00f5 h\u01a1n v\u1ec1 n\u00f3.<\/p>\n\n\n\n T\u1ed5ng qu\u00e1t, m\u1ed9t b\u00e0i to\u00e1n \u0111\u01b0\u1ee3c gi\u1ea3i quy\u1ebft b\u1eb1ng \u0111\u1ec7 quy n\u1ebfu n\u00f3 c\u00f3 hai \u0111\u1eb7c \u0111i\u1ec3m sau:<\/p>\n\n\n\n Ch\u00fang ta s\u1ebd ph\u1ea3i nh\u1eafc l\u1ea1i m\u1ed9t v\u00ed d\u1ee5 kinh \u0111i\u1ec3n v\u1ec1 \u0111\u1ec7 quy, \u0111\u00f3 l\u00e0 t\u00ednh giai th\u1eeba c\u1ee7a m\u1ed9t s\u1ed1 t\u1ef1 nhi\u00ean n. <\/p>\n\n\n\n Ch\u00fang ta bi\u1ebft c\u00f4ng th\u1ee9c c\u1ee7a n\u00f3 nh\u01b0 sau:<\/p>\n\n\n\n Nh\u01b0 v\u1eady b\u00e0i to\u00e1n l\u1edbn n! t\u00ednh \u0111\u01b0\u1ee3c th\u00f4ng qua b\u00e0i to\u00e1n nh\u1ecf h\u01a1n l\u00e0 (n-1)!, c\u1ee5 th\u1ec3:<\/p>\n\n\n\n V\u00e0 c\u0169ng v\u1eady (n-1)! t\u00ednh \u0111\u01b0\u1ee3c th\u00f4ng qua (n-2)!<\/p>\n\n\n\n \u0110\u00e2y ch\u00ednh l\u00e0 t\u00ednh \u0111\u1ec7 quy.<\/p>\n\n\n\n C\u00f2n \u0111i\u1ec3m d\u1eebng c\u1ee7a \u0111\u1ec7 quy n\u00e0y, gi\u00fap cho qu\u00e1 tr\u00ecnh truy h\u1ed3i k\u1ebft th\u00fac ch\u00ednh l\u00e0 khi n = 0, v\u00e0 ch\u00fang ta bi\u1ebft gi\u00e1 tr\u1ecb c\u1ee7a \u0111i\u1ec3m d\u1eebng \u0111\u00f3 l\u00e0 1.<\/p>\n\n\n\n Th\u1ec3 hi\u1ec7n trong m\u1ed9t ng\u00f4n ng\u1eef l\u1eadp tr\u00ecnh, v\u00ed d\u1ee5 PHP, n\u00f3 s\u1ebd tr\u00f4ng gi\u1ed1ng nh\u01b0 d\u01b0\u1edbi \u0111\u00e2y:<\/p>\n\n\n\n Nh\u01b0 v\u1eady \u0111o\u1ea1n m\u00e3 trong l\u1eadp tr\u00ecnh c\u0169ng s\u1ebd ph\u1ea3n \u00e1nh t\u00ednh ch\u1ea5t c\u1ee7a \u0111\u1ec7 quy, n\u00f3 g\u1ed3m hai ph\u1ea7n:<\/p>\n\n\n\n Ti\u1ebfp theo ch\u00fang ta s\u1ebd n\u00f3i v\u1ec1 d\u00e3y s\u1ed1 Fibonacci, m\u1ed9t v\u00ed d\u1ee5 d\u1ec5 hi\u1ec3u kh\u00e1c v\u1ec1 kh\u1ea3 n\u0103ng \u0111\u1ec7 quy.<\/p>\n\n\n\n Ch\u00fang ta bi\u1ebft r\u1eb1ng c\u00f4ng th\u1ee9c t\u00ednh c\u1ee7a m\u1ed9t s\u1ed1 Fibonacci l\u00e0 nh\u01b0 sau:<\/p>\n\n\n\n \u0110o\u1ea1n m\u00e3 PHP \u0111\u1ec3 gi\u1ea3i quy\u1ebft b\u00e0i to\u00e1n n\u00e0y:<\/p>\n\n\n\n Gi\u1edbi l\u1eadp tr\u00ecnh th\u01b0\u1eddng c\u1ea3nh b\u00e1o l\u00e0 ph\u1ea3i h\u1ebft s\u1ee9c th\u1eadn tr\u1ecdng khi vi\u1ebft m\u00e3 s\u1eed d\u1ee5ng thu\u1eadt to\u00e1n \u0111\u1ec7 quy \u0111\u1eb7c bi\u1ec7t khi x\u1eed l\u00fd d\u1eef li\u1ec7u l\u1edbn, ph\u1ee9c t\u1ea1p. <\/p>\n\n\n\n S\u1edf d\u0129 nh\u01b0 v\u1eady v\u00ec qu\u00e1 tr\u00ecnh \u0111\u1ec7 quy s\u1eed d\u1ee5ng nhi\u1ec1u b\u1ed9 nh\u1edb \u0111\u1ec3 l\u00e0m \u0111\u1ec7m trong qu\u00e1 tr\u00ecnh truy h\u1ed3i, do v\u1eady n\u1ebfu kh\u00f4ng kh\u00e9o, n\u00f3 s\u1ebd l\u00e0m tr\u00e0n b\u1ed9 nh\u1edb (stack overflow), c\u00e1i v\u1ed1n lu\u00f4n h\u1eefu h\u1ea1n v\u1edbi b\u1ea5t c\u1ee9 h\u1ec7 th\u1ed1ng t\u00ednh to\u00e1n n\u00e0o. <\/p>\n\n\n\n V\u00e0 khi b\u1ecb stack overflow, ch\u01b0\u01a1ng tr\u00ecnh s\u1ebd d\u1eebng ho\u1eb7c b\u1ecb treo (crash), v\u00e0 t\u1ea5t nhi\u00ean, ch\u01b0\u01a1ng tr\u00ecnh s\u1ebd kh\u00f4ng ho\u1ea1t \u0111\u1ed9ng nh\u01b0 ch\u00fang ta mong mu\u1ed1n.<\/p>\n","protected":false},"excerpt":{"rendered":" \u1ede trong hai b\u00e0i vi\u1ebft tr\u01b0\u1edbc v\u1ec1 s\u1eafp x\u1ebfp tr\u1ed9n (merge sort) v\u00e0 s\u1eafp x\u1ebfp nhanh (quick sort), ch\u00fang ta \u0111\u00e3 th\u1ea5y \u0111\u01b0\u1ee3c s\u1ee9c m\u1ea1nh c\u1ee7a \u0111\u1ec7 quy (recursion), \u0111\u1eb7c bi\u1ec7t l\u00e0 v\u1edbi s\u1eafp x\u1ebfp nhanh, khi hi\u1ec7u su\u1ea5t c\u1ee7a n\u00f3 l\u00e0 v\u01b0\u1ee3t tr\u1ed9i, \u0111i\u1ec1u r\u1ea5t quan tr\u1ecdng khi x\u1eed l\u00fd d\u1eef li\u1ec7u l\u1edbn. Tuy …<\/p>\n","protected":false},"author":1,"featured_media":24641,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[333],"tags":[336],"yoast_head":"\n\n
\n
n! = n * (n-1)!<\/code><\/pre>\n\n\n\n
(n-1)! = (n-1) * (n-2)!<\/code><\/pre>\n\n\n\n
function factorial($n){\n if($n == 0){\n return 1;\n }\n else{\n return $n * factorial($n-1);\n }\n}\n\necho factorial(6); \/\/ Output: 720<\/code><\/pre>\n\n\n\n
\n
if($n == 0){\n return 1;\n}<\/code><\/pre>\n\n\n\n
\n
return $n * factorial($n-1);<\/code><\/pre>\n\n\n\n
\n\n\n\n\n
function fibonacci($n) {\n if ($n == 0 || $n == 1) {\n return $n;\n }\n return fibonacci($n - 1) + fibonacci($n - 2);\n}\n<\/code><\/pre>\n\n\n\n
\n\n\n\nL\u1ed7i stack overflow<\/h2>\n\n\n\n