一亩三分地

 找回密码 注册账号

扫描二维码登录本站

微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
查看: 669|回复: 3
收起左侧

[高频题] 刷题感悟一: 一切都是递归

[复制链接] |只看干货 |高频题, 刷题
我的人缘0

升级   40.5%


分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (211)
 
 
0% (0)    👎

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

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

x
divide and conquer不用说了,肯定是递归呀

dfs,用stack肯定是递归对吧

dynamic programming,从子问题中解决原问题,只不过加了一个cache/memo来记录子问题,用空间换时间

backtracking,也是递归对吧, 只是子问题之前没有overlap所以时间复杂度比dp高很多

binary search其实也可以算递归,每次通过一个local的condition(砍掉左边还是右边)来决定如何把原问题的size降低一半, 然后不断重复

问啥递归这么强大呢?这个lz是外行只能引用一下wiki

It follows that it is difficult to devise a computable function that is not primitive recursive

https://en.wikipedia.org/wiki/Primitive_recursive_function#:~:text=In%20computability%20theory%2C%20a%20primitive,determined%20before%20entering%20the%20loop).

所以从计算理论上来说recursion是相当强大的,所以各种方法看成是递归的变种也不奇怪。

只不过这个perspective虽然general,但是还缺少很多细节。实际做题的时候只用递归可能会太慢。这时候就想办法转成iteration的方法来加速。有很多细节和奇技淫巧lz下次再总结吧

大家觉得有用给点大米呗~~

上一篇:你们都怎么学习递归
下一篇:brain teaser求讨论!金工买方OA
我的人缘0

升级   5.93%

duao119 2020-10-29 10:15:20 | 显示全部楼层
本楼: 👍   100% (7)
 
 
0% (0)   👎
全局: 👍   99% (256)
 
 
0% (2)    👎
楼主有没有听说过
"All iterative functions can be converted to recursion; All recursive functions can be converted to iteration"
所以要说一切都是循环也可以

评分

参与人数 1大米 +2 收起 理由
14417335 + 2

查看全部评分

回复

使用道具 举报

我的人缘0

升级   73%

lifesuckad 2020-10-29 10:25:11 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   87% (260)
 
 
12% (37)    👎
本帖最后由 lifesuckad 于 2020-10-29 10:27 编辑






那你还不如说一切问题都是数学。computer science is a small part of math.  
递归也不过是一个数学公式而已。
所有算法都可以抽象成数学, 然后证明。你都不用写代码。



评分

参与人数 1大米 +2 收起 理由
14417335 + 2

查看全部评分

回复

使用道具 举报

我的人缘0

升级   45.29%

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (636)
 
 
0% (2)    👎
有一定道理。刷题网里相关的题多因为分治法通常能带来从n^2 到nlogn的性能提高。应用比较广泛。再往下优化规律性就不是很强了,需要case by case。我印象里要求O(n)的题递归的少。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

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