Kỹ thuật khử đệ quy

Đệ quy là quả tim trong các nghiên cứu lý thuyết cũng như thực hành tính toán, đã thể hiện rấtnhiều sức mạnh và có ưu điểm trong nhiều bài toán. Tuy nhiên bài này tôi lại đi ngược với côngviệc chúng ta thường làm: khử đệ quy, đó là vấn đề cũng có nhiều thú vị và đáng để chúng taxem xét.
Nội dung trích xuất từ tài liệu:
Kỹ thuật khử đệ quyKỹ thuật khử đệ quy Trần Đức ThiệnĐệquylàquảtimtrongcácnghiêncứulýthuyếtcũngnhưthựchànhtínhtoán,đãthểhiệnrất nhiềusứcmạnhvàcóưuđiểmtrongnhiềubàitoán.Tuynhiênbàinàytôilạiđingượcvớicông việcchúngtathườnglàm:khửđệquy,đólàvấnđềcũngcónhiềuthúvịvàđángđểchúngta xemxét.Khửđệquyởđâylàbiếnmộtthủtụcđệquythànhmộtthủtụcchỉchứavònglặpmàkhôngảnhhưởnggìđếncácyếutốkhác,chứkhôngphảilàthayđổithuậttoán.Vídụnhưtrongcáchàmđệquytínhn!vàsốFibonaciF(n)tacóthểthaybằngmộtvònglặpđểtính;Đókhôngphảilàphươngphápkhửđệquymàtôimuốnnói.Trongtrườnghợptổngquát,khửđệquylàmộtviệclàmkháphứctạpvàkhókhăn.ởhàmn!hayF(n)tacóthểdùngmộtthuậttoánkhôngđệquy,nhưngtrongmộtsốbàitoán,đệquylàbắtbuộc.Bạncóthểnóirằng,vậythìcứsửdụngđệquy,vừangắngọndễhiểu,vừadễcàiđặt.Nhưngcóđôikhi,sựhạnhẹpcủabộnhớdànhchochươngtrìnhconkhôngchophépchúngtalàmđiềuđó;hoặcchúngtabiếtrằng,ngônngữmáykhôngcóđệquy,vìvậycáctrìnhbiêndịchđềuphảicónhiệmvụkhửđệquy.Vàbạncóthểthựcsựgặprắcrốivớithủtụcđệquycủamìnhkhitrongmộtmôitrườnglậptrìnhmàkhôngcungcấpkhảnănggọiđệquy.Khửđệquygiúpbạnvẫngiữđượcnguyênbảnthuậttoánđệquycủamìnhmàkhônghềcólờigọiđệquy,vànhưthếchươngtrìnhcóthểchạyđượctrongbấtkỳmôitrườnglậptrìnhnào.Khửđệquythựcchấtlàchúngtaphảilàmcôngviệccủamộttrìnhbiêndịchđốivớimộtthủtục,đólà:Đặttấtcảcácgiátrịcủacácbiếncụcbộvàđịachỉcủachỉthịkếtiếpvàongănxếp(Stack),quyđịnhcácgiátrịthamsốchothủtụcvàchuyểntớivịtríbắtđầuthủtục,thựchiệnlầnlượttừngcâulệnh.Saukhithủtụchoàntấtthìnóphảilấyrakhỏingănxếpđịachỉtrảvềvàcácgiátrịcủacácbiếncụcbộ,khôiphụccácbiếnvàchuyểntớiđịachỉtrảvề.Đểdễtheodõichúngtalấyvídụvớibàitoáncụthểlàbàitoánduyệtcây.Giảsửcómộtcâynhịphânlưutrữtrongbiếnđộngtđượcđịnhnghĩa:type pnode = ^node;node = record inf : variable; { truong luu tru thong tin } l,r : pnode;end;var t : pnode;Xuấtpháttừnútgốct,cầnduyệtquahếtcâytheothứtựtừtráiquaphải.Chươngtrìnhconđệquysẽnhưsau:procedure Try(t : pnode);beginif t nil then begin visit(t); Try(t^.l); Try(t^.r); end;end;