检查无限呼叫/重新调用呼叫算法

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));
    }
}

这不会捕获Function3中存在的Function1.因此,如果它比第1级更深,它将无法根据我的逻辑捕获它.还有另一种方法吗？

提前致谢!

Answer 1

还有另一种方法吗？

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

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

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

(您不需要显式图结构来执行此遍历.可以使用相同的方法遍历/检查另一个数据结构隐含的图.)

但是,我们在这里实际做的是检查递归调用.我们将无法区分终止(可以)和无限递归(这是坏的)的递归.这是一个非常棘手的问题.(事实上​​,计算理论认为证明终止问题的最一般形式没有解决方案.)

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