-
da3m0ns
.User deleted
Buona sera,
sto seguendo il libro di Marijn Haverbeke , eloquent javascript ed ho incominciato ad avere i primi dubbi sulle funzioni ricorsive in particolare in questo codice, nel quale il programma deve calcolare un numero passato alla funzione come sequenza di moltiplicazione e addizione:CODICEfunction findSolution(target) {
function find(start, history) {
if (start == target)
return history;
else if (start > target)
return null;
else
return find(start + 5, "(" + history + " + 5)") ||
find(start * 3, "(" + history + " * 3)");
}
return find(1, "1");
}
console.log(findSolution(24));
// → (((1 * 3) + 5) * 3)
Non riesco a capire che percorso fa la struttura dati una volta passato il 24 ed entrati nella findSolution.
Ho provato a sorvolare il problema, cercando di imparare la sruttura ad albero, dato che è la più frequente funzione ricorsiva in design.SPOILER (clicca per visualizzare)CODICEvar rootNode = {
nodeName: 'root',
children: [
{
nodeName: 'child 1',
children: [
{
nodeName: 'test',
children: []
}
]
} ,
{
nodeName: 'child 2',
children: []
},
{
nodeName: 'child 3',
children: [
{
nodeName: 'test',
children: []
},
{
nodeName: 'child 3-2',
children: []
}
]
}
]
}
function findNode(node, text) {
console.log(node.nodeName);
if (node.nodeName == text)
return node;
for (var childIndex in node.children) {
var result = findNode(node.children[childIndex], text);
if (result)
return result;
}
return null;
};
Ma penso che mi manchino ancora le conoscenze per comprenderlo a fondo.
Edited by da3m0ns - 2/3/2016, 22:57. -
.
Ho provato a fare uno schema con one note, a penna, per quanto riguarda la prima parte. Vedi se ti diventa più chiaro: SPOILER (clicca per visualizzare)
Poiché entrambe le opzioni I ed M ritornanonull, anche G avrà valorenull. Verrà quindi eseguito H che effettuerà X controlli che ti puoi solo aspettare secondo la struttura e i controlli illustrati nell'immagine.
Il risultato sarà, come illustrato, questo qui:CODICEconsole.log(findSolution(24)); // (((1 * 3) + 5) * 3)
Adesso passo all'altro PC e ti rispondo per quanto riguarda la seconda parte.
Per il secondo dubbio, intanto probabilmente quella struttura ad oggetti ti darà errore perché hai dimenticato di chiudere un apice alla seguente posizione:
4° children, primo nodeName, dopo 'test. Se vogliamo esprimerlo in Javascript:rootNode.children[2].children[0].nodeName;
Correggi anche nel tuo messaggio.
Per quanto riguarda il codice, cosa non capisci di preciso?. -
da3m0ns .
User deleted
Il flusso dati inizia dalla chiamata di funzione dove passa il 24, poi saltiamo la funzione find e arriviamo alla return find(1, "1"); da quì incominciano i duppi perché ho una return che dovrebbe terminare la funzione e restituire il contenuto della funzione.
Il flusso poi si sposta all' else e se non erro l'operatore || in JS legge il numero a sinistra se risulta true, altrimenti devo considerare quello a destra?. -
+1 .
Il return, in questo caso, effettua l'esecuzione di una funzione in un caso oppure della stessa con parametri differenti.
Affinché l'OR scelga una delle due opzioni, deve esserci almeno una delle due condizioni vere (true). Di conseguenza esegue la prima FINO alla G (dello schema), che è la prima che da un valore False.
Se al primo posto è presente un valore comenull, 0, false stesso o "" (stringa vuota), è come se facessifalse || find( ... , ... );. Tutto chiaro fin qui?
Tutti i controlli, tranne dalla G in poi, ti dovrebbero portare all'else perché non è rispettata la condizione di uguaglianza (che stampahistory). Di conseguenza avrai uno schema a blocchi che risale non appena arriva alla G e che quindi trascina il tuo valorenullfino alla A. Dalla A verrà quindi eseguito il B. Notiamo questo:startin B non è stato modificato, quindi riparte da 1 e continua a fare il giro.
La discussione è stata continuata in privato, dove è stato spiegato il funzionamento del codice:SPOILER (clicca per visualizzare)da3m0ns: Risposto, vado un passo alla volta se non non capisco, poi vediamo anche l'albero che è quello peggio. Comunque come prima funzione ricorsiva mi sembra un po esagerata, ci sono anche pochi esercizi per testare sul libro 😔
eXander: Sono funzioni semplici, dimostrative
da3m0ns: A lavoro mi han detto il contrario 😂 Ma nella seconda parte dell'espressione quello è un concatenamento di una stringa?
eXander: Quelle del libro sono dimostrative, poi ci sono altre applicazioni ma a livello di performance, sono migliori le iterazioni. Quale intendi con "espressione"?
da3m0ns: "(" + history + ! è 5)" e anche quella sotto
eXander: Il + fuori dalle virgolette è la concatenazione, si
da3m0ns: Non capisco come hai determinato che quella a sx è vera
eXander: dove?
da3m0ns: Ah no è falsa, ma non capisco come hai fatto, la A
eXander: Semplicemente il percorso che viene fatto è questo:
A -> C -> E -> G -> I
Solo che I restituisce null, quindi viene eseguita M.
Poiché anche M da null, implicitamente anche G avrà null. Ma siccome G è null, per E avremo la seguente logica:
null || H.
Viene quindi eseguita H fino a tornare alla A in pratica con un valore null e siccome A sarà null, verrà eseguita B e si ricomincia finché non si riesce a trovare un punto in cui viene ritornata history.
da3m0ns: Ma perché 6 == 24 ? x
eXander: 1+5 che è start nuovo in pratica, cioè, start + 5
da3m0ns: Cioè, è un calcolo tuo per vedere se è false?
eXander: no, non è un calcolo mio, è un'istruzione che viene comunque eseguita. X è per dire FALSO.
da3m0ns: Ah, quindi non viene calcolato se è false, passa i parametri? 🙈
eXander: Lui comunque fa tutto fino al passaggio G e poi torna indietro passando il Null come risultato
da3m0ns: Okay, ho capito il flusso, credo, fino al null || null poi che succede?
eXander: Arriverai al punto in cui avrai A = null e quindi verrà eseguito B. In pratica se vedi il risultato, lui fa B:
1 * 3
3 + 5
8 * 3
24
E hai ottenuto il tuo "path". In pratica in B fa lo stesso percorso di A finché non arriva a trovare una soluzione null che lo porta all'altra. Comunque in qualche modo lo trova.
da3m0ns: Ma B non risulta anche lui null? Non abbiamo ottenuto nulla e ritorna a a find(1, "1")
eXander: Non risulta null, altrimenti non restituirebbe history la tua funzione ma null. Non è vero che non ottieni nulla: ottieni una stringa con "history".
da3m0ns: Allora un attimo mi son calcolato questo find(start + 5, "(" + history + " + 5)") ed esce null giusto?
eXander: Alla fine del percorso si ma non è detto che esca null con tutti i casi. Dovresti analizzare passo per passo tutto il path, però è un lavoro immane e decisamente da non fare per affrontare correttamente la ricorsione.
da3m0ns: Okay, dici che se ho capito il percorso posso sorvolare?
eXander: Se hai capito COME FUNZIONA la ricorsione, si, più che altro perché seguire ogni step oltre che una perdita di tempo si trasforma in una cosa inutile e dispendiosa anche per la testa
da3m0ns: Beh in pratica funzione che chiama funzione all'interno, fine
eXander: Si praticamente si. Poi dipende dalle condizioni che decidi.
Edited by eXander - 2/3/2016, 22:47.
|
Contacts