Báo cáo khoa học: Đệ quy và các ph-ơng pháp khử đệ quy

Đệ quy là công cụ mạnh trong tin học để lập trình các bài toán khó. Tuy nhiên các hàm đệ quy th-ờng đòi hỏi bộ nhớ lớn, vì vậy vấn đề khử đệ quy là rất cần thiết. Trong báo cáo này trình bầy cấu trúc, nguyên lý hoạt động của hàm đệ quy và cách xây dựng một hàm không đệ quy t-ơng ứng. So với các ph-ơng pháp khử đệ quy đã biết, thì mô hình trình bầy ở đây đơn giản và dễ dàng áp dụng hơn....
Nội dung trích xuất từ tài liệu:
Báo cáo khoa học: "Đệ quy và các ph-ơng pháp khử đệ quy" §Ö quy vμ c¸c ph−¬ng ph¸p khö ®Ö quy PGS. TS. Ph¹m v¨n Êt Khoa C«ng nghÖ th«ng tin - Tr−êng §H GTVT Tãm t¾t: §Ö quy lμ c«ng cô m¹nh trong tin häc ®Ó lËp tr×nh c¸c bμi to¸n khã. Tuy nhiªn c¸c hμm ®Ö quy th−êng ®ßi hái bé nhí lín, v× vËy vÊn ®Ò khö ®Ö quy lμ rÊt cÇn thiÕt. Trong b¸o c¸o nμy tr×nh bÇy cÊu tróc, nguyªn lý ho¹t ®éng cña hμm ®Ö quy vμ c¸ch x©y dùng mét hμm kh«ng ®Ö quy t−¬ng øng. So víi c¸c ph−¬ng ph¸p khö ®Ö quy ®· biÕt, th× m« h×nh tr×nh bÇy ë ®©y ®¬n gi¶n vμ dÔ dμng ¸p dông h¬n. Summary: The recursive is a powerfull tool for programming difficult problems. However the recursion functions offen demand a larger memory, so the recursive removal is very neccessary. In this paper, we will present the structure and the activity of recursion functions and a method of creating a corresponding non recursion function. This method is simpler and easier to apply compared with known methods. {i. CÊu tróc cña hμm ®Ö quy in x2 // phÐp to¸n c¬ b¶n Hµm ®Ö quy gåm 2 phÇn: P(x-1) // Lêi gäi §Q thø 1 + PhÇn suy biÕn gåm mét dÉy c¸c c©u in x // phÐp to¸n c¬ b¶nlÖnh vµ kh«ng chøa c¸c lêi gäi ®Ö quy. P(x-1) // Lêi gäi §Q cuèi + PhÇn tæng qu¸t còng bao gåm nhiÒu in 1 // phÐp to¸n c¬ b¶nc©u lÖnh, nh−ng bao gåm mét hoÆc nhiÒu lêigäi ®Ö quy (gäi tíi chÝnh hµm ®ang xÐt). } D−íi ®©y, sÏ gäi c¸c c©u lÖnh kh«ng }chøa lêi gäi ®Ö quy lµ c¸c phÐp to¸n c¬ b¶n. VÝ dô xÐt hµm sau: ii. Nguyªn lý ho¹t ®éng void P(x) // x nguyªn d−¬ng 2.1. Tr−íc khi b¾t ®Çu ch−¬ng trinh { §Æt mét dÊu hiÖu ®Æc biÖt vµo ng¨n xÕp if(x==1) // Suy biÕn - kh«ng cã lêi gäi ®Ö (vÝ dô k = 0) lµm dÊu hiÖu kÕt thóc hµmquy 2.2. C¸ch xö lý lêi gäi ®Ö quy // chØ gåm c¸c phÐp to¸n c¬ b¶n 2.2.1. §Æt gi¸ trÞ hiÖn t¹i cña ®èi vµo { ng¨n xÕp (®Ó sau nµy lÊy ra dïng). in 8 // phÐp to¸n c¬ b¶n 2.2.2. §Æt mét dÊu hiÖu vµo ng¨n xÕp (®Ó } sau nµy biÕt lèi trë vÒ - trë vÒ sau lêi gäi ®Ö quy nµo). else // Tæng qu¸t, sÏ cã c¸c lêi gäi ®Ö quy 2.2.3. C¨n cø vµo tham sè lêi gäi ®Ö quy ....®Ó thay ®æi gi¸ trÞ cña ®èi. else if(k==m) // trá vÒ tõ lêi gäi cuèi 2.2.4. NhÈy (trë vÒ) ®Çu hµm. { 2.3. PhÇn suy biÕn - trë vÒ 1. C¸c c©u lÖnh sau lêi gäi §Q m 2.3.1. Xö lý c¸c phÐp to¸n c¬ b¶n. 2. LÊy gi¸ trÞ cña ®èi (x) vµ dÊu hiÖu (k) tõ ®Ønh ng¨n xÐp 2.3.2. LÊy gi¸ trÞ cña ®èi (x) vµ dÊu hiÖu(k) tõ ®Ønh ng¨n xÐp. 3. NhÈy tíi ®o¹n ch−¬ng tr×nh xö lý trë vÒ (Goto 2.4.2) 2.3.3. NhÈy tíi ®o¹n ch−¬ng tr×nh xö lýtrë vÒ (xem 2.4). } 2.4. PhÇn tæng qu¸t - sÏ gÆp c¸c lêigäi ®Ö quy iii. tæ chøc hμm kh«ng ®Ö quy 2.4.1. Xö lý c¸c phÐp to¸n c¬ b¶n. 3.1. Hç trî 2.4.2. Xö lý lêi gäi ®Ö quy ®Çu tiªn gÆp CÇn t¹o mét ng¨n xÕp vµ x©y dùng c¸cph¶i. phÐp to¸n: 2.5. §o¹n ch−¬ng tr×nh xö lý trë vÒ a. push(x,k) ®Ó ®−a ®èi x vµ dÊu hiÖu k lªn ng¨n xÕp. 2.5.1. Dùa vµo gi¸ trÞ cña k ®Ó ph©n biÖt3 tr−êng hîp. b. pop(x,k) ®Ó lÊy ®èi x vµ dÊu hiÖu k tõ ®Ønh ng¨n xÕp. a. KÕt thóc hµm (k=0) b. Trë vÒ tõ lêi ...