📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 6648| 回复: 7
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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

哪位版友知道的,请不吝赐教。

上一篇:recursive的题目一直都感觉有点绕,求指点
下一篇:求cc150的c++参考答案
🔗
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?这倒是说得过去,但是“中序遍历”算哪种呢?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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