将递归函数转换为非递归函数

Question

是否可以将函数go转换为非递归函数？一些提示或启动草图将是非常有益

public static TSPSolution solve(CostMatrix _cm, TSPPoint start, TSPPoint[] points, long seed) { 
    TSPSolution sol = TSPSolution.randomSolution(start, points, seed, _cm); 
    double t = initialTemperature(sol, 1000); 
    int frozen = 0; 
    System.out.println("-- Simulated annealing started with initial temperature " + t + " --"); 
    return go(_cm, sol, t, frozen); 
} 

private static TSPSolution go(CostMatrix _cm, TSPSolution solution, double t, int frozen) { 
    if (frozen >= 3) { 
     return solution; 
    } 
    i++; 

    TSPSolution bestSol = solution; 
    System.out.println(i + ": " + solution.fitness() + " " + solution.time() + " " 
      + solution.penalty() + " " + t); 
    ArrayList<TSPSolution> nHood = solution.nHood(); 

    int attempts = 0; 
    int accepted = 0; 

    while (!(attempts == 2 * nHood.size() || accepted == nHood.size()) && attempts < 500) { 
     TSPSolution sol = nHood.get(rand.nextInt(nHood.size())); 
     attempts++; 

     double deltaF = sol.fitness() - bestSol.fitness(); 
     if (deltaF < 0 || Math.exp(-deltaF/t) > Math.random()) { 
      accepted++; 
      bestSol = sol; 
      nHood = sol.nHood(); 
     } 
    } 

    frozen = accepted == 0 ? frozen + 1 : 0; 

    double newT = coolingSchedule(t); 

    return go(_cm, bestSol, newT, frozen); 

} 

Answer 1

这是容易的，因为它是尾递归：还有就是递归调用&什么函数返回之间没有任何代码。因此，一旦循环结束，您可以将go的主体包装在循环while (frozen<3)和return solution中。并将递归调用替换为参数：solution=bestSol; t=newT;。

Answer 2

你需要thinkg两件事：

1. 每一步哪些变化？
2. 算法什么时候结束？

答答案应该是

1. bestSol（solution），newT（t），frozen（frozen）
2. 当frozen >= 3是真的

所以，最简单的方法是只是为了将整个功能放在类似

while (frozen < 3) { 
    ... 
    ... 
    ... 

    frozen = accepted == 0 ? frozen + 1 : 0; 
    //double newT = coolingSchedule(t); 
    t = coolingSchedule(t); 
    solution = bestSol; 
} 

Answer 3

作为一个经验法则，使递归函数迭代的最简单方法是将第一个元素加载到堆栈上，而不是调用递归，将结果添加到堆栈。

例如：

public Item recursive(Item myItem) 
{ 
    if(myItem.GetExitCondition().IsMet() 
    { 
     return myItem; 
    } 
    ... do stuff ... 
    return recursive(myItem); 
} 

将成为：

public Item iterative(Item myItem) 
{ 
    Stack<Item> workStack = new Stack<>(); 
    while (!workStack.isEmpty()) 
    { 
     Item workItem = workStack.pop() 
     if(myItem.GetExitCondition().IsMet() 
     { 
      return workItem; 
     } 
     ... do stuff ... 
     workStack.put(workItem) 
    } 
    // No solution was found (!). 
    return myItem; 
} 

此代码是未经测试，可能（阅读：做）包含错误。它甚至可能不会编译，但应该给你一个大概的想法。