h****e
发帖数: 928 | 1 不用专门练recursion的，还是多看多做题吧。有的题目recursive的解法
非常明显，难的反而是改成非recursive的，例如binary tree的遍历。
也有的题目recursive的解法不明显，但是最后做下来要比非recursive的
简洁。还有的题目硬用recursive反而不优。
DP的不少问题都可以用recursion来解，但是往往为了优化你还得改成
bottom-up的。不然你就多找些DP的问题来练练吧。
http://people.csail.mit.edu/bdean/6.046/dp/ |
|
b********e
发帖数: 386 | 2 sort, link list, trees are great study cases for recursion.
For link list and trees, cuz these structures are defined recursively.
Sometimes, the recursive solution is more intuitive.
Only for linked list:
a few examples:
1: Get the length of the link list
2: Get the max/min value of linked list
3: Get the nth/last nth number of the list
4: Reverse linked list(There should be 2 recursive version, one with
carryover)
5: Sort linked list (this is hard)
6: Copy linked list
7: Delete a value in a so... 阅读全帖 |
|
H**********y
发帖数: 7928 | 3 这个，我觉得需要慢慢琢磨
看到一个题，recursion的，就想怎么变，实在想不明白，就放狗
请大家推荐recursion以及把recursion转变为iteration的资料。
谢谢。 |
|
B*****g
发帖数: 34098 | 4 ***既然是授渔，那就没有鱼，要鱼的请绕行.***
首先，这类复杂sql问题，建议大家用CTE(和Recursive无关)，每一步都分开，思路会
清晰得多
with t1 as(
select ....
from ....),
t2 as (
select...
from t1, .....),
....
select
from tn
用过oracle connect by的同学，Recursive CTE实现了类似功能，而且是ansi的，推荐
大家使用，当然，本题用connect by也可以
对于解决本题，思路和用Analytic Functions类似，就是要达到排序后分组的目的，以
原题数据为例，如果有以下标记，用group by user，标记值可得到min(startdate),
max(enddate)即可
User StartDate EndDate 标记值
1 12/2/2011 1/16/2012 0
1 3/4/2012 3/24/2012 1
1 4/5/2012 4/26/2012 1
1 5/14/2012 6/7/2012 1
2 3/5/2012 7/30... 阅读全帖 |
|
y*y
发帖数: 4 | 5 Hi,
I want to write a shell script to display all the
occurances of bin
directory, the code like this:
#!/usr/bin/ksh
recursive ( )
{
for i in *
do
if [[ $i == bin ]]
then print "$(pwd)/$i"
fi
if [[ -d $i ]]
then cd $i
recursive
fi
done
}
#call the function recursive
cd /
for i in *
do
recursive
done
#end of file
The problem is only the first directory in cu |
|
f*********m
发帖数: 726 | 6 我知道如果函数func不是recursive的话，func(type arg)和func(type & arg)的区别
，比如func(int i)和func(int& i)。但func是recursive的话，用不用reference有什
么区别？
比如：
void func(type arg){
...
func(arg+1);
...
}
与
void func(type& arg){
...
func(arg+1);
...
}的区别？
recursive会创建很多stack overhead,这是不是说func(type arg)会创建很多arg的
local copy在stack里边，而func(type& arg)只会有一个arg itself?
谢谢。 |
|
t****a
发帖数: 1212 | 7 从recursion到iteration，一步步来吧。recursion多美多简洁啊，改写成iteration有
时候非常丑陋。
也许有一天，编译器技术可以聪明到把recursion自动转换成iteration，那个时候就不
用担心这个事情了。 |
|
f*********m
发帖数: 726 | 8 请大家推荐recursion以及把recursion转变为iteration的资料。
谢谢。 |
|
w****x
发帖数: 2483 | 9
一般是不是只有tail recursion 才比较好做成iteration, 也不是所有的recursion都
可能做成iteration的吧 |
|
j******8
发帖数: 746 | 10 If the question can be implemented by both recursive and non-recursive
methods? |
|
d********i
发帖数: 582 | 11 recursive 和 non-recursive 代码互相转化，有规律可循。 很简单的。 |
|
z***y
发帖数: 73 | 12 recursive消耗栈空间，同时函数调用有上下文切换的消耗。
iterative效率比recursive高，但是代码可能就没有recursive清晰明了。 |
|
k*********e
发帖数: 2039 | 13 在看java启蒙书。书后有条习题，要求用recursive的方法，写一个method，check一个
整数n能不能整除5。
能不能整除5，只要 n%5==0，不就行了么，怎样才能写成recursive呢？是不是题目的
意思就是不用%，用recursive写一个类似%的method?
望大家指教。 |
|
c**m
发帖数: 30 | 14 One of my co-workers once was very impressed by someone he interviewed
because that person reversed linked-list recursively.
I never thought of this as a recursion problem.. Actually I am not sure how
to do it recursively. Anyone care to pitch in? |
|
m********a
发帖数: 128 | 15 Java has limit on the # of recursive locks by the same thread.
can someone give an example of such locks? thanks!
Must the recursive locks be locking different objects? so this means the
limit is on the # of locks one thread can hold, right? but why recursive
locks? |
|
p*****2
发帖数: 21240 | 16 recursion还好吧？recursion的DP也好好吧？
我觉得难的是iteration的DP。 |
|
f*********m
发帖数: 726 | 17 谢谢，重新给个例子：
void func(type arg){
...
arg += 1;
func(arg);
...
}
vs.
void func(type& arg){
...
arg += 1;
func(arg);
...
}
当然，传递效率是一个问题。除了这个以外，这两种用法在recursive中还会不会有其
他的不同，比如最终结果。感觉上是不用reference那么各个arg是独立的，不过在
stack理由很多的arg copy，他们的值不一定一样。而用了reference,stack中只有一个
arg,每一次对arg的修改都会影响到整个stack，因为整个stack中只有一个arg。不知我
的理解对否？
recursive应用中哪种arg更好呢？ |
|
f*********m
发帖数: 726 | 18 据说所有recursion都有对应的iteration,但有的不好转变。
说是可以用stack模拟递推过程，但有很多细节要结合具体的题，这就不好搞了。 |
|
d**********o
发帖数: 11 | 19 以preorder为例
我知道recursive的该怎么写，也知道stack的方法该怎么写
但是我不知道是怎么能从recursive的方法看出来stack的应该这么写
求问这个思考的过程
多谢！ |
|
d**********o
发帖数: 11 | 20 没有人谈谈思路吗？
我要的不是code啊，code我自己也会写
难道大家也是看到书上这么写，验证是对的以后然后背下来了？
那以后遇到一个不同的情况，recursive的一个什么函数，让你用stack替换成非
recursive的，怎么下手呢？ |
|
|
a***e
发帖数: 413 | 22 这道题的iterative解法比较好懂，但看到下面这个recursive的就觉得想不清楚了。一
直对树的recursion挺糊涂的。怎么才能搞清楚呢？多谢！
class Solution {
public:
void flatten(TreeNode *root) {
helper(root, NULL);
}
TreeNode *helper(TreeNode *root, TreeNode *tail){
if (NULL==root) return tail;
root->right = helper(root->left, helper(root->right, tail));
root->left = NULL;
return root;
}
}; |
|
a***e
发帖数: 413 | 23 这道题和1我都是觉得iterative的比recursive的好写，看别人答案也更容易懂，（压
根儿没写出通过的recursion来）。下面这个都不知道思路是怎么地，特别是怎么能
connect(dummy.next);就保证 dummy.next 就是下一层的第一个了呢？见笑哈。
如果明天还看不出来就去VS里面调调。。。。。。
void connect(TreeLinkNode *root) {
if (root==NULL) return;
TreeLinkNode dummy(-1);
for (TreeLinkNode *cur = root, *prev=&dummy; cur; cur = cur->next)
{
if (cur->left!=NULL){
prev->next = cur->left;
prev = prev->next;
}
... 阅读全帖 |
|
k********4
发帖数: 858 | 24 基本上能用recursion的要求你不用recursion，都可以用stack代替。 |
|
w*****h
发帖数: 139 | 25 This is a typical BOM question.
SQL99 already supports recursive SQL.
You have a table: assembly(part, subpart,...)
CREATE RECURSIVE view all_subparts(Major, Minor) AS
SELECT PART SUBPART
FROM assembly
UNION
SELECT all.Major assb.SUBPART
FROM all_subparts all, assembly assb
WHERE all.minor = assb.PART
SELECT * FROM all_subparts |
|
O******e
发帖数: 734 | 26 I know one can export variables and macros from top-level
invocations of make to the sub-levels of make that are invoked
recursively. However, I have a number of static pattern rules
and implicit pattern rules that I would like to define in the
top-level makefile and have them passed down to the recursively
invoked sub-level make. Is this possible? I prefer not to
write the pattern rules into a separate file and have the top-level
and sub-level makefiles include this file.
Thanks! |
|
t****t
发帖数: 6806 | 27 tail recursion can be transformed to iterations
on the other hand, some iterations can be transformed to tail recursion as
well, i guess
in your case, i guess
reverse(head)=head ? [reverse(head->next), head] : null
how |
|
z***t
发帖数: 14 | 28 所有的recursion algorithm都可以写成iterative algorithm + stack.这个时候的
stack是在heap上的。而一个程序stack的大小远小于heap的大小，既然这样，compiler
为什么不遇到recursion call就在heap上做? |
|
e*******o
发帖数: 4654 | 29 如何找出所有的recursive function？
copy 一段代码到一个function，一不小心，拷贝的代码调用了这个function。
out of memory，太恶心了。
有没有方法可以检测所有的recursive function，这样，就可以很快发现问题。 |
|
w*s
发帖数: 7227 | 30 Error: (node) warning: Recursive process.nextTick detected. This will break
in the next version of node. Please use setImmediate for recursive deferral.
at maxTickWarn
一大堆这个，
基本就是
https://github.com/joyent/node/issues/6065
问题是我的multer是1.0的版本了，大家碰到过吗？ |
|
B*********h
发帖数: 800 | 31 ☆─────────────────────────────────────☆
newnewlife (newlife) 于 (Fri Jan 19 16:55:23 2007) 提到:
圆圈上顺时针排列着1,2,3,....2000 这
2000个数. 从1开始,顺时针隔一个拿走一个(1最先被拿走,下一个是3被拿走).
问最后剩下是哪一个数字.
this is a question from 精华区 and already have a solution.
here i just want to sovle it using recursion.
the recursion formula is:
f(2n) = 2f(n); since if it is even then the odds are eliminated first and
start with the game starting with the first even number again.
f(2n+1)=2*{ [f(n)+1]%n}; after first round the game st |
|
i***0
发帖数: 8469 | 32 Solve this task using recursion. how to ?
“Given a string build all possible non-zero length substrings from it.
Example
Input:
abc
Output:
a
b
c
ab
ac
bc
abc
Solve this task using recursion.” |
|
b*******e
发帖数: 6920 | 33 对方ID:
recursive
Feedback (+/-/0):
+
具体交易内容:
US AIRWAYS MILEAGE
我的评价:
交易愉快 |
|
|
v*******7
发帖数: 187 | 35
tree,
child
I am wondering whether such solution exists. Traversal of a tree without
recursion
can be done by either Queue-based or Stack-based. But if the space required
is no
more than constant, it means that the space allocated to Queue or Stack is
constant.
But I have no idea on how to deal with it by using Q/S with constant space
forever. |
|
c******t
发帖数: 1500 | 36 BFS在CLRS上的解法就不是recursion呀
DFS是的，因为用到了stack |
|
h*****g
发帖数: 312 | 37 【 以下文字转载自 Quant 讨论区 】
发信人: salientxu (salientxu), 信区: Quant
标 题: fibonacci recursion
发信站: BBS 未名空间站 (Wed Aug 4 16:39:13 2010, 美东)
算fibonacci number 的resursion
int F(int n)
{ if (n==0) return 1;
if(n==1) return 1;
return F(n-1)+F(n-2);}
这个算法的空间复杂度是多少？ |
|
k*********6
发帖数: 738 | 38 见到这样的题就很痛苦。大家都是怎么准备的呢？有没有个收集好的recursion, dp 题
集？
谢谢！ |
|
f*********m
发帖数: 726 | 39 对于recursive总是掌握不了，大家有什么比较好的这方面的学习资料推荐吗？
谢谢。 |
|
h****e
发帖数: 928 | 40 面试不会只问你recursion的题吧。尽力而为吧。:) |
|
|
|
f*********m
发帖数: 726 | 43 "recursion就是DFS。"
这个心得恐怕需要做过很多题才能体会得到。 |
|
d**e
发帖数: 6098 | 44 我觉得跟recursive没关系，区别应该是一样的。
但我觉得下面的例子不太好。arg+1应该是一个新的临时变量了。 |
|
g*********e
发帖数: 14401 | 45 recursive会创建很多stack overhead,这是不是说func(type arg)会创建很多arg的
local copy在stack里边，而func(type& arg)只会有一个arg itself?
我觉的你说的没错。
reference就是一个指针吧，函数传递的就是指针。
不用ref的话，要是arg是一个很大的type，传递起来效率低，每次copy arg占用大量
stack空间。 |
|
c********t
发帖数: 5706 | 46 是不是面试官都非常反感recursion？
是不是如果能写iteration，即使codes长一倍，复杂一倍也好？ |
|
d**********x
发帖数: 4083 | 47 that depends.
if you can avoid recursion, why not
if you cannot, just let it be |
|
j******2
发帖数: 362 | 48 比如binary search，两种都可以，用iteration会不会快点？
比如binary search in rotated array, 只能用recursion。
大家说说是不是这个理儿？
菜鸟问题，见笑了。 |
|
c********r
发帖数: 286 | 49 希望对Recursion Big-O complexity 分析有些疑惑的童鞋有些帮助
Recurrence Algorithm Big-O Solution
T(n) = T(n/2) + O(1) Binary Search O(log n)
T(n) = T(n-1) + O(1) Sequential Search O(n)
T(n) = 2 T(n/2) + O(1) tree traversal O(n)
T(n) = T(n-1) + O(n) Selection Sort (other n2 sorts) O(n^2)
T(n) = 2 T(n/2) + O(n) Mergesort (average case Quicksort) O(nlog n) |
|
c********t
发帖数: 5706 | 50 问个弱问题。
如果一个recursion使用O(1)空间，在执行过程中，它调用了自己n次，请问空间复杂度
是不是就是O(n)? 如果它使用了O(m)空间，是不是最后空间复杂度为O(m*n)? |
|
