Hierholer算法的递归实现

Question

完成了老师留思考题-Hierholer算法的递归实现，请老师批阅一下～

另外在实现递归算法的时候，悟出了一个道理，不知道对不对，就是：方法调用也是通过调用栈来完成的，栈定元素就是当前在执行的方法，那么其实从某种意义上，也可以说方法的参数是栈顶元素，这样从参数的出栈入栈的角度看的话，其实和非递归实现中使用的栈中元素出栈入栈的过程是完全相同的

package graph;

import dfs.CC;

import java.util.ArrayList;

/**
 * @author gaowenfeng02
 * @desc
 * @date 2019/9/22
 */
public class EulerLoopRecur {

    private Graph G;
    private ArrayList<Integer> result;

    public EulerLoopRecur(Graph G) {
        this.G  = (Graph) G.clone();

        result = new ArrayList<>();
        if(!hasResult()){
            return;
        }

        dfs(0);
    }

    public boolean hasResult(){

        CC cc = new CC(this.G);
        if(cc.count() / 2 == 1){
            return false;
        }
        for (int v = 0; v < this.G.V(); v++) {
            if(G.degree(v) % 2 == 1){
                return false;
            }
        }
        return true;
    }

    /**
     * 从 v 出发，寻找欧拉回路
     * 若 v 没有其他边了，则将v加入result里
     * 否则 只要从 v 出发还有边，就选择其中一条边，将其删除，并递归该边的另一个定点
     *     若 v 没有边了，说明已经从 v 出发遍历了所有的环，则将 v 加入result
     *
     * @param v
     */
    private void dfs(int v){
        if(G.degree(v) == 0){
            result.add(v);
        }else{
            while (G.degree(v) != 0){
                int w = G.adj(v).iterator().next();
                G.remove(v,w);
                dfs(w);
            }
            result.add(v);
        }
    }

    public Iterable<Integer> result(){
        return result;
    }
}

Answer 1

liuyubobobo 2019-09-22 19:00:58

大赞！感谢分享！

你对递归转非递归的理解也非常到位。实际上，在系统中，递归的实现，就是把上层调用的相关参数压入栈，然后开始执行新的调用：）

继续加油！：）

• 提问者 Meet_相识 #1

  嗯嗯，那么所有算法，如果不考虑成本和实现的复杂性可读性的话，都可以在递归和非递归上相互转化吗？

• liuyubobobo 回复 提问者 Meet_相识 #2

  很少有人需要把非递归转成递归。但递归一定能转成非递归：）