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

punk2sang 20天前 9

假如说有代码如下:请问还能将递归改为循环吗
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;
}
最新回复 (18)
  • WuSiYu 15天前
    引用 2
    递归本质上就是通过函数的栈帧来保存信息,所以通过栈就可以转化任何的递归算法,最经典的比如二叉树的前序、中序、后序遍历都有非递归的写法
  • dd112389 15天前
    引用 3
    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 15天前
    引用 4
    这是想算累加 ?
    那直接一个循环不就出来了 ?
    var n = 10;
    var sum = 0;
    for (let i = 0; i <= 10; i++) sum += i;
  • thedrwu 15天前
    引用 5
    自己维护个栈,再 goto 大法
  • irytu 15天前
    引用 6
    说到这个有点意思的,想问个一样的问题:



    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 15天前
    引用 7
    如何把任意递归转循环?——编译器编译后看生成的汇编 [狗头]
  • abersheeran 15天前
    引用 8
    如楼上所说,编译再反编译即可。哈哈哈哈哈哈
  • atuocn 15天前
    引用 9
    看看 sicp, 关于递归和迭代的解释。主要的区别是,递归需要使用栈空间,而迭代不需要。大多时候递归算法容易解决,转成迭代算法则不太容易。
  • Whurry 15天前
    引用 10
    666
  • jiangzhizhou 15天前
    引用 11
    就不能缩进一下么
    ```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 15天前
    引用 12
    @jiangzhizhou 为啥不支持 MarkDown
  • no1xsyzy 15天前
    引用 13
    @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 15天前
    引用 14
    @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 15天前
    引用 15
    不都是 jmp 吗,有什么不能转的
  • yeqizhang 15天前
    引用 16
    @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 15天前
    引用 17
    @yeqizhang 哈哈哈 是的 这是之前 leetcode 的一道题的解法
  • 楼主 punk2sang 15天前
    引用 18
    @GAsss @Whurry @WuSiYu @abersheeran @atuocn @dd112389 @irytu @jiangzhizhou @misaka19000 @no1xsyzy 感谢大家的回复,我后面想了下,这种是不是可以看作就是非递归版的多叉树后序遍历
  • no1xsyzy 15天前
    引用 19
    @punk2sang 好像确实可以看作对 AST 进行后根遍历
  • 游客
    20
返回