你的位置:首页 > ASP.net教程

[ASP.net教程]使用递归方法拼接层级树


递归算法这个是非常常见的一个算法,也是大多数人都会用的,因为它足够简单,通俗易懂!在遍历城市,树等大脑里反应出来的第一方法大多就属于这个了

递归容易使用,但是也容易用坏,我想"内存溢出"这个估计是每个人用递归都会碰到的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\">&#xe6df;</i></a> <a title=\"删除\" href=\"javascript:;\" onclick=\" article_category_del(this, '1' )\" class=\"ml-5\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\">&#xe6e2;</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\">&#xe6df;</i></a> <a title=\"删除\" href=\"javascript:;\" onclick=\" article_category_del(this, '1' )\" class=\"ml-5\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\">&#xe6e2;</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\">&#xe6df;</i></a> <a title=\"删除\" href=\"javascript:;\" onclick=\" article_category_del(this, '1' )\" class=\"ml-5\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\">&#xe6e2;</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);}

看老赵的博客,感觉看懂了,但是我想用到我这个案例上,却又感觉差点东西,不知道那方面还没理解到位...先搁这吧,以后再慢慢想解决方案