Esistono altri modi per limitare la profondità di ricorsione per una funzione?

4

Sto cercando di impedire a una funzione / metodo (in Java) di eseguire la ricorsione più di una profondità di 3 chiamate. Ho imparato a conoscere il trucco dell'accumulatore dal corso della scala coursera di odersky.

public void myMethod(File arg, int accumulator) {
    //...snipped...
    File newArg= ...;
    if (accumulator + 1 > 3)
        throw new IllegalStateException("exceeeding depth 3");
    myMethod(newArg, accumulator+1);
}

Qualche altra idea? Forse con un ThreadLocal?

    
posta socgen hacker 26.11.2014 - 22:57
fonte

2 risposte

6

Sì, c'è un altro modo per limitare la profondità della ricorsione, ma non lo incoraggerei .

In generale, possiamo dire che stai attualmente utilizzando un approccio basato sui dati.

public void myMethod(File arg, int accumulator) {

dove accumulator conta la profondità della chiamata di ricorsione.

L'altro modo è enumerare le chiamate. Detto in altro modo, codifica le chiamate:

private void myMethodSnippedCode(/*args*/) {
    //...snipped...
}

public void myMethod(File arg) {
    myMethodSnippedCode(/*whatever*/);
    // File newArg= ...; // ... code is moved to the myMethod1 call below
    // Exception removed. Why would you throw an exception?
    myMethod1(...); // the ... is where your new File is created
}

private void myMethod1(File arg) {
    myMethodSnippedCode(/*whatever*/);
    myMethod2(...);
}

private void myMethod2(File arg) {
    myMethodSnippedCode(/*whatever*/);
    myMethod3(...);
}

private void myMethod3(File arg) {
    myMethodSnippedCode(/*whatever*/);
    // don't make any more calls
}

Che comprensione del codice e incubo di manutenzione . Se dobbiamo cambiare il numero di livelli richiesti o introdurre altre modifiche, qualcuno inevitabilmente si sbaglia.

Attacca con una bella ricorsione pulita che tutti capiranno:

public void myMethod(File arg, int depth) {
    // [snipped code body]
    if (depth< 3)
        myMethod(..., ++depth); // the ... is where your new File is created
}

BTW, la chiamata iniziale a myMethod richiede che il chiamante passi zero. Cosa succederà se superano 6? O -21? La soluzione a questo è di avvolgere la prima chiamata

public void myMethod(File arg) {
        myMethodWorker(arg, 0);
}

private void myMethodWorker(File arg, int depth) {
    // [snipped code body]
    if (depth < 3)
        myMethodWorker(..., ++depth); // the ... is where your new File is created
}
    
risposta data 27.11.2014 - 00:31
fonte
1

ci sono vari modi:

  1. riscrivi la ricorsione in una versione iterativa e non devi preoccuparti della profondità della ricorsione solo la profondità dello stack se la versione iterativa ne richiede uno.

  2. Usa una variabile esterna di qualche tipo (variabile statica, membro del campo, ...) per tracciare la profondità della ricorsione. Questo ha il rovescio della medaglia che occupa alcuni byte solo per questo metodo e potrebbe non essere thread-safe / reentrant a seconda del tipo scelto.

Tuttavia il metodo dell'accumulatore di solito è preferibile quando la versione iterativa risulterebbe illeggibile.

    
risposta data 27.11.2014 - 00:35
fonte

Leggi altre domande sui tag