java在递归中保留变量实例
我正试着做一个程序来找出图中所有的欧拉路径。为了做到这一点,我使用了一个改编自以下内容的代码:http://www.sanfoundry.com/java-program-implement-euler-circuit-problem/
我所做的:我修改了一个递归函数printEulerUtil()(如下),用于测试和查找(方法isValidNextEdge)可能的Euler路径。但是,我的递归方法没有存储变量int[][]localAdjacencyMatrix(它就像一个全局变量,我无法理解),这意味着当递归返回时(例如,在深度优先搜索中找到第一个Euler路径之后),我的变量与上一个递归调用相同(如我所说,是一个全局变量行为),没有在程序中存储之前“原始”调用的值(第一个递归调用之前的上下文)
我做错了什么?毕竟,当递归发生时,不会保存所有上下文
下面是一段代码(注释):
// in the main call, variable vertex and localAdjacencyMatrix are defined in the constructor.
public void printEulerTourUtil(int vertex, int[][] localAdjacencyMatrix) {
ArrayList<Integer> destinationVertexes = new ArrayList<>();
int destination = 1;
// print the actual vertex
System.out.println("V: " + vertex);
for (destination = 1; destination <= numberOfNodes; destination++) {
// test all possibles destinations
if (localAdjacencyMatrix[vertex][destination] == 1 && isValidNextEdge(vertex, destination, localAdjacencyMatrix)) {
// insert these destinations in a list of next vertex for recursion
destinationVertexes.add(destination);
System.out.println(destination + " ");
}
}
// make a recursion for every vertex destination in the list.
for (int i = 0; i < destinationVertexes.size(); i++){
destination = destinationVertexes.get(i);
// go to the next vertex in the graph
System.out.println("-> source : " + vertex + " destination " + destination);
// localAdjacencyMatrix isn't working. it's like a global variable, so my recursion fails
removeEdge(vertex, destination, localAdjacencyMatrix);
printEulerTourUtil(destination, localAdjacencyMatrix);
}
对不起,任何英语错误和任何帮助将是非常有用的!谢谢大家!
# 1 楼答案
localAdjacencyMatrix
数组根本不是本地的。它从外部传递到对printEulerTourUtil
的第一个调用,然后传递到每个递归调用。因此,每个递归调用都会看到并修改此数组的同一实例另一方面,
destinationVertexes
变量是局部变量。它是在printEulerTourUtil
方法的范围内定义的,因此该方法的每次递归执行都会实例化该列表的一个新实例我不确定您需要什么,但是如果您的逻辑要求
localAdjacencyMatrix
是本地的,那么您应该在printEulerTourUtil
方法中声明并实例化它# 2 楼答案
由于数组
localAdjacencyMatrix
在Java中是通过引用传递的,如果不想修改原始数组,则需要首先在方法顶部克隆它。但是,请注意,Java clone()方法本身无法在多维数组上工作。见how to clone multidimensional arrays# 3 楼答案
数组作为引用类型(与作为基元的int不同)。因此,每次通过递归将数组传递给方法时,都只是传递对同一数组对象的引用。基本上,您不需要传递引用,因为所有方法调用都获得对数组字段的引用
如果每次调用都需要一个新的数组实例,则需要创建一个新数组以传入