Debug di un algoritmo ricorsivo

Question

La mia domanda è se ci sono alcuni modi intelligenti per eseguire il debug di complicati algoritmi ricorsivi. Supponiamo che ne abbiamo uno complicato (non un caso semplice quando il contatore di ricorsione è diminuito in ogni 'iterazione annidata').

Intendo qualcosa di simile a un attraversamento ricorsivo di un grafico quando i loop sono possibili.

Ho bisogno di controllare se non sto ottenendo il ciclo infinito da qualche parte. E farlo usando solo un debugger non dà una risposta certa (perché non sono sicuro che un algoritmo sia in loop infinito o proceda come dovrebbe).

È difficile spiegarlo senza un esempio concreto. Ma quello di cui ho bisogno è ...

'per verificare se i loop infiniti non avvengono in un algoritmo ricorsivo, per esempio'.

Answer 1

È necessario formare una teoria per il motivo per cui si ritiene che l'algoritmo termini. Idealmente, dimostra la teoria come un teorema matematico.

È possibile cercare una funzione dello stato del problema che si riduce su ogni chiamata ricorsiva. Ad esempio, vedere la seguente discussione della funzione di Ackermann, da Wikipedia

Può non essere immediatamente evidente che la valutazione di A (m, n) termina sempre. Tuttavia, la ricorsione è limitata perché in ogni applicazione ricorsiva m diminuisce o m rimane uguale e n diminuisce. Ogni volta che n raggiunge lo zero, m diminuisce, quindi m raggiunge anche lo zero.(Espressa più tecnicamente, in ogni caso la coppia (m, n) diminuisce nell'ordine lessicografico su coppie, che è un buon ordinamento, proprio come l'ordinamento di singoli numeri interi non negativi, questo significa che non si può scendere nell'ordine infinite volte in successione). Tuttavia, quando m diminuisce, non vi è limite superiore su quanto può aumentare n e spesso aumenterà notevolmente.

Questo è il tipo di ragionamento che dovresti pensare di applicare al tuo algoritmo.

Se non riesci a trovare un modo per dimostrare che il tuo algoritmo termina, considera la possibilità di cercare una variante di cui puoi provare la risoluzione. Non è sempre possibile decidere se un programma arbitrario termina o meno. Il trucco è scrivere algoritmi che puoi provare a risolvere.

Answer 2

se si desidera verificare la presenza di un circuito senza fine,

scrivere la System.out.println("no its not endless"); alla prossima linea di chiamare la funzione ricorsiva.

se il ciclo sarebbe infinita, questa affermazione non otterrete di stampa, se altrimenti si vedrà l'uscita

Answer 3

Un suggerimento è il seguente:

Se si dispone di loop infinito, allora nel caso del grafico si vuole ottenere un percorso con un numero di vertici maggiore del numero totale di vertici nel grafico. Supponendo che il numero di vertici nel grafico sia una variabile globale (che, penso, sia il caso più comune) è possibile eseguire un breakpoint condizionale all'inizio della ricorsione se la profondità è già superiore al numero totale di vertici.

Here is a link come si fanno i breakpoint condizionali per java in Eclipse.

Answer 4

È necessario conteggiare la profondità delle chiamate ricorsive ... e quindi generare un'eccezione se la profondità delle chiamate ricorsive raggiunge una determinata soglia.

Ad esempio:

void TheMethod(object[] otherParameters, int recursiveCallDepth) 
{ 
    if (recursiveCallDepth > 100) { 
     throw new Exception("...."); } 
    TheMethod(otherParameters, ++recursiveCallDepth); 
} 

Answer 5

migliore è dimostrando finitezza da condizioni, varianti e invarianti pre e post. Se è possibile specificare una formula (virtuale) il cui valore aumenta su ogni chiamata si ha una garanzia.

Questo equivale a provare i loop per essere finiti. Inoltre, potrebbe rendere più affrontabili algoritmi complessi.