V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
punk2sang
V2EX  ›  Java

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

  •  
  •   punk2sang · 246 天前 · 1845 次点击
    这是一个创建于 246 天前的主题,其中的信息可能已经有所发展或是发生改变。
    假如说有代码如下:请问还能将递归改为循环吗
    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 条回复    2021-04-03 19:37:58 +08:00
    WuSiYu
        1
    WuSiYu  
       246 天前
    递归本质上就是通过函数的栈帧来保存信息,所以通过栈就可以转化任何的递归算法,最经典的比如二叉树的前序、中序、后序遍历都有非递归的写法
    dd112389
        2
    dd112389  
       246 天前
    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
        3
    dd112389  
       246 天前
    这是想算累加 ?
    那直接一个循环不就出来了 ?
    var n = 10;
    var sum = 0;
    for (let i = 0; i <= 10; i++) sum += i;
    thedrwu
        4
    thedrwu  
       246 天前 via Android
    自己维护个栈,再 goto 大法
    irytu
        5
    irytu  
       246 天前 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
        6
    GAsss  
       246 天前   ❤️ 1
    如何把任意递归转循环?——编译器编译后看生成的汇编 [狗头]
    abersheeran
        7
    abersheeran  
       246 天前
    如楼上所说,编译再反编译即可。哈哈哈哈哈哈
    atuocn
        8
    atuocn  
       246 天前
    看看 sicp, 关于递归和迭代的解释。主要的区别是,递归需要使用栈空间,而迭代不需要。大多时候递归算法容易解决,转成迭代算法则不太容易。
    Whurry
        9
    Whurry  
       246 天前
    666
    jiangzhizhou
        10
    jiangzhizhou  
       246 天前
    就不能缩进一下么
    ```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
        11
    jiangzhizhou  
       246 天前
    @jiangzhizhou 为啥不支持 MarkDown
    no1xsyzy
        12
    no1xsyzy  
       246 天前
    @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
        13
    no1xsyzy  
       246 天前
    @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
        14
    misaka19000  
       246 天前
    不都是 jmp 吗,有什么不能转的
    yeqizhang
        15
    yeqizhang  
       246 天前
    @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
        16
    irytu  
       245 天前 via iPhone
    @yeqizhang 哈哈哈 是的 这是之前 leetcode 的一道题的解法
    punk2sang
        17
    punk2sang  
    OP
       244 天前
    @GAsss @Whurry @WuSiYu @abersheeran @atuocn @dd112389 @irytu @jiangzhizhou @misaka19000 @no1xsyzy 感谢大家的回复,我后面想了下,这种是不是可以看作就是非递归版的多叉树后序遍历
    no1xsyzy
        18
    no1xsyzy  
       244 天前
    @punk2sang 好像确实可以看作对 AST 进行后根遍历
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2268 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 05:38 · PVG 13:38 · LAX 21:38 · JFK 00:38
    ♥ Do have faith in what you're doing.