 |
WuSiYuApr 2, 2021
1
递归本质上就是通过函数的栈帧来保存信息，所以通过栈就可以转化任何的递归算法，最经典的比如二叉树的前序、中序、后序遍历都有非递归的写法
|
 |
dd112389Apr 2, 2021
2
public int add(int n) {
int k = n; for (int i = 0; i< 3; i++) { if (n != 1) { k += add(n - 1); System.out.println(k); } else { k+=0; System.out.println(k); } } return k; } |
|
dd112389Apr 2, 2021
3
这是想算累加 ？
那直接一个循环不就出来了 ？ var n = 10; var sum = 0; for (let i = 0; i <= 10; i++) sum += i; |
 |
thedrwuApr 2, 2021 via Android
4
自己维护个栈，再 goto 大法
|
 |
irytuApr 2, 2021 via iPhone
5
说到这个有点意思的，想问个一样的问题：
bool reachingPoints(int sx, int sy, int tx, int ty) { if (sx == tx && sy == ty) return true; int sx1 = sx + sy; int sy1 = sy; int sx2 = sx; int sy2 = sx + sy; if ((sx1 > tx || sy1 > ty) && (sx2 > tx || sy2 > ty)) { return false; } return reachingPoints(sx1, sy1, tx, ty) || reachingPoints(sx2, sy2, tx, ty); } 这个递归怎么变循环？ |
 |
6
如何把任意递归转循环？——编译器编译后看生成的汇编 [狗头]
|
 |
abersheeranApr 2, 2021
7
如楼上所说，编译再反编译即可。哈哈哈哈哈哈
|
 |
atuocnApr 2, 2021
8
看看 sicp, 关于递归和迭代的解释。主要的区别是，递归需要使用栈空间，而迭代不需要。大多时候递归算法容易解决，转成迭代算法则不太容易。
|
 |
WhurryApr 2, 2021
9
666
|
 |
jiangzhizhouApr 2, 2021
10
就不能缩进一下么
```Java public int add(int n) { int k = n; for (int i = 0; i< 3; i++) { if (n != 1) { k += add(n - 1); System.out.println(k); } else { k += 0; System.out.println(k); } } return k; } ``` |
|
jiangzhizhouApr 2, 2021
11
@jiangzhizhou 为啥不支持 MarkDown
|
 |
no1xsyzyApr 2, 2021
12
@dd112389 显然不是…… 排除副作用的话
add :: Int -> Int add 1 = 1 add n = n + 3 * add n 这是一个指数增长的函数。 @punk2sang 如果你要保留所有副作用的话就必须自己维护栈帧了。 不保留副作用的话一方面看下 DP，其实只需要保留 last k last = nil loop(nn in 1...n){ k=n loop(i in 0..3){ if(nn != 1){ k += last println(k) } else { k+=0 print(k) } last = k } 虽然上述似乎无法正确地被形式化证明。 虽然在 nn != 1 前可以添加不变式 nn != 1 => last != nil 但如何保证这个不变式正确似乎比较诡异。 |
|
no1xsyzyApr 2, 2021
13
@no1xsyzy 哦……
我不应该加上 print 的 现在这个样子副作用的次数都不对。 要副作用完全一致还是需要自己维护栈帧。 —— 当然还有一种曲线方式 你可以发现这个副作用也是分治的。 所以其实可以把副作用构成传参 add :: (Int, [Char]) -> (Int, [Char]) add (1, s) = (1, "1\n1\n1") add (n, s) = (n + 3 * add n, concat $ replicate 3 $ s ++ show k) 这种简单递归根本不用我说了吧 |
 |
misaka19000Apr 2, 2021
14
不都是 jmp 吗，有什么不能转的
|
 |
yungo8Apr 2, 2021
15
@irytu 按照前面的人说的编译后反编译，我试了 java 确实反编译出来还是递归。
public static boolean reachingPoints(int sx, int sy, int tx, int ty) { if (sx == tx && sy == ty) { return true; } else { int sx1 = sx + sy; int sy2 = sx + sy; if ((sx1 > tx || sy > ty) && (sx > tx || sy2 > ty)) { return false; } else { return reachingPoints(sx1, sy, tx, ty) || reachingPoints(sx, sy2, tx, ty); } } } 不过这代码看起来头疼，结合业务逻辑的目的来看可能还好... |
 |
17
@GAsss @Whurry @WuSiYu @abersheeran @atuocn @dd112389 @irytu @jiangzhizhou @misaka19000 @no1xsyzy 感谢大家的回复，我后面想了下，这种是不是可以看作就是非递归版的多叉树后序遍历
|
1
Select Language