当前位置:网站首页>遞迴思想的巧妙理解
遞迴思想的巧妙理解
2020-11-06 01:35:00 【itread01】
邏輯是數學的少年時代,數學是邏輯的成年時代。
——羅素
“遞迴”
這是在程式、演算法設計中的基礎和重中之重。當初理解這一點我也花費了不少時間,對於初學者來說,如何生動形象的展現著一過程,成了理解這一思想的關鍵。
這篇博文的來由,源於同學問我的一個問題:
我一看啊,這波,這波是明顯的遞迴啊!!
我想著,怎麼解釋呢,於是開啟百度搜索遞迴:
定義
程式呼叫自身的程式設計技巧稱為遞迴( recursion)。遞迴做為一種演算法在程式設計語言中廣泛應用。 一個過程或函式在其定義或說明中有直接或間接呼叫自身的一種方法,它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解,遞迴策略只需少量的程式就可描述出解題過程所需要的多次重複計算,大大地減少了程式的程式碼量。遞迴的能力在於用有限的語句來定義物件的無限集合。一般來說,遞迴需要有邊界條件、遞迴前進段和遞迴返回段。當邊界條件不滿足時,遞迴前進;當邊界條件滿足時,遞迴返回。
我想這,這麼生硬的解釋,還是別麻煩人家了吧,於是這個解釋就鴿了好幾天
奇思妙想
某個摸魚的晚上,我突然想到了一個解釋遞迴生動形象的例子,那就是:
俄羅斯套娃!!
那麼,如何用俄羅斯套娃的思想去理解遞迴思想呢?
又是眾所周知,遞迴其實就是程式呼叫自身,這不就好像是,在自己肚子裡面裝了一個自己麼?
不過,我們開這個套娃的方式,得遵循以下規則;
先吧套娃的上半部分拿走(執行呼叫自身的函式上邊的程式碼);
繼續拿上半部分,直到拿出了一個不能在開的娃(遞迴到底);
看看這個不能再套娃的娃(完整的執行這個最“深”的函式);
在依次拿出所有套娃的下半身(自底向上執行所有遞迴函式的下半部分)。
案例解釋
我們先看這個求樹的深度的程式碼:
int TreeDepth(BT *T){ int ld=0,rd=0; if(T==NULL) return 0; else{ ld=TreeDepth(T->lchild); rd=TreeDepth(T->rchild); if(ld>rd) return ld+1; else return rd+1; } }
我就畫個圖來看看吧
假設有這麼一顆樹,BT是函式中指標*T所在位置
我們執行這一段程式碼
int TreeDepth(BT *T){ int ld=0,rd=0; if(T==NULL) return 0; else{ ld=TreeDepth(T->lchild);
先遞迴到底邊,在走下去,全是NULL了,就可以執行後一段程式碼
if(ld>rd) return ld+1; else return rd+1;
當然,這裡ld和rd都是0,返回值是1,根據
ld=TreeDepth(T->lchild);
則上一層函式的ld=1
我們繼續看,因為這一個函式已經執行結束了,我們來執行上一個函式的後半段程式碼。
rd=TreeDepth(T->rchild); if(ld>rd) return ld+1; else return rd+1; } }
這裡我們發現,可以一直走右子樹走下去,參考上一步的操作,以此類推,我們得到下圖
再繼續推下去,整個程式的返回值就一目瞭然了
這裡還是要再提一下深度優先搜尋(DFS),眾所周知深搜的最基本技巧就是遞迴。
PS:雖然深搜也可以用棧實現,不過遞迴就是程式自己調出棧來儲存資料,差別不大。
樹是特殊的圖,樹的遍歷也是圖的遍歷,這種按照深度一口氣遍歷下來的方式,就是我們所謂的DFS,再樹基礎的學習過程中,我們也可以體會到很多圖的性質
希望我的拋磚引玉能引起更多的思考
版权声明
本文为[itread01]所创,转载请带上原文链接,感谢
https://www.itread01.com/content/1604563565.html
边栏推荐
猜你喜欢
随机推荐
【數量技術宅|金融資料系列分享】套利策略的價差序列計算,恐怕沒有你想的那麼簡單
Skywalking系列博客5-apm-customize-enhance-plugin插件使用教程
Cocos Creator 原始碼解讀:引擎啟動與主迴圈
Azure Data Factory(三)整合 Azure Devops 實現CI/CD
keras model.compile损失函数与优化器
【事件中心 Azure Event Hub】Event Hub日誌種發現的錯誤資訊解讀
如何将分布式锁封装的更优雅
业务策略、业务规则、业务流程和业务主数据之间关系 - modernanalyst
6.9.2 session flashmapmanager redirection management
Python 基于jwt实现认证机制流程解析
TensorFlow2.0 问世,Pytorch还能否撼动老大哥地位?
[C#] (原創)一步一步教你自定義控制元件——04,ProgressBar(進度條)
字符串的常见算法总结
深入了解JS数组的常用方法
小白量化投资交易入门课(python入门金融分析)
JVM Metaspace内存溢出排查与总结
Using lime to explain black box ML model
别走!这里有个笔记:图文讲解 AQS ,一起看看 AQS 的源码……(图文较长)
Big data real-time calculation of baichenghui Hangzhou station
6.7 theme resolver theme style parser (in-depth analysis of SSM and project practice)