會寫遞歸超越了多少程序員?
閱讀本文大概需要 2.8 分鐘。
來自:https://www.zhihu.com/question/589779747

閃耀大叔
好多年前的我,大二,剛學c語言,啥也不會,只會遞歸。參加藍橋杯,就憑這一招,拿了省賽一等獎,國賽二等獎。我以為自己很強,后來發(fā)現(xiàn)是這個比賽水......
后來做嵌入式,發(fā)現(xiàn)遞歸思路簡單,但開銷極大,經(jīng)常想盡辦法改成非遞歸......
Evan_song
恭喜你!你超越了大部分程序員!
你掌握了遞歸技術(shù),說明你可以寫出dfs!
使用dfs技術(shù),你可以寫二叉搜索樹!
熟練運用dfs,你還可以完成線段樹的編寫!
二叉搜索樹再隨便學學,就是平衡樹,你掌握了FHQ,Splay,Treap,紅黑樹,替罪羊樹,B樹!
線段樹可以拓展到值域線段樹!
同樣的,平衡樹可以拓展到文藝平衡樹!
繼續(xù)就是樹套樹!
Link-Cut-Tree!
往圖論那邊走走,你學會了tarjan!
tarjan可以完成割邊割點,邊點雙連通分量!
二分圖匈牙利算法、網(wǎng)絡(luò)流最大流也不難,會dfs都可以學!
你還可以去DP那看看,dfs記憶化加剪枝能完成很多動態(tài)規(guī)劃!
這還不止,會遞歸就可以寫歸并排序,你掌握了sorting。
你會求逆序?qū)Α?/span>
你會分治。
你會CDQ分治。
你會整體二分。
你會KDtree你會exgcd,你會歐拉反演你會莫比烏斯反演。
…………
Terrell
會寫遞歸容易,會把實際問題建模成遞歸問題才是能力。實際工作中總會看到一個復雜的問題被大佬搞成驚艷的遞歸。
揚揚
多年以前的公司,年末會有一項小活動,大家一起實現(xiàn)一小段程序,看誰效率最高。
第一年搞的是輸出100內(nèi)質(zhì)數(shù),一個來實習的小姑娘獨占鰲頭。一看代碼直接手動輸出,確實效率最高。
第二年總監(jiān)學聰明了,搞了個兔子繁殖(1,1,2,3,5...),輸出第幾萬個。像我這種用遞歸實現(xiàn)的菜雞直接沒有運行的機會,。
南山煙雨珠江潮
會寫遞歸剛?cè)腴T,不會寫遞歸的不能稱之為程序員。
但是如果能將任意循環(huán)改成遞歸、且能將任意遞歸改成循環(huán),應(yīng)該可以超越30%以上的程序員。
karlestira
不好說,看問題。
有一些東西,人家哼哧哼哧寫一長串循環(huán)邏輯,你寫了一個看似很優(yōu)美的遞歸。
上線以后人家的運行正常,你的爆棧。
現(xiàn)實中并沒有那么多只能靠遞歸來解的問題,但現(xiàn)實中有很多商業(yè)應(yīng)用邏輯要求你能夠適應(yīng)任意大小的輸入,不得因為輸入規(guī)模變化導致程序崩潰(有些人對咱這里說的規(guī)模不是很清楚,我就這么說吧,匿名頁100G起步,IO總量T級別起步,P級別也算正常)。在我的觀念里除開一些特殊場合(比如遍歷文件系統(tǒng),目錄深度100層已經(jīng)很了不起了,層數(shù)過多文件系統(tǒng)就先報警了),遞歸真的只能寫玩具。
另外,哥們,像我做高性能計算,AVX這種SIMD指令幾乎是必須使用的。遞歸方便使用SIMD指令嗎?寫到CUDA那邊還舒服嗎?以后的維護人員會不會想請你吃大嘴巴?
真正對性能要求特別高的東西、瓶頸已經(jīng)到訪存帶寬、L3延遲的,我就沒見過一定要遞歸處理的,99%以上都是SIMD的思路。至于性能沒啥要求的,應(yīng)付應(yīng)付網(wǎng)卡那點撐死16GB每秒速度、延遲微秒起步的東西,你愛咋寫咋寫。
我還是那句話,如果一個實際問題你第一反應(yīng)就是想遞歸(比如說文件系統(tǒng)遍歷),那就遞歸,如果你第一反應(yīng)不是遞歸,并且不用遞歸也可以很舒服的寫出代碼,那遞歸就毛用沒有,對這種問題強行遞歸我只能說回字確實有很多種寫法。
推薦閱讀:
注解方式優(yōu)雅的實現(xiàn) Redisson 分布式鎖
互聯(lián)網(wǎng)初中高級大廠面試題(9個G) 內(nèi)容包含Java基礎(chǔ)、JavaWeb、MySQL性能優(yōu)化、JVM、鎖、百萬并發(fā)、消息隊列、高性能緩存、反射、Spring全家桶原理、微服務(wù)、Zookeeper......等技術(shù)棧!
?戳閱讀原文領(lǐng)?。?/span> 朕已閱

