Преобразование рекурсивной функции в нерекурсивную функцию

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. Когда заканчивается алгоритм?

Ans ответ должен быть

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

Этот код тестировался и может (читай: делает) содержат ошибки. Он может даже не компилироваться, но должен дать вам общую идею.