遞歸演算法這個是非常常見的一個演算法,也是大多數人都會用的,因為它足夠簡單,通俗易懂!在遍歷城市,樹等大腦里反應出來的第一方法大多就屬於這個了 遞歸容易使用,但是也容易用壞,我想"記憶體溢出"這個估計是每個人用遞歸都會碰到的bug,我為什麼還是要寫這方面的知識呢,那是因為文章的最後我有一個問題要問 首先我 ...
遞歸演算法這個是非常常見的一個演算法,也是大多數人都會用的,因為它足夠簡單,通俗易懂!在遍歷城市,樹等大腦里反應出來的第一方法大多就屬於這個了
遞歸容易使用,但是也容易用壞,我想"記憶體溢出"這個估計是每個人用遞歸都會碰到的bug,我為什麼還是要寫這方面的知識呢,那是因為文章的最後我有一個問題要問
首先我先展示我之前寫的一段遞歸拼接層級樹的代碼:
private string ParentColumns(List<Cy_Column> columns, int id) { using (msdb) { var parents = columns.Where(p => p.parentid == id).ToList(); StringBuilder sb = new StringBuilder(); if (parents.Count > 0) { parents.ForEach(item => { sb.AppendFormat("<tr class=\"text-c\"><td><input type =\"checkbox\" name =\"\" value=\"\" ></td><td>{0}</td><td>{1}</td><td class=\"text-l\">{2}</td><td class=\"f-14\"><a title=\"編輯\" href=\"javascript:;\" onclick=\"system_category_edit('欄目編輯', 'http://localhost:40043/AdminManage/Content/SystemColumnsEdit', '1', '700', '480')\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\"></i></a> <a title=\"刪除\" href=\"javascript:;\" onclick=\" article_category_del(this, '1' )\" class=\"ml-5\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\"></i></a></td></tr>", item.cl_id, item.cl_px, item.cl_name); sb.Append(ChildColumns(columns, item.cl_id, 2)); }); //釋放記憶體 parents = null; } return sb.ToString(); } }
private string ChildColumns(List<Cy_Column> columns, int cl_id, int sub) { var childs = columns.Where(p => p.parentid == cl_id).ToList(); StringBuilder sb = new StringBuilder(); if (childs.Count > 0) { string substag = ""; for (int i = 0; i < sub; i++) { substag += "—"; } childs.ForEach(item => { sb.AppendFormat("<tr class=\"text-c\"><td><input type =\"checkbox\" name =\"\" value=\"\" ></td><td>{0}</td><td>{1}</td><td class=\"text-l\">{3}{2}</td><td class=\"f-14\"><a title=\"編輯\" href=\"javascript:;\" onclick=\"system_category_edit('欄目編輯', '/AdminManage/Content/SystemColumnsEdit', '1', '700', '480')\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\"></i></a> <a title=\"刪除\" href=\"javascript:;\" onclick=\" article_category_del(this, '1' )\" class=\"ml-5\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\"></i></a></td></tr>", item.cl_id, item.cl_px, item.cl_name, substag); sb.Append(ChildColumns(columns, item.cl_id, 2 * sub)); }); childs = null; } return sb.ToString(); }
這代碼是我修複過的,之前報記憶體溢出的代碼我就不貼了,無非就是我引用了靜態變數list以及StringBuilder類,所以遞歸的時候,記憶體得不到有效釋放,最後就瀑黃頁了。
那麼這個bug的本質我說一下:因為線程在運行函數,都會分配一定的記憶體(棧空間)給它,如方法的參數,變數,返回值等!而這個方法又在不斷的調用自身,所以深度大了,其記憶體又得不到釋放,就超出異常了!所以我這裡用靜態變數就顯得“助紂為虐”了
那麼,問題就來了,如果根據老趙的尾遞歸與Continuation一問中的描述,那我也可以改造成堆記憶體不造成影響的“尾遞歸”形式,我只要用accStr來記錄上一次累加的字元串當作參數傳遞,於是就有了下麵這段異常難看的代碼
private string ChildColumnsRecursively(List<Cy_Column> columns, int cl_id, int sub,string accStr) { var childs = columns.Where(p => p.parentid == cl_id).Select(p => new { id = p.cl_id, oid = p.cl_px, name = p.cl_name }).ToList(); StringBuilder sb = new StringBuilder(); if (childs.Count > 0) { string substag = ""; for (int i = 0; i < sub; i++) { substag += "—"; } childs.ForEach(item => { sb.AppendFormat("<tr class=\"text-c\"><td><input type =\"checkbox\" name =\"\" value=\"\" ></td><td>{0}</td><td>{1}</td><td class=\"text-l\">{3}{2}</td><td class=\"f-14\"><a title=\"編輯\" href=\"javascript:;\" onclick=\"system_category_edit('欄目編輯', '/AdminManage/Content/SystemColumnsEdit', '1', '700', '480')\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\"></i></a> <a title=\"刪除\" href=\"javascript:;\" onclick=\" article_category_del(this, '1' )\" class=\"ml-5\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\"></i></a></td></tr>", item.id, item.oid, item.name, substag); accStr += ChildColumnsRecursively(columns, item.id, 2 * sub, sb.ToString()); }); childs = null; sb.Append(accStr); } return sb.ToString(); }
這怎麼看怎麼不是尾遞歸,連“偽遞歸”都談不上
我心中的改造形式應該是像下麵這樣的偽代碼:
public string ChildColumnsRecursively(List<Cy_Column> columns,int id,string accStr){ ...Logic Code accStr = values; return ChildColumnsRecursively(columns,pid,accStr); }
看老趙的博客,感覺看懂了,但是我想用到我這個案例上,卻又感覺差點東西,不知道那方面還沒理解到位...先擱這吧,以後再慢慢想解決方案