java - 检查无限调用/递归调用算法

Question

这是我要解决的问题的一部分。假设我已经解析了一些代码，现在我正在尝试检查它在逻辑上是否正确。其中一项检查是函数调用不能调用自身或参与另一个函数相互调用或函数的函数相互调用，等等。

我已经解决了这个问题，并且能够轻松地解决对自身和下一级的调用，尽管它可能不是最佳代码。现在，性能不是问题。

这是我编写的逻辑以及示例:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LoopTest {

    public static void main(String[] args) {
        List<Loop> test = new ArrayList<Loop>();
        test.add(new Loop("Function1",new String[]{"Function2", "Function1"}));
        test.add(new Loop("Function2",new String[]{"Function3", "Function1"}));
        test.add(new Loop("Function3",new String[]{"Function1"}));
        checkLooping(test);
    }

    public static void checkLooping(List<Loop> input) {
        for(Loop main : input) {
            for(int i = 0; i < main.getInputSize(); i++) {
                if(main.getName().equals(main.getInputValue(i))) {
                    System.err.println("Looping condition found at " + main.getName());
                }
                for(Loop inside : input) {
                    for(int j = 0; j < inside.getInputSize(); j++) {
                        if(main.getInputValue(i).contains(inside.getName()) && 
                                main.getName().equals(inside.getInputValue(j))) {
                            System.err.println("Looping condition found between " 
                                    + main.getName() + " and " + inside.getName());
                        }
                    }
                }
            }
        }
    }
}

class Loop {
    private String name;
    private String input[];

    public Loop(String name, String input[]) {
        this.name = name;
        this.input = input;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String[] getInput() {
        return input;
    }
    public void setInput(String[] input) {
        this.input = input;
    }

    public int getInputSize() {
        return input.length;
    }

    public String getInputValue(int i) {
        return input[i];
    }

    public boolean contains(String search) {
        if(name.contains(search))
            return true;
        else
            return false;
    }

    @Override
    public String toString() {
        return String.format("%s %s", this.name, Arrays.toString(input));
    }
}

这不会发现 Function1 存在于 Function3 中。因此，如果它比 1 级更深，它不会根据我的逻辑捕获它。还有其他方法吗？

提前致谢!

Answer 1

Is there another way to do so?

是的，这是一个图遍历问题；特别是在(在这种情况下)方法调用图中检测循环引用的问题。

一个简单的算法是这样的:

def detect_cycle(node, seen={}):
    if seen contains node:
        // found a cycle
    seen.add(node)
    foreach child in node.children:
        detect_cycle(child, seen)

(您不需要明确的图形结构来执行此遍历。相同的方法可用于遍历/检查由另一个数据结构隐含的图形。)

然而，我们实际上在这里做的是检查递归调用。我们将无法区分终止递归(没问题)和无限递归(不好)。这是一个非常困难的问题。 (事实上​​ ，计算理论表明，证明终止问题的最一般形式无解。)

---

作为一个问题或兴趣 (:-) )，上面的图遍历算法是一个具有良好递归的程序示例。然而，编写一个程序来证明它会终止......并确定它不会终止的理论情况将是一项巨大的工作量!