將遞歸函數轉換爲非遞歸函數

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

此代碼是未經測試，可能（閱讀：做）包含錯誤。它甚至可能不會編譯，但應該給你一個大概的想法。