根据一切递归可以转为循环，问个递归中嵌套循环的问题

[punk2sang]

假如说有代码如下：请问还能将递归改为循环吗
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;
}

[WuSiYu]

递归本质上就是通过函数的栈帧来保存信息，所以通过栈就可以转化任何的递归算法，最经典的比如二叉树的前序、中序、后序遍历都有非递归的写法

[dd112389]

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;
}

[dd112389]

这是想算累加 ？
那直接一个循环不就出来了 ？
var n = 10;
var sum = 0;
for (let i = 0; i <= 10; i++) sum += i;

[thedrwu]

自己维护个栈，再 goto 大法

[irytu]

说到这个有点意思的，想问个一样的问题：



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);
}


这个递归怎么变循环？

[GAsss]

如何把任意递归转循环？——编译器编译后看生成的汇编 [狗头]

[abersheeran]

如楼上所说，编译再反编译即可。哈哈哈哈哈哈

[atuocn]

看看 sicp, 关于递归和迭代的解释。主要的区别是，递归需要使用栈空间，而迭代不需要。大多时候递归算法容易解决，转成迭代算法则不太容易。

[Whurry]

666

[jiangzhizhou]

就不能缩进一下么
```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;
}
```

[jiangzhizhou]

@jiangzhizhou 为啥不支持 MarkDown

[no1xsyzy]

@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 但如何保证这个不变式正确似乎比较诡异。

[no1xsyzy]

@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)

这种简单递归根本不用我说了吧

[misaka19000]

不都是 jmp 吗，有什么不能转的

[yeqizhang]

@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);
}
}
}

不过这代码看起来头疼，结合业务逻辑的目的来看可能还好...

[irytu]

@yeqizhang 哈哈哈 是的 这是之前 leetcode 的一道题的解法

[punk2sang]

@GAsss @Whurry @WuSiYu @abersheeran @atuocn @dd112389 @irytu @jiangzhizhou @misaka19000 @no1xsyzy 感谢大家的回复，我后面想了下，这种是不是可以看作就是非递归版的多叉树后序遍历

[no1xsyzy]

@punk2sang 好像确实可以看作对 AST 进行后根遍历