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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1339 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

int

递归

add

套循环

18 条回复 • 2021-04-03 19:37:58 +08:00

WuSiYu

2021-04-02 01:24:06 +08:00

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

dd112389

2021-04-02 01:39:44 +08:00

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

2021-04-02 01:48:22 +08:00

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

thedrwu

2021-04-02 01:57:28 +08:00 via Android

自己维护个栈，再 goto 大法

irytu

2021-04-02 02:03:37 +08:00 via iPhone

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

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

2021-04-02 09:00:23 +08:00

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

abersheeran

2021-04-02 09:19:37 +08:00

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

atuocn

2021-04-02 09:22:52 +08:00

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

Whurry

2021-04-02 09:23:20 +08:00

666

jiangzhizhou

2021-04-02 09:31:16 +08:00

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

2021-04-02 09:31:34 +08:00

@jiangzhizhou 为啥不支持 MarkDown

no1xsyzy

2021-04-02 10:34:21 +08:00

@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

2021-04-02 10:45:04 +08:00

@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

2021-04-02 10:47:14 +08:00

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

yeqizhang

2021-04-02 11:04:38 +08:00

@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

2021-04-02 17:16:35 +08:00 via iPhone

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

punk2sang

2021-04-03 16:01:04 +08:00

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

no1xsyzy

2021-04-03 19:37:58 +08:00

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