Come convertire questo problema ricorsivo in iterativo? L'algoritmo Line Simplification non riesce a funzionare a causa della massima profondità di ricorsione che viene colpita

Convertire un algoritmo ricorsivo per essere iterativo di solito implica fare la stessa cosa che il compilatore o l'interprete fa da sé dietro le quinte, cioè davanti alle scene. Ciò significa che devi programmare uno stack di chiamate e tenere traccia dei valori delle variabili nelle chiamate ricorsive, in modo che vivano in una struttura di dati definita dall'utente piuttosto che nello stack di chiamate fornito dal sistema. È uno sforzo maggiore e in genere meno leggibile rispetto all'utilizzo della ricorsione corretta, ma può consentire di aggirare le limitazioni del sistema: anziché colpire il limite di ricorsione integrato, si raggiunge solo il limite predefinito della dimensione dei dati allocati dinamicamente.

Naturalmente, spesso è anche possibile risolvere lo stesso problema in modo completamente diverso, a volte anche meglio. Ma poi non è tanto convertire la ricorsione come che lo sostituisce con qualcosa di completamente diverso. Dipende dal problema se ciò sia possibile o meno.

Vorrei simulare nel modo più generico come segue: Questo è ciò che credo che farebbe la macchina di basso livello.

func(Param x) {

  Stack stack = new Stack();
  Frame frame = new Frame(x);
  push(frame);

  while (!stack.empty()) {
    frame = stack.pop();

    if (baseCase) {
       createResult(frame);
    } else {
       newFrame = doWork(frame);
       stack.push(frame);
       stack.push(newFrame);
    }
  }

  return frame.getResult();
}

Puoi definire Frame come segue:

class Frame {
   FrameData state;
   Data sharedData;
   Param inputParam;

   Result getResult() {
     ..compute result from 'state' and 'sharedData'
   }
}

Ora ti puoi chiedere perché c'è una sola spinta nello stack anche se hai 2 chiamate ricorsive. È perché la prima chiamata ricorsiva viene spinta nello stack con un frame con% diverso di% co_de e% di co_de rispetto al frame inserito nello stack dalla seconda chiamata.

Dato che hai detto, vuoi solo approccio e suggerimento. Spero che questo sia abbastanza I dettagli sono fatti nel metodo state . Ci sono variabili di istanze di sharedData modificate.

Mi ci è voluto un po 'per arrivare a questo. Spero che non ci sia nulla di sbagliato qui.

Vorrei usare uno stack, ma semplicemente mantenerlo il più semplice possibile. Dopotutto, tutto quello che devi sapere che cosa fare dopo è una coppia di numeri.

def line_simple(array, epsilon):
    keep = [False for i in array]
    keep[0], keep[-1] = True, True
    stack = deque()
    stack.append((0, len(array) -1))

    while len(stack) != 0:
        left, right = stack.pop();
        worst_distance, worst_index = find_worst(array, left, right)

        if worst_distance > epsilon:
            keep[worst_index] = True
            stack.append((left, worst_index))
            stack.append((worst_index, right))

    return keep

Tutto quello che devi fare è scrivere find_worst. Nota che find_worst dovrebbe prendere gli argomenti come ho mostrato; non dovresti fare find_worst(array[left:right]) che fa una copia dell'array. Assicurati che find_worst restituisca 0 se right-left = 0 o 1.