C++数据结构学习:递归
2008-03-08 21:36:34 来源：WEB开发网 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鎯у⒔閹虫捇鈥旈崘顏佸亾閿濆簼绨绘い鎺嬪灪閵囧嫰骞囬姣挎捇鏌熸笟鍨妞ゎ偅绮撳畷鍗炍旈埀顒勭嵁婵犲嫮纾介柛灞捐壘閳ь剛鎳撻～婵嬪Ω閳轰胶鐤呯紓浣割儐椤戞瑩宕ョ€ｎ喗鐓曟い鎰靛亝缁舵氨绱撻崘鈺傜婵﹤顭峰畷鎺戔枎閹搭厽袦婵犵數濮崑鎾绘⒑椤掆偓缁夌敻骞嗛悙鍝勭婵烇綆鍓欐俊鑲╃磼閹邦収娈滈柡灞糕偓鎰佸悑閹肩补鈧尙鏁栧┑鐐村灦閹稿摜绮旈悽绋课﹂柛鏇ㄥ灠閸愨偓濡炪倖鍔﹀鈧繛宀婁邯濮婅櫣绱掑Ο璇茶敿闂佺ǹ娴烽弫璇差嚕婵犳碍鏅插璺猴工瀹撳棝姊虹紒妯哄缂佷焦鎸冲畷鎴﹀箻鐠囧弶宓嶅銈嗘尰缁嬫垶绂嶉悙顒佸弿婵☆垳鍘ф禍楣冩倵濮樼偓瀚�
闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鎯у⒔閹虫捇鈥旈崘顏佸亾閿濆簼绨奸柟鐧哥秮閺岋綁顢橀悙鎼闂侀潧妫欑敮鎺楋綖濠靛鏅查柛娑卞墮椤ユ艾鈹戞幊閸婃鎱ㄩ悜钘夌；婵炴垟鎳為崶顒佸仺缂佸瀵ч悗顒勬⒑閻熸澘鈷旂紒顕呭灦瀹曟垿骞囬悧鍫㈠幍缂傚倷鐒﹂敋缂佹う鍥ㄧ厓鐟滄粓宕滈敃鍌氱煑闁告劦鐓堝ḿ鏍煕濠靛棗鐝旂憸鏂跨暦閹偊妲炬繛瀵稿Т閵堢ǹ顫忛搹瑙勫珰闁肩⒈鍓涢澶愭⒑閻撳海绉虹紒鐘崇墵楠炲啯銈ｉ崘鈺佲偓濠氭煢濡警妲奸柟鑺ユ礋濮婃椽妫冨☉杈€嗘繝纰樷偓铏枠鐎规洏鍨介幃浠嬪川婵炵偓瀚奸梺鑽ゅ枑閻熴儳鈧氨鍏樺畷顖濈疀濞戞瑧鍘遍梺缁樏壕顓熸櫠閻㈠憡鐓忛柛鈩冾殔閳ь剙婀辩紓鎾寸鐎ｎ亜绐涙繝鐢靛Т鐎氼剟鐛崼銉︹拺缁绢厼鎳庨ˉ宥夋煙濞茶绨芥俊鍙夊姍瀵挳鎮㈤崫鍕ㄥ彏闂傚倸鍊搁崐椋庢濮橆兗缂氱憸宥囧弲闂侀潧鐗嗗ú鐘诲磻閹炬剚娼╂い鎰╁灩缁侇噣姊虹紒妯圭繁闁革綇缍侀悰顕€骞掗幊铏閸┾偓妞ゆ帒鍊绘稉宥夋煥濠靛棙顥犵紒鈾€鍋撻梻鍌氬€搁悧濠勭矙閹达箑姹叉繛鍡楃贩閻熸壋鍫柛顐犲灮閺嗩偊姊洪崫鍕効缂傚秳鐒﹂幈銊╁焵椤掑嫭鐓冮柟顖滃绾偓绻濋埀顒佹綇閵娧呭骄闂佸搫娲ㄩ崰鎾跺姬閳ь剙鈹戦鏂や緵闁告﹢绠栧畷銏ゆ偨閸涘ň鎷虹紓鍌欑劍閿氬┑顕嗙畵閺屾盯骞橀弶鎴濇懙闂佽鍠楄摫婵炵厧绻樻俊鎼佸Χ閸モ晝鏆伴梻鍌欑濠€杈╁垝椤栨粍鏆滈柣鎰摠濞呯姵绻涢幋鐐寸殤缁炬崘鍋愮槐鎾存媴鐠愵垳绱板┑鐐村絻椤曨參鍩€椤掑喚娼愭繛鍙夌墪閻ｇ兘顢楅崘顏冪胺闂傚倷绀侀幉锟犲礉閺囥垹鐤柣妯款嚙缁€鍫熺節闂堟稓澧涚€规洖寮剁换娑㈠箣閻愩劎绱伴梺鍝勬濡鍩為幋锔藉亹閺夊牜鍋勯崢锟犳⒑鏉炴壆鍔嶉柣妤佺矌濡叉劙骞樼€涙ê顎撴繛瀵稿Т椤戝懘骞楅悽鍛娾拺闁革富鍘介崵鈧┑鐐茬湴閸婃繈骞冩ィ鍐╁€婚柦妯侯槺椤斿﹪姊虹憴鍕剹闁告ü绮欏畷鎾绘偨閸涘ň鎷洪梺鑽ゅ枑濠㈡﹢骞冩笟鈧弻锝夊箳閻愮數鏆ら梺璇″枟椤ㄥ﹪鐛弽銊﹀闁稿繐顦扮€氳棄鈹戦悙鑸靛涧缂佹彃娼″畷鏇㈠Χ婢跺﹤鎯為梺閫炲苯澧存慨濠冩そ楠炴牠鎮欏ù瀣壕闁哄稁鍘介崑瀣煟濡灝鍚圭€规挷绶氶悡顐﹀炊閵娧€濮囬梺鍝勬噺閹倿寮婚妸鈺傚亞闁稿本绋戦锟�
濠电姷鏁告慨鐑藉极閸涘﹥鍙忛柣鎴ｆ閺嬩線鏌涘☉姗堟敾闁告瑥绻橀弻锝夊箣閿濆棭妫勯梺鍝勵儎缁舵岸寮诲☉妯锋婵鐗婇弫楣冩⒑閸涘﹦鎳冪紒缁樺灴婵＄敻宕熼姘鳖啋闂佸憡顨堥崑鐔哥閼测晝纾藉ù锝呮惈椤庡矂鏌涢妸銉у煟鐎殿喛顕ч埥澶愬閻樼數鏉搁梻鍌氬€搁悧濠勭矙閹烘鍊堕柛顐犲劜閸婄敻鏌ｉ悢鍝勵暭闁哥喓鍋熺槐鎺旀嫚閹绘帗娈绘繝纰夌磿閺佽鐣烽悢纰辨晬婵﹢纭搁崯瀣⒑鐠囨煡鍙勬繛浣冲洤绠烘繝濠傜墛閸嬧晛鈹戦崒姘暈闁抽攱鍨归惀顏堫敇閻愭潙顎涘┑鐐插悑閸旀牜鎹㈠☉銏″殤妞ゆ巻鍋撻柡瀣閵囧嫰顢曢姀銏㈩唺缂備浇椴哥敮鎺曠亽闂佸吋绁撮弲婊堝吹瀹€鍕拻濞撴埃鍋撻柍褜鍓涢崑娑㈡嚐椤栨稒娅犳い鏃囧亹閺嗗棝鏌ㄥ┑鍡欏闁告柨鐏氶妵鍕晜閻ｅ苯寮ㄩ梺璇″櫙缁绘繃淇婇懜闈涚窞閻庯綆鍓欑敮楣冩⒒娴ｇǹ顥忛柛瀣噽閹广垽宕橀鑲╋紱濡炪倕绻愰幊鎰不閸撗€鍋撻悷鏉款棌闁哥姵娲滈懞杈ㄧ節濮橆剛鐣鹃梺缁樻煥閸氬鍩涢幋锔藉€甸柛锔诲幖鏍￠梺闈涙閸熸挳寮婚妶澶婄闁肩⒈鍓欓悡鐔兼倵鐟欏嫭绀冪紒璇茬墦瀵偊宕橀鑲╁姦濡炪倖甯掔€氀囧焵椤掍焦顥堢€规洘锕㈤、娆撳床婢诡垰娲﹂悡鏇㈡煃閳轰礁鏋ゆ繛鍫燂耿閺岋綁鎮㈢粙鍨潚濠殿喖锕ュ浠嬪箖閳╁啯鍎熼柍鈺佸暞閻︼綁姊绘担铏瑰笡闁绘娲熸俊鍓佺矙鐠恒劍娈鹃梺缁樺灦宀ｈ法寮ч埀顒勬⒑閹肩偛鍔€闁告劑鍔庨妶顕€姊婚崒娆戠獢婵炰匠鍕垫闊洦娲橀～鏇㈡煛閸ャ儱鐏╅柛灞诲妽閵囧嫯绠涢幘璺侯杸闂佹娊鏀遍崹鍧楀蓟閻斿吋鍤冮柍杞版缁爼姊洪崨濠冣拹妞ゃ劌锕濠氭晸閻樻彃绐涘銈嗘閺侇喗鎱ㄩ崶鈺冪＝濞达絿枪閳ь剙婀遍弫顕€鎮㈡俊鎾虫川閳ь剟娼ч幗婊呭婵傜ǹ绾ч柛顐ｇ☉婵¤偐绱掑Δ浣侯暡缂佺粯鐩幃鈩冩償閿濆浂鍟嬮梻浣虹《閺備線宕滃┑瀣闁告稑鐡ㄩ悡銉╂倵閿濆懐浠涚紓宥嗩殜濮婂宕掑顑藉亾瀹勬噴褰掑炊瑜滃ù鏍煏婵炵偓娅嗛柛濠傛健閺屻劑寮撮悙娴嬪亾閸濄儳涓嶉柡灞诲劜閻撴洟鏌曟径妯烘灈濠⒀屽櫍閺岋紕鈧絺鏅濈粣鏃堟煛瀹€鈧崰鏍х暦濠婂棭妲鹃柣銏╁灡閻╊垶寮婚敓鐘插窛妞ゆ棁妫勯埀顒佸姍閺岋紕浠︾拠鎻掝潎闂佽鍠撻崐婵嗙暦閹烘垟妲堟慨妤€妫旂槐锟�闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鎯у⒔閹虫捇鈥旈崘顏佸亾閿濆簼绨绘い鎺嬪灪閵囧嫰骞囬姣挎捇鏌熸笟鍨妞ゎ偅绮撳畷鍗炍旈埀顒勭嵁婵犲嫮纾介柛灞捐壘閳ь剛鎳撻～婵嬪Ω閳轰胶鐤呯紓浣割儐椤戞瑩宕ョ€ｎ喗鐓曟い鎰靛亝缁舵氨绱撻崘鈺傜婵﹤顭峰畷鎺戔枎閹搭厽袦婵犵數濮崑鎾绘⒑椤掆偓缁夌敻骞嗛悙鍝勭婵烇綆鍓欐俊鑲╃磼閹邦収娈滈柡灞糕偓鎰佸悑閹肩补鈧尙鏁栧┑鐐村灦閹稿摜绮旈悽绋课﹂柛鏇ㄥ灠閸愨偓濡炪倖鍔﹀鈧繛宀婁邯濮婅櫣绱掑Ο璇茶敿闂佺ǹ娴烽弫璇差嚕婵犳碍鏅插璺猴工瀹撳棝姊虹紒妯哄缂佷焦鎸冲畷鎴﹀箻鐠囧弶宓嶅銈嗘尰缁嬫垶绂嶉悙顒佸弿婵☆垳鍘ф禍楣冩倵濮樼偓瀚� 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鐐劤缂嶅﹪寮婚敐澶婄闁挎繂鎲涢幘缁樼厱闁靛牆鎳庨顓㈡煛鐏炶鈧繂鐣烽锕€唯闁挎棁濮ら惁搴♀攽閻愬樊鍤熷┑顕€娼ч～婵嬪Ω瑜庨～鏇㈡煙閹规劦鍤欑痪鎯у悑缁绘盯宕卞Ο铏圭懆闂佸憡锕槐鏇犳閹惧鐟归柛銉戝嫮褰梻浣规偠閸斿矂鎮ラ崗闂寸箚闁圭虎鍠栫粈鍐┿亜閺冨倸甯剁紒鎰洴濮婃椽宕崟鍨ч梺鎼炲妼缂嶅﹤鐣烽姀鐘嗘椽顢旈崨顓涘亾閸偒娈介柣鎰皺娴犮垽鏌涢弮鈧喊宥夊Φ閸曨垱鏅滈悹鍥皺娴犳悂鎮楃憴鍕┛缂佺粯绻堥悰顔芥償閵婏箑娈熼梺闈涳紡閸愩劌顩梻鍌氬€搁オ鎾磻閸曨個娲晝閳ь剛鍙呴梺鍝勭Р閸斿孩鏅堕敓鐘斥拻闁稿本鐟︾粊鐗堛亜閺囧棗鎳夐崑鎾诲垂椤愩垺璇為悗瑙勬礃缁捇骞冮姀锛勯檮濠㈣泛顑囩粙渚€姊绘担鐟板姢缂佺粯鍔曢敃銏℃綇閳轰緡妫滈梺绋跨箻濡法鎹㈤崱妯镐簻闁哄秲鍔庨。鏌ユ煙椤栨氨澧涢柕鍥у椤㈡洟濮€閵忋垹濮辨繝娈垮枛閿曘儱顪冮挊澶屾殾闁绘垹鐡旈弫鍥ㄧ箾閹寸偟鎳冮柣婵嬩憾濮婄粯鎷呴崨闈涚秺椤㈡牠宕ㄩ鍥ㄧ☉閳规垹鈧綆浜為悾楣冩⒑闁偛鑻晶顖炴煏閸パ冾伂缂佺姵鐩獮妯尖偓鍨偠閸嬫劖绻濈喊妯活潑闁搞劍澹嗛埀顒佺濠㈡﹢锝炶箛鎾佹椽顢旈崟顏嗙倞闂備礁鎲″ú锕傚礈濮樿泛绠柛妤冨亹閺€浠嬫煟閹邦厼绲荤紒鐙欏啰鏆嗛柨婵嗘噺閸嬨儲顨ラ悙鏉戠伌濠殿喒鍋撻梺缁橈供閸嬪懘寮埀顒€鈹戦悩鍨毄濠殿喖顕埀顒佸嚬閸ｏ絽顕ｉ崼鏇炵濞达絽鍘滈幏娲⒑閸涘﹦绠撻悗姘煎幖椤斿繐鈹戦崱蹇旀杸濡炪倖姊归崕鎶藉储閹绢喗鐓欐い鏃囶嚙瀹撳棗鈹戦敍鍕幋闁糕晪绻濆畷鎺懳旀担鍓蹭紲濠电姷鏁搁崑鐘诲箵椤忓棗绶ゅù鐘差儏缁犺銇勯幇鈺佲偓鏍汲濠婂牊鍋ｉ弶鐐村椤掔喖鏌ｉ弬鎸庮棦闁哄矉缍侀幃銏犵暋閹殿喚娉块梻浣姐€€閸嬫捇鏌ゆ慨鎰偓妤冨婵傚憡鐓曢悘鐐靛亾閻ㄦ垹鈧稒绻傝灃婵°倕锕ｇ花鐑芥煕濡も偓閸熷潡鎮鹃悜鑺ュ亗閹兼惌鍠楅崓鐢告⒑閹稿海绠撻柟鍐茬У缁旂喖寮撮姀鈾€鎷洪梺鍛婄箓鐎氼剟寮冲▎鎾寸厽婵°倐鍋撴俊顐ｇ〒閸掓帡宕奸妷銉ь槰闂佸磭鎳撻妵妯艰姳婵犳碍顥婃い鎰╁灪閹兼劖绻涚€电ǹ鍘撮挊婵嬫煥閺囨浜鹃梻鍥ь槹缁绘繃绻濋崒婊冣叡闂佷紮绲惧浠嬪蓟閿涘嫪娌悹鍥ㄥ絻椤牓姊虹€圭媭娼愰柛銊ョ仢閻ｇ兘宕￠悙鈺傤潔闂佺懓鍚€缁€浣圭閻愵兛绻嗛柕鍫濆€告禍鎯ь渻閵堝骸寮ㄩ柛搴☆煼绡撳〒姘ｅ亾闁哄本鐩幃鈺佺暦閸パ€鎷版繝鐢靛Л閸嬫挸銆掑锝呬壕濠殿喖锕ㄥ▍锝囨閹烘嚦鐔煎即閻旈浼岄梺璇″枤閸忔ɑ淇婇悿顖ｆХ闂佺ǹ顑嗛幐鎼侊綖濠靛鍋傞幖娣灮娴滃墽绱撻崒娆戣窗闁哥姵姘ㄩ崚鎺楊敍閻愬弬褔鏌ㄥ┑鍡╂Ц缂佲偓閸愵喗鐓冮柛婵嗗閺嗘瑦顨ラ悙鑼濞ｅ洤锕幃娆擃敂閸曘劌浜鹃柡宥庡幖缁€澶愭煙鏉堝墽鐣辩痪鎯х秺閺岋繝宕堕妷銉т患闂佸憡鍨规繛鈧鐐寸墪鑿愭い鎺嗗亾濠碘€茬矙閺岋綁骞樼捄鐑樼亪闂佺粯鎼╅崑濠傜暦閹偊妾ㄩ梺绋块缁绘﹢寮诲☉銏犵睄闁逞屽墰閸掓帡骞樼拠鑼舵憰闂佸搫娲㈤崹褰掓倷婵犲嫭鍠愮€广儱顦介弫鍌涖亜閹捐泛袥闁稿鎸搁埢鎾诲垂椤旂晫浜舵繝鐢靛仜閸氬鎮烽妸鈺傚€堕柟鐑橆殕閳锋垿鏌涘☉姗堝姛缂佺姵鎹囬幃妤€顫濋悡搴♀拤濡炪們鍊曢崐鍦崲濠靛牆鏋堝璺虹灱閿涚喖姊虹粙娆惧剱闁搞劌鐏濋悾鐑藉箛閺夎法顓洪梺鎸庢磵閸嬫捇鏌涢妸銉モ偓鍦崲濞戞﹩鍟呮い鏃囧吹閸戝綊姊虹粙娆惧劀缂佺粯绻堝璇差吋婢跺﹣绱堕梺鍛婃处閸撴瑥鈻嶉敐鍥╃＝濞达絽鎼牎闂佺粯顨堟繛鈧€殿喛顕ч鍏煎緞婵犲嫬骞愬┑鐐舵彧缁蹭粙骞夐垾鏂ユ灁闁哄被鍎查埛鎴犵磼鐎ｎ偄顕滈柟鐧哥秮閺屾盯鎮╁畷鍥р拰閻庢鍠栭…宄邦嚕閹绢喖顫呴柣姗€娼ч埀顒傚仱閹嘲饪伴崘顎倝鏌ゆウ鍧楀摵缂佺粯绻傞～婵嬵敇閻樻彃绠ラ梻鍌欑閹诧繝宕归鐐茬９闁哄稁鍋€閸嬫挸顫濋悙顒€顏�
核心提示：上网查了查，关于“递归”的文章可以说“汗牛充栋”——请原谅我在这里犯酸，C++数据结构学习:递归，我的意思是，写别人都写臭的东西让大家看，就要一个令人信服的例子，而这个例子非汉诺塔莫属，只是浪费大家的时间，所以我下面的东西应该是一些至少我看起来是新的东西
上网查了查，关于“递归”的文章可以说“汗牛充栋”——请原谅我在这里犯酸，我的意思是，写别人都写臭的东西让大家看，只是浪费大家的时间，所以我下面的东西应该是一些至少我看起来是新的东西，假如觉得有什么不清楚的，请参阅相关的文章（太多了）。
看过这样一道题，问，“程序结构化设计的三种基础结构，顺序、选择、循环是不是必须的？”当然，你知道这样一个论断，只要有这三种就足够了；但是能不能更少呢？答案是“可以”，原因就是递归能取代循环的作用，例如下面的对一个数组里面元素求和的函数：
float rsum (float a[], const int n)
{
if (n <= 0) return 0;
else return rsum(a, n – 1) + a[n – 1];
}
实际上就是：
sum = 0;
for (int i = 0; i < n; i++) sum += a[i];
但实际的情况是，任何的一种语言里面都有循环结构，但不是任何的语言都支持递归；套用一句话，递归是万能的，但没有递归不是万万不能的。然而，我看到现在的某些人，不管什么问题都要递归，明明循环是第一个想到的方法，偏偏费尽脑筋去寻找递归算法。对此，我真的不知道该说什么。
递归是算法吗
经常的看到“递归算法”、“非递归算法”，这种提法没有语义上的问题，并且我自己也这样用——递归的算法。但这也正说明了，递归不是算法，他是一种思想，正是因为某个算法的指导思想是递归的，所以才被称为递归算法；而一个有递归算法的问题，当你不使用递归作为指导思想，这样得到的算法就是非递归算法。——而对于循环能处理的问题，都有递归解法，在这个意义上说，循环算法都可以称为非递归算法。
更多内容请看C/C++技术专题 数据结构 数据结构教程专题，或
我在这咬文嚼字没什么别的意思，只是想让大家知道，能写出什么样的算法，要害是看你编写算法时的指导思想。
从学排列组合那天开始，我所知道的阶乘就是这个样子n! = 1×2×……n。假如让我来写阶乘的算法，我也只会想到从1乘到n。再如，斐波那契数列，假如有人用自然语言描述的话，一定是这样的，开始两项是0、1，以后的每项都是前面两项的和。所以让我写也只会得到“保存前两项，然后相加得到结果”的迭代解法。——现在只要是讲到递归几乎就有他们的登场，美其名曰：“定义是递归的，所以我们写递归算法”。
我想问的是，定义的递归抽象是从哪里来的？显然阶乘的定义是从一个循环过程抽象来的，斐波那契数列的定义是个迭代的抽象。于是，我们先从一个本不是递归的事实抽象出一个递归的定义，然后我们说，“因为问题的定义是递归的，因此我们很轻易写出递归算法”，接着说，“我们也能将这个递归算法转化为循环、迭代算法”，给人的感觉就像是1÷3＝0.33……，0.33……×3＝0.99……，然后我们花了好大的心智才明白1＝0.99……。
还是有那么些人乐此不疲，是凡讲到递归就要提到这两个，结果，没有一个学生看到阶乘那样定义没有疑问的，没有一个对于那个递归的阶乘函数抱有钦佩之情的——瞎折腾什么呢？所以，假如要讲递归，就要一个令人信服的例子，而这个例子非汉诺塔莫属。
更多内容请看C/C++技术专题 数据结构 数据结构教程专题，或
中查找“C++数据结构学习:递归”更多相关内容
中查找“C++数据结构学习:递归”更多相关内容更多精彩
赞助商链接
