由买买提看人间百态

topics

全部话题 - 话题: 递归
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)
p*****2
发帖数: 21240
1
来自主题: JobHunting版 - 关于尾递归

大牛谦虚了。我也是刚学。看看到底尾递归都能做什么。
p*****2
发帖数: 21240
2
来自主题: JobHunting版 - 关于尾递归

尾递归
def C(m:Int, n:Int):Int={
recursion(m, 0, None)(n)
}

def recursion(m:Int, i:Int, arr:Option[Array[Int]]):Array[Int]= i match{
case _ if i==m+1 => arr.get
case 0 => recursion(m, 1, Option(Array[Int](0)))
case _ => val ret=process(i,arr.get); recursion(m, i+1, Option(ret))
}

def process(i:Int, arr:Array[Int]):Array[Int]={
val ar=new Array[Int](i+1)
ar(0)=1
ar(i)=1

1 until i foreach(j=>ar(j)=arr... 阅读全帖
p*****2
发帖数: 21240
3
来自主题: JobHunting版 - 关于尾递归
今天问了scala group的人了,确实所有的recursion都可以转换成尾递归。这个貌似没
什么悬念了。
y****n
发帖数: 743
4
来自主题: JobHunting版 - 关于尾递归
加一点难度。两个函数相互递归
public static double H(double val, int n)
{
if (n == 0)
return val;
else
{
double left = V(val - 1, n - 1);
double right = V(val + 1, n - 1);
return Math.Sqrt(Math.Abs(left * right));
}
}
public static double V(double val, int n)
{
if (n == 0)
return val;
else
{
double up = H(val * 2, n - 1);
double down = H(val / 2, n - 1);
return Math.Sqrt(Math.Abs(up + down));
}
}
p*****2
发帖数: 21240
5
来自主题: JobHunting版 - 关于尾递归

那怎么对尾递归这么熟?
p*****2
发帖数: 21240
6
来自主题: JobHunting版 - 关于尾递归

好呀。一起学习呀。今天准备总结一下尾递归,大牛帮助点评一下。
p*****2
发帖数: 21240
7
来自主题: JobHunting版 - 关于尾递归
总结了一下尾递归
http://blog.sina.com.cn/s/blog_b9285de20101i5s1.html
p*****2
发帖数: 21240
8
来自主题: JobHunting版 - 关于尾递归

这个应该比yishan那个容易很多。memoization与尾递归并不矛盾吧?
b******7
发帖数: 92
9
后序遍历非递归bug free就很难了,像这种遍历过程中还要进行复杂判断的就更麻烦了
p*****2
发帖数: 21240
10
干嘛要写非递归
g***9
发帖数: 159
11
RT. 只看最后递归的call是不是原函数吗..
有么有可以debug之类或其他方法来确认? 谢谢!
p*****2
发帖数: 21240
12

好久没研究了。当时稍微研究了一下尾递归,感觉还是挺麻烦的。
J****3
发帖数: 427
13
来自主题: JobHunting版 - 递归这个概念实在是太重要了
re +1 楼上名字都是递归!赞!
t***t
发帖数: 6066
14
来自主题: JobHunting版 - 递归这个概念实在是太重要了
俺们从小就学数学归纳法,就是递归嘛。
r*******n
发帖数: 3020
15
来自主题: JobHunting版 - 递归这个概念实在是太重要了
递归是CS的核心啊
t***t
发帖数: 6066
16
来自主题: JobHunting版 - 递归这个概念实在是太重要了
俺们写的程序都是原始递归集的子集。
m********s
发帖数: 55301
17
来自主题: JobHunting版 - 递归这个概念实在是太重要了
楼主递归了。
f********4
发帖数: 988
18
来自主题: JobHunting版 - 递归这个概念实在是太重要了
刷题的时候总是忍不住看答案。。结果面试时候一遇到没写过的递归,就紧张。。哎。
。。智商真令人捉急。
s*****e
发帖数: 1679
19
来自主题: JobHunting版 - 递归这个概念实在是太重要了
对递归还是了解不透彻啊,感觉似懂非懂,有谁给指导下?
j*****n
发帖数: 1545
20
来自主题: JobHunting版 - 递归这个概念实在是太重要了
很多 算法 递归写出来 实在是漂亮。就是 debug 太难了。。。
p*****2
发帖数: 21240
21
来自主题: JobHunting版 - 递归这个概念实在是太重要了
LZ说说需不需要理解尾递归呀?
s*******n
发帖数: 305
22
来自主题: JobHunting版 - 求个递归复杂度答案
每每遇到递归这种的分析就抓瞎, 围观。
m******s
发帖数: 204
23
来自主题: JobHunting版 - regular expression递归的复杂度多少?
最差情况分析:
参见http://leetcode.com/2011/09/regular-expression-matching.html
zhong zhang提到运算时间较长的情况:
s[] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
p[] = "a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*b"
注意这个例子没法early out,假设s的长度是n,不考虑p的长度,那么递归的时间函数
表达式近似是:
T(n) = T(n-1) + T(n-2) +。。。
所以T(n)是2^n.
请指正。
z****e
发帖数: 54598
24
可以用循环实现啊
为什么一定要用递归
s********u
发帖数: 1109
25
哦我大致明白了,就是通过space cost来换取time cost的,就是dp?
比如这个题:
给一个bool IsWord(string)的API, 判断能否把一个string分割成单词, 并给出所有
的答案。
如果要求用dp的话,递归还是要比循环好写很多吧。。
z****e
发帖数: 54598
26
dp就是数学归纳法,从前面已知的结果推导出当前的结果
循环一般比递归节省时间和空间
s*****h
发帖数: 155
27
你说的cache的这种属于自顶向下的DP,应该算是递归,需要一个global var
CLRS专门有一章讲DP的,有背包,编辑距离以及折棍子几个例子,讲得很清楚
s*****r
发帖数: 108
28
DAG 是有向无环图
有了 toposort 才知道应该怎样从前往后递推
否则的话得写记忆话搜索
所以进行 DP 通常这两种实现;知道了自底向上的顺序用递推
不知道又不想拓扑排序后再推就用递归 用这种形式感觉不怎么动脑子把转移方程放那
开头判断个边界就好了 好像显得没有递推实现高端
上面的回复大多不准确或者错误的
直到 jianglai 说到了本质 引入了拓扑排序好像蒙了一下 但把模型转化为 DAG 是
必要的 只是我们刚开始碰到的 DP 大都划分阶段显然 知道了推的顺序 其实在一些树
或图上的 DP 不容易递推实现 因为要么得先拓扑排序从边界开始向后推 要么用了巧妙
的实现方式那是非常值得一读的程序
s***e
发帖数: 403
29
DP是剑法
递归是内功
相同的剑法可以用不同的内功驱动
就是这个意思。
s********u
发帖数: 1109
30
来自主题: JobHunting版 - wordBreak问题,有非递归的方法么
之前有人放过这个题,就是提供一个bool isWord(string s)的函数,要求得到一个
string拆成若干个word的所有组合,word之间用空格隔开。
自己写了下,用递归 + memoization,想问问这个题有iteration的做法么?如果是每
个string有唯一解(只有一种拆法)呢?
vector wordBreak( string str, map >& cache){
vector vs;

if( str.empty() ){
vs.push_back(str);
return vs;
}

if(cache.count(str) > 0)
return cache[str];

string prefix;
string suffix;
vector segSuffix;

for( int len = 1;len <= str.s... 阅读全帖
p*****2
发帖数: 21240
31
FP里只有递归,没有循环
s********u
发帖数: 1109
32
如果compiler如此智能的话,可以随便用递归而不用考虑效率了吧。。反正overlap会
自动解决

n
s********u
发帖数: 1109
33
嗯,在理论上我是这么总结的:
**Divide and conquer :** 将问题分成几个部分,每一部分问题互相不重叠,假定每
个部分都可以得到解决进行递归调用,合并每一部分的结果。例如Merge Sort,Quick
Sort。
**Dynamic Programming**:对于具备最优子结构以及子问题重叠特性的问题,尽可能
不重复计算每个subproblem,将计算结果存储下来,以确定后驱问题的结果。与贪心算
法的区别是,在计算后驱问题时,可能会reconsider前驱问题的解,从而改变全局path

**Greedy Algorithm** : 当前问题的最优解只取决于前驱问题的最优解,即局部最
优解推广至全局最优解。如Dijkstra算法。
**Backtracking**: 一种暴力(穷举)的深度优先搜索法,直至检索到节点空间的尽
头。Tree或Graph的DFS,是backtracking的special case。
但实际上很多问题就算满足dp的条件,用dp却非常繁琐,比如8皇后问题,或path sum
问题。是可以用dp做,但实际上没必要。用b... 阅读全帖
s******y
发帖数: 416
34
DP和递归不是一个层面的概念,不能比较适用范围…
j******o
发帖数: 4219
35
来自主题: JobHunting版 - 面试时 迭代还是递归
很长的一段时间以来,大家普遍认为都认为迭代好于递归
d**e
发帖数: 6098
36
来自主题: JobHunting版 - 面试时 迭代还是递归
我觉得是先写递归,除非要求写迭代。
因为首先是需要说服人家你的算法是对的,所以先用比较简单直观的做法令人容易理解
来说服他/她。
又除非那个算法迭代就已经很简单易懂,比如fibonacci。
a**********0
发帖数: 422
37
来自主题: JobHunting版 - reorder list 递归方法超时
原因找到了 递归method之中有一个线性的操作 这样会导致整体的n平方复杂度
a**********0
发帖数: 422
38
来自主题: JobHunting版 - reorder list 递归方法超时
你的递归中没有O(n)的操作 我的有 所以用 length不好 应该直接给出最后一个节点
的指针
w********s
发帖数: 1570
39
为啥湾区的面试都搞那么复杂的?
国内面试就问问语言知识,过去项目,哪来那么多递归,dp?你干活的时候用过么?
g*********e
发帖数: 14401
40
干活的时候dp 递归 位运算都要用
g*********e
发帖数: 14401
41

毫不扯淡。
比如你有个有向图,图里每个node都可以是一个小图,你要给这个大图做优化,递归最
好写。
还是这个图,求它的topo order算dependency,就得dfs。
电路里面做静态时序分析,那都是dp。
用位来存储一些数据结构,或者做查找表,节约空间。更抠的还有把flag存到指针低位
a*******m
发帖数: 626
42
哪这么简单,只能说你面过的国内公司太少。
国内问项目实践多,感觉还是湾区这边简单,靠刷题就可以。在国内只靠刷题基本没戏
,更看重有没有真的做过东西。

为啥湾区的面试都搞那么复杂的?
国内面试就问问语言知识,过去项目,哪来那么多递归,dp?你干活的时候用过么?
z**a
发帖数: 69
43
好角度,写了个,过了LC,差不多是非递归中序遍历二叉树的思路。
class Solution {
public:
class stack
{
public:
char c;
int flag;
stack(char c, int flag)
{
this->c = c;
this->flag = flag;
}
};
vector generateParenthesis(int n) {
int left = 0;
int right = 0;
vectorrecord;
vectorresult;
stack temp(0,0);
record.push_back(stack('(', 0));
le... 阅读全帖
p*****2
发帖数: 21240
44

可以用尾递归
C********e
发帖数: 492
45
也算吧,
比如inorder遍历tree,不论是用stack还是递归,其实都是logN的space复杂度
真正的O(1)space解法,需要靠morris算法来
a*****a
发帖数: 46
46
如果递归算空间的话,怎么O(1)判断一个链表是不是palindrome?
b******g
发帖数: 3616
47
都递归了还能算O(1) space啊....
s**********5
发帖数: 19
48
递归转iterative用stack
public int depthSum2 (List input){
Stack> nstack = new Stack<>();
Stack dstack = new Stack<>();
nstack.add(input);
dstack.add(1);
int total = 0;
while(nstack!=null){
int depth = dstack.pop();
for(NestedInteger i: nstack.pop()){
if(i.isInteger()){
total += i.getInteger()*depth;
} else{
dst... 阅读全帖
t******4
发帖数: 134
49
来自主题: JobHunting版 - 借人气问个C递归函数的问题
加一个parent指针? or
加一个域标识root?
如果不能修改数据结构
送进函数之前特殊处理root,处理完进去递归

:目的是对根的处理和其他层不一样,需要保留判断条件。
:送之前存一个当然是搞笑了。
:多一个参数可行,就是看起来怪怪的,调用的时候传递两个相同参数。如果只允许一
个参数,有没有别的办法?
s****a
发帖数: 794
50
用到递归 dp的时候公司再去招个会写的?
要是用平时工作做标准的话,招个高中生就够了
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)