解recursion的思路是什么?

m
midpasse
楼主 (未名空间)

我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断
去碰试,看看能不能碰出来一个正确的算法。

比如这么简单一道

We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3, ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3
ears, because they each have a raised foot. Recursively return the number of "ears" in the bunny line 1, 2, ... n (without loops or multiplication).

我的尝试:
public int bunnyEars2(int bunnies) {
if (bunnies==0){
return 0;
}
else {
return bunnies+bunnies%2+bunnyEars2(bunnies-1);
}
}

我试了好几个表达式,都得不到以下这个结果
bunnyEars2(0) → 0
bunnyEars2(1) → 2
bunnyEars2(2) → 5
bunnyEars2(3) → 7
bunnyEars2(4) → 10
bunnyEars2(5) → 12
bunnyEars2(6) → 15
bunnyEars2(10) → 25

请教如何解recursion的题,谢谢!
k
kz80

recursion没那么复杂,就是function可以call on itself, 但设置了先决条件不会死
循环。
比如计算fibonacci sequence, O(logn), 你这个例子就是这种。

解这玩意儿就看recursion发生在哪里。

recursive function弄不好会很慢,为了避免重复计算,下一步优化是加上hashtable
记录和调用已知计算结果。

【 在 midpasse (事人) 的大作中提到: 】
: 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断
: 去碰试,看看能不能碰出来一个正确的算法。
: 比如这么简单一道
: We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3
: , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3
: ears, because they each have a raised foot. Recursively return the number of
: "ears" in the bunny line 1, 2, ... n (without loops or multiplication).
: 我的尝试:
: public int bunnyEars2(int bunnies) {
: if (bunnies==0){
: ...................
L
Liber8

tree遍历的概念 先搞清楚 然后就容易了
【 在 midpasse (事人) 的大作中提到: 】
: 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断
: 去碰试,看看能不能碰出来一个正确的算法。
: 比如这么简单一道
: We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3
: , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3
: ears, because they each have a raised foot. Recursively return the number of
: "ears" in the bunny line 1, 2, ... n (without loops or multiplication).
: 我的尝试:
: public int bunnyEars2(int bunnies) {
: if (bunnies==0){
: ...................

l
ludovic

就是想多了。别想,如果有了小一号的答案,怎么扩展成下一步答案。

recursion和DP在思考上是一回事,实现的时候解空间的构造和维护不同而已。其实都
十分简单,搞不清就是想多了。

【 在 midpasse (事人) 的大作中提到: 】
: 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断
: 去碰试,看看能不能碰出来一个正确的算法。
: 比如这么简单一道
: We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3
: , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3
: ears, because they each have a raised foot. Recursively return the number of
: "ears" in the bunny line 1, 2, ... n (without loops or multiplication).
: 我的尝试:
: public int bunnyEars2(int bunnies) {
: if (bunnies==0){
: ...................

m
magliner

比如写个函数,f(n)
if n = 1 return 2
else {
if n is even, return f(n-1) +3
else return f(n-1) +2 }

意思一下。 我老不写代码谋生。 不明白这东西明明没用, 为啥还琢磨它,有这时间
,学点别的不好么?
m
mjmjmjmjmjmj

这题要递归干啥?

if (n%2 == 0) {
return 5 * (n/2)
} else {
return 5 * (n/2) + 2
}

你要真想写递归,就是楼上那个写法
d
digua

这一行有bug:
return bunnies+bunnies%2+bunnyEars2(bunnies-1);
应改成:
return 2+bunnies%2+bunnyEars2(bunnies-1);

【 在 midpasse (事人) 的大作中提到: 】
: 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断
: 去碰试,看看能不能碰出来一个正确的算法。
: 比如这么简单一道
: We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3
: , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3
: ears, because they each have a raised foot. Recursively return the number of
: "ears" in the bunny line 1, 2, ... n (without loops or multiplication).
: 我的尝试:
: public int bunnyEars2(int bunnies) {
: if (bunnies==0){
: ...................

f
fhnan

Devide and conquer

【 在 midpasse (事人) 的大作中提到: 】
: 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断
: 去碰试,看看能不能碰出来一个正确的算法。
: 比如这么简单一道
: We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3
: , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3
: ears, because they each have a raised foot. Recursively return the number of
: "ears" in the bunny line 1, 2, ... n (without loops or multiplication).
: 我的尝试:
: public int bunnyEars2(int bunnies) {
: if (bunnies==0){
: ...................

n
nchip

(defn bunnies [num]
(loop [c 0 n num]
(cond
(zero? n) c
(odd? n) (recur (+ c 2) (dec n))
:else (recur (+ c 3) (dec n)))))

递归不需要动脑子
(time (bunnies 10))
"Elapsed time: 0.0359 msecs"
=> 25

【 在 mjmjmjmjmjmj (mjmjmjmjmjmj) 的大作中提到: 】
: 这题要递归干啥?
: if (n%2 == 0) {
: return 5 * (n/2)
: } else {
: return 5 * (n/2) + 2
: }
: 你要真想写递归,就是楼上那个写法

s
sanwadie

递归是简便方法,对程序栈有压力。考试时,有些题会说不许递归。
写递归注意几个点:
选择合适的递归入口
有解套代码,就是在这个点不是继续递归而是通过其他方式返回
递归深度不能太大
t
tfusion

俺们中国人不是从初中就学了数学归纳法?一回事