A*****i
发帖数: 3587 | 1 高中dropout经验尚浅，做过的分布式项目没见过用递归的，当然外组做的data
analysis倒是大片大片的scala和erlang，递归这玩意跟软件设计完全不搭边，感觉就
是搞数学用的 |
|
j*********6
发帖数: 407 | 2 之前开过一篇帖子讨论递归可不可以算是不是用额外空间 因为如果递归的时间复杂度
时logN 那么即使N是1000000，最终的空间也只不过是6。如果真的没有别的不使用空间
的方法 可以和面试官讨论一下递归是否可以算作O1的空间 |
|
x*****p
发帖数: 1707 | 3 我们假设不知道什么叫素数，我们对正整数集合进行如下的定义来定义素数。（这是从
链接上取下来的，也是I63的定义）
(1) 1不是素数 (base case)
(2) a是素数当且仅当a不能被任何小于它的素数整除。
我曾经多次指出，这个定义在用素数定义素数，是不正确的。但看到很多的反驳如下。
1不是素数, 我们考察2，发现小于2的素数集合为空集，于是2为素数。以此再往下递归
，得出所有素数的定义。我想昨天深入讨论此内容的人，都不会反对我的总结吧。关于
"小于2的素数集合为空集"推出"2为素数"，因我的不慎，还做出过郑重道歉。
好，我们仿造这种递归定义，来定义偶数。
我们假设不知道什么叫偶数，我们对非负整数集合进行如下的定义来定义偶数。
(1) 0不是偶数 (base case)
(2) a是偶数当且仅当a与任何小于它的偶数之差为2的倍数。
我从base case开始。0不是偶数。我们考察下一个数1，发现小于1的偶数集合为空集，
于是1为偶数。以此递归，我们得出的偶数是1, 3, 5, 7, ...。实际上，这与我们传统
定义的偶数完全不一样。
大家发现问题在那里么？ |
|
m**x
发帖数: 8454 | 4 不带像lz这样煽自己耳光的好不好
发信人: xiongyp (dreamrain), 信区: WaterWorld
标 题: Re: 关于使用反证法证明 "素数有无穷多个"
发信站: BBS 未名空间站 (Thu May 23 17:23:27 2013, 美东)
我承认，但这个等价不明显，需要有完备性的证明。我同样给出的另一个类似的递归定
义，就不完备。对于一个不明显的递归定义，有必要进行说明或者证明。楼主在这个问
题上一笔跳过，是不严谨的。
发信人: xiongyp (dreamrain), 信区: WaterWorld
标 题: Re: 有人认为反证法的证明过程中不能用某些定理,某些等价定义,我问
发信站: BBS 未名空间站 (Fri May 24 09:02:54 2013, 美东)
等价定义可以，但I63对素数的递归定义，与素数本身的定义不等价。
,. |
|
t**********s
发帖数: 930 | 5 比如下面这个同时求出一个数组中最大和最小值的算法，我已算出其元素之间的比较次
数是3n/2-2,这要比分别扫描数组两次所比较次数2*(n-1)要少。
我的问题是如何让这个递归函数自己记下算出递归的次数？
我对递归函数间如何传递数据很糊涂。
vector minmax( vector V, int l, int u )
{
int m;
vector M( 2 ), M1( 2 ), M2( 2 );
if( u == l ) // one element - no comparisons needed
{
M[0] = V[l]; M[1] = V[u];
return M;
}
if( u-l == 1 ) // two elements - only one comparison
{
if( V[l] <= V[u] )
{
M[0] = V[l]; M[1] = V[u];
|
|
c*****y
发帖数: 90 | 6 1004%10再/10就可以得到4、0、0、1呀。不单独处理if(num/10=0)，我觉得就不会知道
何时跳出
递归，例如在1004这个例子中，你就不知道在1这个数字处要跳出递归。 |
|
r****o
发帖数: 1950 | 7 非递归求二叉树的高度，可以用按层次遍历的方法，层数就是高度。
还有其他方法可以非递归求二叉树高度吗? |
|
c********1
发帖数: 161 | 8 这个问题就难说了，不是一句两句说得清的，可以自己体会下merge sort和quick sort
的算法空间复杂度。另外，递归往深了说就是stack，既然自己外部调用stack可以做到
inplace和计算空间复杂度，那么递归用program stack也就可以用同样的方法计算了。 |
|
|
b******v
发帖数: 1493 | 10 binary search
后来知道binary search非递归的方法，觉得更好用
还有BST里也经常用递归，非常简洁 |
|
a****l
发帖数: 8211 | 11 树型结构里找东西不是需要用递归.我现在做诸如扫目录等事就不用递归. |
|
|
|
p*****2
发帖数: 21240 | 14 1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
自变量为一维的问题。
感觉这个可以解决呀。 |
|
|
i**********e
发帖数: 1145 | 16 orz.. 哈哈，搞糊涂了。
这个非递归还是不好写，面试时写递归的已经很好了。 |
|
b*****n
发帖数: 143 | 17 Postfix evaluation 的经典解法是把数字放到堆栈里，遇到算符就把最上面的两个数
字拿出来做计算，再把结果放进堆栈，以此类推，直到结束。
还有一个从右往左扫描的递归解法:
// 假设postfix数字只有一位
double eval_postfix(const string& postfix, size_t& idx) {
char c = postfix[idx];
if (c == '+' || c == '-' || c == '*' || c == '/') {
double right = eval_postfix(postfix, ++idx);
double left = eval_postfix(postfix, ++idx);
return calc(left, c, right);
}
else
return c - '0';
}
既然堆栈的解法是从左往右扫描，有没有从左往右的递归解法？ 大家讨论讨论。 |
|
p*******8
发帖数: 344 | 18 RT, 比如subsets, permutation, 电话号码等，需要能写出非递归的算法吗？对于非递
归算法，一般的思路是怎样的？谢谢！ |
|
j*****y
发帖数: 1071 | 19 permutation 可以用 next permuation 实现非递归 |
|
|
p*******8
发帖数: 344 | 21 那我就不打算去弄非递归的了，主要也就面试用用，真问到就说不会了，我也觉得多数
面试也没这种要求 |
|
h**6
发帖数: 4160 | 22 我现在能不用递归就不用，尽量避免DFS，改写BFS。 |
|
f*********g
发帖数: 110 | 23 leetcode 上Unique Paths, 我写了一个递归，但不是很明白这个递归的时间复杂度和
空间复杂度。我觉得空间复杂度是O(m*n),时间复杂度是O(m*n).不知道对不对，请大家
指点。
public int uniquePaths(int m, int n) {
if(m==1|| n==1) return 1;
return uniquePaths(m-1,n)+uniquePaths(m,n-1);
} |
|
p*****2
发帖数: 21240 | 24 来自主题: JobHunting版 - 关于尾递归
尾递归的实现，不过Scala不支持这种递归的优化。
def H(value:Double, n:Int):Double={
H_helper(Array(value),n)(0)
}
def V(value:Double, n:Int):Double={
V_helper(Array(value),n)(0)
}
def H_helper(arr:Array[Double], n:Int):Array[Double]=n match{
case 0 => caclV(arr)
case _ => {
val ar=new Array[Double](arr.length*2)
for(i<- 0 until arr.length) {
ar(2*i)=arr(i)-1
ar(2*i+1)=arr(i)+1
}
... 阅读全帖 |
|
b*****o
发帖数: 715 | 25 来自主题: JobHunting版 - 关于尾递归 硬币找零问题（100用1，5，10，25有几种表示方法）能不能写成尾递归？
我只能想出用普通递归或者memoization的办法。 |
|
p*****2
发帖数: 21240 | 26 来自主题: JobHunting版 - 关于尾递归
miss掉的大牛的回复。感觉你的理解稍微有点问题。我是这样理解的。
1. 尾递归的本质就是循环
2. 纯FP是没有循环的，所以才需要尾递归。如果有循环的话，确实没必要这么搞。 |
|
r********d
发帖数: 7742 | 27 就这一个概念，就主导了可超过一半的主要算法和超过一半的主要数据结构。
一定要好好理解啊。
要理解递归，先要理解递归啊。 |
|
|
r********d
发帖数: 7742 | 29 尾递归就是伪递归，咱们是不是把它转换成循环就好了？ |
|
z****e
发帖数: 54598 | 30 当然算咯
而且一般写dp都是用循环实现的
而不是递归，递归效率偏低
... |
|
g**G
发帖数: 767 | 31 DP一般你会写出最优的子问题的递归方程对吧，其实就是递归
只不过一般DP是自底向上的，Recursion+cache是自顶向下的，写的顺序不一样
DP效率高，但理解起来可能比较困难
Recursion+cache的话，想起来比较顺溜，但是其实虽然中间结果cache了，但重复的
function call还是太多了，比dp效率低 |
|
r*******h
发帖数: 315 | 32 最直观的递归往往会重复计算一个子问题，DP主要目的是解决子问题的重复解带来的指
数级开销，但是并不意味着DP不能和递归共存。 |
|
b*********n
发帖数: 368 | 33 小弟外行，在刷leetcode，请问在时间和空间复杂度相同的情况下，递归和迭代哪个更
好，自己感觉递归更好些，逻辑清晰，不知道面试时有什么要求吗？ |
|
a**********0
发帖数: 422 | 34 不递归无非就是分成两半 后一办reverse 然后插入到第一份去 我懒得写这么多代码
于是用了递归方法 结果超时 在自己电脑上跑了几个小case 都过了 不知道大家什么看
法 又超时了！
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if(head == null)
return;
if(head.next ==null)
return;
if(head.next.next == null)
ret... 阅读全帖 |
|
m*********a
发帖数: 3299 | 35 Given n pairs of parentheses, write a function to generate all combinations
of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
递归很容易
void generateParenthesisRecr(string str,int n,int l,int r,vector&
result){
if (l==n && r==n){
result.push_back(str);
return;
}
if (l
if (l>r) generateParenthesisRecr(str+")",n,l,r+... 阅读全帖 |
|
m*********a
发帖数: 3299 | 36 大家很牛啊，想得清楚>2可能的非递归的
左右二种选择就比较难了非递归就比较难了 |
|
|
|
|
s**x
发帖数: 7506 | 40 关键是面试者对这个怎么定义， 稀里糊涂的面试者还是很多的， 所以， 沟通时第一
位的。
常识是递归使用stack to store a lot of things (return address, frame pointer,
parameters etc) on each call, 所以递归显然不是 O(1) space, 除非只调用 有限
次数。 说得时候尽量浅显易懂， 如果面试者水平有限， frame pointer 之类的就不
用提了， LOL. |
|
s****a
发帖数: 794 | 41 如果是没想到要递归的话 可能是一时蒙住了或者正好碰上知识盲点 这个可能还是要看
其他人的面试结果综合决定 但是如果是在理解了算法后还不能顺利写出递归 那就是写
代码的能力有问题 基本上就是red flag |
|
发帖数: 1 | 42 给个不能用递归的理由？
: 谁TM在工作的时候用递归，早大巴掌甩脸上了
|
|
x*****p
发帖数: 1707 | 43 我开此贴的目的，是为了证明，对一个概念的定义，是不能用递归方法来进行的，这也
是I63开的高楼的错误所在。因为递归定义的base case的判断，就是来源于一个概念的
原始定义。 |
|
x*****p
发帖数: 1707 | 44 昨天我的很多回帖，许多人看不懂。我质疑在递归定义中1为什么不是素数，许多人觉
得这是再明显不过的事情，可是在离开素数原始定义的前提下，这却很不明显。所以我
今天开贴举一反例，证明递归定义的错误所在。 |
|
j****q
发帖数: 204 | 45 大哥。。你的递归定义没有问题啊，只是你说的偶数其实是公认的奇数而已，原因就在
于你的base case和本该定义偶数的base case不一样。
那么你是不是认为把你的base case改为0是偶数，你的递归定义仍然是错的？因为你不
知道什么偶数？ |
|
p*****2
发帖数: 21240 | 46 【 以下文字转载自 JobHunting 讨论区 】
发信人: peking2 (scala), 信区: JobHunting
标 题: 关于尾递归
发信站: BBS 未名空间站 (Tue Jan 29 14:37:44 2013, 美东)
大家能不能给点例子不能转变成尾递归的？我想写写看。谢谢。 |
|
e****d
发帖数: 333 | 47 对，就是BST不是BT。
怎么用栈替代递归呢？有没有通用的算法，把递归转化为栈？ |
|
z****e
发帖数: 54598 | 48 呸，java也不用递归，fp才用递归，估计是fp转行的 |
|
g*******t
发帖数: 7704 | 49 递归就怕堆栈不够，
能写出递归的都不是学生了，
汽车里的电脑板，就巴掌大，ram肯定没多少，堆栈都是在ram里，
如果学过单片机， 堆栈一般是在内存的最底部， |
|
G**Y
发帖数: 33224 | 50 每次递归得多少overhead呀，
现在compiler能提高递归的效率吗？ |
|
