Come mentalmente tenere traccia della ricorsione

Question

Come mentalmente tenere traccia della ricorsione

#1 da (8 voti)
#2 da (2 voti)
#3 da (-1 voti)

3

Ho grossi problemi nel fare la ricorsione, specialmente cercando di visualizzarla. Un ottimo esempio è il problema del vino di invecchiamento descritto nella risposta principale di questo link: link . Nell'esempio, hai il compito di trovare la sequenza ottimale di vino da vendere dato i prezzi iniziali del vino e il fatto che i prezzi raddoppiano ogni anno.

int p[N]; // read-only array of wine prices
// year represents the current year (starts with 1)
// [be, en] represents the interval of the unsold wines on the shelf
int profit(int year, int be, int en) {
  // there are no more wines on the shelf
  if (be > en)
    return 0;
  // try to sell the leftmost or the rightmost wine, recursively calculate the 
  // answer and return the better one
  return max(
    profit(year+1, be+1, en) + year * p[be],
    profit(year+1, be, en-1) + year * p[en]);
}

In alto, ho difficoltà a visualizzare. Innanzitutto penso a cosa restituisce la funzione alla fine della ricorsione, che è uno 0, quindi provo a calcolare il valore restituito dalla penultima alla ricorsione. Posso farlo per diversi passaggi finché non mi perdo.

recursion

posta mrQWERTY 16.07.2016 - 03:07

fonte

3 risposte

2

Non farlo. Disegnalo invece.

Voglio dire, a meno che tu non stia riflettendo su una soluzione durante un arresto del traffico, o dovunque non hai accesso al materiale di scrittura, o stai tentando di sfoggiare il machismo intellettuale, non vedo alcun motivo per farlo difficile per te, soprattutto quando ci sono più di una manciata di ricorsi in gioco.

Inoltre, è più importante far rotolare la palla che risolvere il problema nella tua testa. Quindi una volta capito cosa sta succedendo, basta codificarlo ed eseguirlo. Puoi entrare nel debugger per vedere i valori esatti come una sorta di controllo incrociato con il tuo calcolo mentale.

risposta data 16.07.2016 - 10:24

fonte

-1

In realtà hai due modi per capire cosa fa la ricorsione. Stai cercando un modo per visualizzare la ricorsione. Il modo semplice è quello di rappresentare le chiamate ricorsive come albero. Ogni nodo dell'albero è una chiamata alla funzione ricorsiva. Le foglie dell'albero sono le chiamate alla funzione ricorsiva che non chiama la funzione ricorsiva. la radice dell'albero è la prima chiamata alla funzione ricorsiva. Ogni volta che la funzione ricorsiva si chiama, è necessario aggiungere un nodo figlio. Si noti che l'attraversamento dell'albero è un traversale più a sinistra (chiamato anche attraversamento pre-ordine). dimmi se vuoi ulteriori informazioni su questo tipo di visualizzazione.

risposta data 16.08.2016 - 10:36

fonte

Leggi altre domande sui tag recursion

Le iniezioni di dipendenza nelle entit sono considerate contro SRP? È un tentativo di creare una risorsa duplicata, ad es. un utente, degno di lanciare un'eccezione?

score 8 · Accepted Answer

Non cercare di scendere la pila nella tua testa. In questo modo giace la pazzia. Con la magia dell'induzione matematica, ogni invocazione ricorsiva sotto di te può essere considerata come debug e funziona già grazie al programmatore che è il futuro te. Tratta come una chiamata a una funzione di libreria a cui non hai il codice sorgente. Se ti aiuta a risolverlo, commentalo temporaneamente e sostituiscilo con i risultati per un caso di prova di dimensioni ragionevoli.

In altre parole, non è necessario essere in grado di seguire l'algoritmo completo. Tutto quello che devi sapere è come ridurre leggermente il problema in modo da poter chiamare un algoritmo che funziona già grazie a ricorsivi e scrivere un caso base banale. Non posso sottolineare abbastanza. Affidati che la chiamata ricorsiva funzioni già. Una volta fatto ciò, gli algoritmi ricorsivi diventano molto più facili.