Quello che in parole povere è una funzione ricorsiva che usa PHP

Qualcuno può spiegarmi una funzione ricorsiva in PHP (senza usare Fibonacci) in un linguaggio comune e usando degli esempi? stavo guardando un esempio ma il Fibonacci mi ha totalmente perso!

Grazie in anticipo 😉 Inoltre, quanto spesso li usi nello sviluppo web?

Termini termini:

Una funzione ricorsiva è una funzione che chiama se stessa

Un po ‘più in profondità:

Se la funzione continua a chiamarsi, come fa a sapere quando fermarsi? Si imposta una condizione, nota come caso base. I casi base dicono alla nostra chiamata ricorsiva quando fermarsi, altrimenti passerà all’infinito.

Quello che è stato un buon esempio di apprendimento per me, dal momento che ho un forte background in matematica, è stato fattoriale . Con i commenti qui sotto, sembra che la funzione fattoriale possa essere un po ‘eccessiva, la lascerò qui nel caso lo volessi.

function fact($n) { if ($n === 0) { // our base case return 1; } else { return $n * fact($n-1); // <--calling itself. } } 

Per quanto riguarda l'utilizzo di funzioni ricorsive nello sviluppo web, non ricorro personalmente all'utilizzo di chiamate ricorsive. Non che io consideri la ctriggers pratica fare affidamento sulla ricorsione, ma non dovrebbero essere la tua prima opzione. Possono essere mortali se non utilizzati correttamente.

Anche se non posso competere con l'esempio di directory, spero che questo aiuti in qualche modo.

(4/20/10) Aggiornamento:

Sarebbe anche utile dare un'occhiata a questa domanda, dove la risposta accettata dimostra in termini laici come funziona una funzione ricorsiva. Anche se la domanda dell'OP si è occupata di Java, il concetto è lo stesso,

  • Comprendere la ricorsione di base

Un esempio potrebbe essere quello di stampare ogni file in qualsiasi sottodirectory di una determinata directory (se non ci sono collegamenti simbolici all’interno di queste directory che potrebbero in qualche modo interrompere la funzione). Uno pseudo-codice di stampa di tutti i file assomiglia a questo:

 function printAllFiles($dir) { foreach (getAllDirectories($dir) as $f) { printAllFiles($f); // here is the recursive call } foreach (getAllFiles($dir) as $f) { echo $f; } } 

L’idea è di stampare prima tutte le sottodirectory e poi i file della directory corrente. Questa idea viene applicata a tutte le sottodirectory e questo è il motivo per cui chiama questa funzione in modo ricorsivo per tutte le sottodirectory.

Se vuoi provare questo esempio devi controllare le directory speciali . e .. , altrimenti printAllFiles(".") bloccato chiamando printAllFiles(".") tutto il tempo. Inoltre, è necessario controllare cosa stampare e quale è la directory di lavoro corrente (vedere opendir() , getcwd() , …).

La ricorsione è qualcosa che si ripete. Come una funzione che si chiama da se stessa. Permettetemi di dimostrare in un esempio un po ‘pseudo:

Immagina di essere fuori con i tuoi amici a bere birra, ma tua moglie ti darà un inferno se non torni a casa prima di mezzanotte. A questo scopo, creiamo la funzione orderAndDrinkBeer ($ time) in cui $ time è mezzanotte meno il tempo necessario per terminare il drink corrente e tornare a casa.

Quindi, arrivando al bar, ordini la tua prima birra e inizi a bere:

 $timeToGoHome = '23'; // Let's give ourselves an hour for last call and getting home function orderAndDrinkBeer($timeToGoHome) { // Let's create the function that's going to call itself. $beer = New Beer(); // Let's grab ourselves a new beer $currentTime = date('G'); // Current hour in 24-hour format while ($beer->status != 'empty') { // Time to commence the drinking loop $beer->drink(); // Take a sip or two of the beer(or chug if that's your preference) } // Now we're out of the drinking loop and ready for a new beer if ($currentTime < $timeToGoHome) { // BUT only if we got the time orderAndDrinkBeer($timeToGoHome); // So we make the function call itself again! } else { // Aw, snap! It is time :S break; // Let's go home :( } } 

Ora speriamo solo che non sei stato in grado di bere abbastanza birra per diventare così intossicato che tua moglie ti farà dormire sul divano, a prescindere dal fatto di essere a casa in tempo -.-

Ma sì, è più o meno come va la ricorsione.

È una funzione che chiama se stessa. È utile per camminare su certe strutture dati che si ripetono, come gli alberi. Un DOM HTML è un classico esempio.

Un esempio di una struttura ad albero in javascript e una funzione ricorsiva per “camminare” sull’albero.

  1 / \ 2 3 / \ 4 5 

 var tree = { id: 1, left: { id: 2, left: null, right: null }, right: { id: 3, left: { id: 4, left: null, right: null }, right: { id: 5, left: null, right: null } } }; 

Per camminare sull’albero, chiamiamo ripetutamente la stessa funzione, passando i nodes figli del nodo corrente alla stessa funzione. Chiamiamo quindi di nuovo la funzione, prima sul nodo sinistro e poi a destra.

In questo esempio, otterremo la profondità massima dell’albero

 var depth = 0; function walkTree(node, i) { //Increment our depth counter and check i++; if (i > depth) depth = i; //call this function again for each of the branch nodes (recursion!) if (node.left != null) walkTree(node.left, i); if (node.right != null) walkTree(node.right, i); //Decrement our depth counter before going back up the call stack i--; } 

Alla fine chiamiamo la funzione

 alert('Tree depth:' + walkTree(tree, 0)); 

Un ottimo modo per comprendere la ricorsione è quello di scorrere il codice in fase di runtime.

In poche parole: una funzione ricorsiva è una funzione che chiama se stessa.

La ricorsione è un modo elegante per dire “fai questa cosa di nuovo fino alla fine”.

Due cose importanti da avere:

  1. Un caso base: hai un objective da raggiungere.
  2. Un test – Come sapere se hai capito dove stai andando.

Immagina un compito semplice: ordina una pila di libri in ordine alfabetico. Un semplice processo sarebbe prendere i primi due libri, ordinarli. Ora, ecco che arriva la parte ricorsiva: ci sono più libri? Se è così, fallo di nuovo. Il “rifarlo” è la ricorsione. Il “ci sono altri libri” è il test. E “no, niente più libri” è il caso base.

È molto semplice, quando una funzione si chiama per eseguire un compito per un numero indefinito e finito di tempo. Un esempio tratto dal mio codice, funzione per il popolamento di un albero di categorie multilivello

  function category_tree ($ parent = 0, $ sep = '')
 {
     $ q = "seleziona id, nome da categorye dove parent_id =". $ parent;
     $ Rs = mysql_query ($ q);
     while ($ rd = mysql_fetch_object ($ rs))
     {
         echo ( 'id.' "> '' $ settembre $ RD-> nome...');
         category_tree ($ RD-> id, $ settembre .'-- ');
     }
 } 

La migliore spiegazione che ho trovato quando stavo imparando che io sono qui: http://www.elated.com/articles/php-recursive-functions/

È perché una cosa:

La funzione quando viene chiamata in memoria (viene creata una nuova istanza)

Quindi la funzione ricorsiva NON È CALLLING STESSO , ma chiama un’altra istanza – quindi non è una funzione in memoria a fare un po ‘di magia. Il suo paio di istanze in memoria che si stanno restituendo alcuni valori – e questo comportamento è lo stesso quando per esempio la funzione a sta chiamando la funzione b. Hai due istanze e anche se la funzione ricorsiva chiama nuova istanza di se stessa.

Prova a disegnare la memoria con istanze su carta: avrà un senso.

La ricorsione è un’alternativa ai loop, è abbastanza raro che porti più chiarezza ed eleganza al tuo codice. Un buon esempio è stato dato dalla risposta di Progman, se non usasse la ricorsione sarebbe costretto a tenere traccia di quale directory è attualmente (questo è chiamato stato) le ricorsioni gli permettono di fare la contabilità usando lo stack (l’area in cui le variabili e l’indirizzo di ritorno di un metodo sono memorizzati)

Gli esempi standard fattoriali e Fibonacci non sono utili per comprendere il concetto perché sono facili da sostituire con un ciclo.

Fondamentalmente questo. Continua a chiamarsi fino al suo completamento

 void print_folder(string root) { Console.WriteLine(root); foreach(var folder in Directory.GetDirectories(root)) { print_folder(folder); } } 

Funziona anche con i loop!

 void pretend_loop(int c) { if(c==0) return; print "hi"; pretend_loop(c-); } 

Puoi anche provare a cercarlo su google. Nota “Volevi dire” (fai clic su di esso …). http://www.google.com/search?q=recursion&spell=1

Ecco un esempio pratico (ce ne sono già molti buoni). Volevo solo aggiungerne uno utile a quasi tutti gli sviluppatori.

A un certo punto, gli sviluppatori dovranno analizzare un object come con una risposta da un’API o da qualche tipo di object o array.

Inizialmente questa funzione viene chiamata per analizzare un object che può contenere solo parametri, ma cosa succede se l’object contiene anche altri oggetti o matrici? Questo dovrà essere affrontato, e per la maggior parte la funzione di base lo fa già, quindi la funzione si chiama di nuovo (dopo aver verificato che la chiave o il valore è o un object o un array) e analizza questo nuovo object o array. In definitiva, ciò che viene restituito è una stringa che crea ciascun parametro su una riga di per sé per leggibilità, ma è altrettanto semplice registrare i valori in un file di registro o inserirli in un DB o in qualsiasi altro modo.

Ho aggiunto il parametro $prefix per utilizzare l’elemento parent per aiutare a descrivere la variabile end in modo che possiamo vedere a cosa si riferisce il valore. Non include cose come valori nulli, ma questo può essere modificato da questo esempio.

Se hai l’object:

 $apiReturn = new stdClass(); $apiReturn->shippingInfo = new stdClass(); $apiReturn->shippingInfo->fName = "Bill"; $apiReturn->shippingInfo->lName = "Test"; $apiReturn->shippingInfo->address1 = "22 S. Deleware St."; $apiReturn->shippingInfo->city = "Chandler"; $apiReturn->shippingInfo->state = "AZ"; $apiReturn->shippingInfo->zip = 85225; $apiReturn->phone = "602-312-4455"; $apiReturn->transactionDetails = array( "totalAmt" => "100.00", "currency" => "USD", "tax" => "5.00", "shipping" => "5.00" ); $apiReturn->item = new stdClass(); $apiReturn->item->name = "T-shirt"; $apiReturn->item->color = "blue"; $apiReturn->item->itemQty = 1; 

e usare:

 var_dump($apiReturn); 

ritornerà:

object (stdClass) # 1 (4) {[“shippingInfo”] => object (stdClass) # 2 (6) {[“fName”] => stringa (4) “Bill” [“lName”] => stringa ( 4) “Test” [“address1”] => string (18) “22 S. Deleware St.” [“city”] => string (8) “Chandler” [“stato”] => string (2) “AZ” [“zip”] => int (85225)} [“phone”] => stringa (12 ) “602-312-4455” [“transactionDetails”] => array (4) {[“totalAmt”] => string (6) “100.00” [“currency”] => string (3) “USD” [” tax “] => string (4)” 5.00 “[” shipping “] => string (4)” 5.00 “} [” item “] => object (stdClass) # 3 (3) {[” name “] = > string (7) “T-shirt” [“color”] => string (4) “blue” [“itemQty”] => int (1)}}

e qui è il codice per analizzarlo in una stringa con un’interruzione di riga per ogni parametro:

 function parseObj($obj, $prefix = ''){ $stringRtrn = ''; foreach($obj as $key=>$value){ if($prefix){ switch ($key) { case is_array($key): foreach($key as $k=>$v){ $stringRtrn .= parseObj($key, $obj); } break; case is_object($key): $stringRtrn .= parseObj($key, $obj); break; default: switch ($value) { case is_array($value): $stringRtrn .= parseObj($value, $key); break; case is_object($value): $stringRtrn .= parseObj($value, $key); break; default: $stringRtrn .= $prefix ."_". $key ." = ". $value ."
"; break; } break; } } else { // end if($prefix) switch($key){ case is_array($key): $stringRtrn .= parseObj($key, $obj); break; case is_object($key): $stringRtrn .= parseObj($key, $obj); break; default: switch ($value) { case is_array($value): $stringRtrn .= parseObj($value, $key); break; case is_object($value): $stringRtrn .= parseObj($value, $key); break; default: $stringRtrn .= $key ." = ". $value ."
"; break; } // end inner switch } // end outer switch } // end else } // end foreach($obj as $key=>$value) return $stringRtrn; } // END parseObj()

Ciò restituirà l’object come segue:

 shippingInfo_fName = Bill shippingInfo_lName = Test shippingInfo_address1 = 22 S. Deleware St. shippingInfo_city = Chandler shippingInfo_state = AZ shippingInfo_zip = 85225 phone = 602-312-4455 transactionDetails_totalAmt = 100.00 transactionDetails_currency = USD transactionDetails_tax = 5.00 transactionDetails_shipping = 5.00 item_name = T-shirt item_color = blue item_itemQty = 1 

Ho fatto le istruzioni switch nidificati per evitare confusione con if . . . ifelse . . . else if . . . ifelse . . . else if . . . ifelse . . . else , ma era quasi il tempo. Se aiuta, basta chiedere i condizionali if e io posso incollarli per chi ne ha bisogno.

Camminare attraverso un albero di directory è un buon esempio. Puoi fare qualcosa di simile per elaborare un array. Ecco una semplice funzione ricorsiva che elabora semplicemente una stringa, una semplice serie di stringhe o una matrice nidificata di stringhe di qualsiasi profondità, sostituendo le istanze di ‘hello’ con ‘addio’ nella stringa o i valori dell’array o qualsiasi sub-array:

 function replaceHello($a) { if (! is_array($a)) { $a = str_replace('hello', 'goodbye', $a); } else { foreach($a as $key => $value) { $a[$key] = replaceHello($value); } } return $a } 

Sa quando smettere, perché ad un certo punto la “cosa” che sta elaborando non è una matrice. Ad esempio, se chiami replaceHello (“ciao”), restituirà “addio”. Se gli mandi una serie di stringhe, anche se si chiamerà una volta per ogni membro dell’array, restituirà la matrice processata.

Se aggiungi un certo valore (diciamo “1”) all’esempio di Anthony Forloney, tutto sarà chiaro:

 function fact(1) { if (1 === 0) { // our base case return 1; } else { return 1 * fact(1-1); // <--calling itself. } } 

originale:

 function fact($n) { if ($n === 0) { // our base case return 1; } else { return $n * fact($n-1); // <--calling itself. } } 

Questo è un esempio molto semplice di fattoriale con ricorsione:

I fattoriali sono un concetto matematico molto semplice. Sono scritti come 5! e questo significa 5 * 4 * 3 * 2 * 1. Quindi 6! è 720 e 4! è 24.

 function factorial($number) { if ($number < 2) { return 1; } else { return ($number * factorial($number-1)); } } 

spero che questo sia utile per te. 🙂

Funziona un semplice esempio ricorsivo (Y)

  

Ricorsione usata per la costante di Kaprekar

 function KaprekarsConstant($num, $count = 1) { $input = str_split($num); sort($input); $ascendingInput = implode($input); $descendingInput = implode(array_reverse($input)); $result = $ascendingInput > $descendingInput ? $ascendingInput - $descendingInput : $descendingInput - $ascendingInput; if ($result != 6174) { return KaprekarsConstant(sprintf('%04d', $result), $count + 1); } return $count; 

}

La funzione continua a chiamarsi con il risultato del calcolo fino a raggiungere la costante Kaprekars, alla quale restituirà il numero di volte in cui sono stati effettuati i calcoli.

/ modifica Per chiunque non conosca Kaprekars Constant, ha bisogno di un input di 4 cifre con almeno due cifre distinte.