一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 704|回复: 7
收起左侧

[其他] Recursion也有Top-down和Bottom-up之分么?

[复制链接] |试试Instant~ |关注本帖
stellari 发表于 2015-9-18 17:12:11 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
最近和一个白人哥们讨论一个递归算法,我把算法写到白板上,他突然问我:“你写的这个是Top-down recursion还是Bottom-up recursion”?我一愣,心想,递归难道不都是top-down的么,还有bottom-up的说法么?但是这时因为某些原因讨论被中断了,之后也没能再找到这哥们。Google了一下都是说DP的top-down和bottom-up的区别,于是想来版上问一下:递归算法是否真的有Top-down和Bottom-up之分?

------

按我自己的理解,他可能是这个意思,比如列举一个无重复的字符数组s = {'a', 'b', 'c' ... }的全排列程序:

  1. vector<vector<char> > result;
  2. vector<char> p;
  3. void foo(vector<char>& s, int start) {
  4.     if (start == s.size()) {result.push_back(p); return;}
  5.     for (int i = start; i < s.size(); ++i) {
  6.         swap(s[start], s[i]);
  7.         p.push_back(s[start]);
  8.         foo(s, start+1);
  9.         p.pop_back();
  10.         swap(s[start], s[i]);
  11.     }
  12. }
复制代码

  1. vector<vector<char> > bar(vector<char> s, int start)  {
  2.     vector<vector<char> > res{};
  3.     for (int i = start; i < s.size(); ++i) {
  4.         swap(s[start], s[i]);
  5.         vector<vector<char> > temp = bar(s, start+1);
  6.         if (temp.empty()) temp.push_back(vector<char>());
  7.         swap(s[i], s[start]);
  8.         for (auto& t: temp) {
  9.              res.push_back(t);
  10.              res.back().push_back(s[i]);
  11.         }
  12.     }
  13.     return res;
  14. }
复制代码
-------

foo的方法是向下搜索的时候暂存了目前得到的部分结果,因此向解集中加入一个完整解的过程发生在最深层递归;而bar则是在递归中不断构造子问题的解,在最浅层递归中再把所有的结果综合在一起。也许他管这两种递归分别叫top-down和bottom-up,但即使这样,我还是没搞清楚那种情况算是top-down,哪种情况算是bottom-up

哪位版友知道的,请不吝赐教。
zwcelesta 发表于 2015-9-18 18:49:00 | 显示全部楼层
之前做leetcode看到过。
可以参考下http://articles.leetcode.com/201 ... alanced-binary.html
bottom up的代码一般好像比top down的要小很多。但是很别扭的感觉。
回复 支持 反对

使用道具 举报

 楼主| stellari 发表于 2015-9-20 22:53:47 | 显示全部楼层
zwcelesta 发表于 2015-9-18 18:49
之前做leetcode看到过。
可以参考下http://articles.leetcode.com/2010/11/convert-sorted-list-to-balanc ...

多谢提醒!这个题我自己其实也是这么做的,但是没有特别注意它是bottom-up的情况。
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2015-9-21 00:48:30 | 显示全部楼层
我记得当初课上讲算法导论,说到动态规划那章就举了两个递归的例子,一个top-bottom,一个bottom-up
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-21 01:19:06 | 显示全部楼层
我的理解感觉两者区别只是在于  visit() 函数 放在 下一层的recursion函数前面就是top down, 后面就是bottom up, 不知道对不对
回复 支持 反对

使用道具 举报

zealot5209 发表于 2015-9-21 03:11:52 | 显示全部楼层
才开始看list的飘过 以后慢慢研究
回复 支持 反对

使用道具 举报

 楼主| stellari 发表于 2015-9-21 13:10:27 | 显示全部楼层
mnmunknown 发表于 2015-9-21 00:48
我记得当初课上讲算法导论,说到动态规划那章就举了两个递归的例子,一个top-bottom,一个bottom-up

多谢。我们上课时只是说了DP用递归是top-down,填表是bottom-up,没有提在递归中也分top-down和bottom-up。不过或许和教材有关系?我们用的是Jon Kleinberg的算法设计。可能CLRS对这个问题涉及较多?
回复 支持 反对

使用道具 举报

 楼主| stellari 发表于 2015-9-21 13:13:58 | 显示全部楼层
kelvinzhong 发表于 2015-9-21 01:19
我的理解感觉两者区别只是在于  visit() 函数 放在 下一层的recursion函数前面就是top down, 后面就是bott ...

多谢回答。但这意思好像是说“先序遍历”是top down,“后序遍历”是bottom up?这倒是说得过去,但是“中序遍历”算哪种呢?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 08:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表