Dato: Tirsdag den 16. januar 2018 uge: 3

Rekursion

factorialRecursive:
'; // echo factorialRecursive(5); // direkte rekursion det korteste version :) function factotialRecursive_2($num) { return $num > 1 ? $num * factotialRecursive_2($num - 1) : 1; } echo '
factotialRecursive_2:
'; echo factotialRecursive_2(5); function factorialIterative($num) { $factorial = 1; for ($i = 1; $i <= $num; $num--) { $num > 1 ? $factorial *= $num : 1; } return $factorial; } echo '
factorialIterative:
'; echo factorialIterative(5); /*------------------------------------------------------------------------*/ // head rekursion (hoved nieogonowa) - rekursion kald findes før blok, // hvor udføres forædlingsprocesser (processing operations) // hver worker skal overholde følgende regler (tasks): // Kald til næste station udføres først - før optælling eller summering af papagøjer // Udførelsen af ​​arbejdet suspenderes, indtil det øjeblik, // hvor alle stationer vil rapportere sit antal papegøjer. // 1. kald næste station // 2. tæl antal af papegøjer // 3. kald næste station // 4. overfør af delsum til den tidligere station // tail rekursion (hale ogonowa) - rekursion kald findes efter blok, hvor udføres // forædlingsprocesser (processing operations) // her rekursion kald forgår efter forædlingsprocesser // (processing operations, og er det sidste handling, der udføres i funktionen // 1. tæl antal af papegøjer det ses på stationen // 2. sum antal til summen du har modtaget fra tidligere station // 3. kald næste station og overfør af delsum af papagøjer det ses // 4. vent po opkald fra næste station, hvor du modtager summen af alle synlige papagøjer // og videregiv den til den tidligere station /*------------------------------------------------------------------------*/ /*------------------------------------------------------------------------*/ /* Rigtig god idé for gentagelser (rekursion) */ /*------------------------------------------------------------------------*/ /*------------------------------------------------------------------------*/ // Problem - beregn summen af ​​heltal i arrayet // Opgaven: skriv en rekursiv funktion det som parametre bruger // et array med heltal og dets størrelse (size) // Problemløsning: // 1. Det første vi tænker om at det er en triviel - iterative løsning. $integers = array(1, 5, 5, 4, 7); function iterativeArraySum ($integers, $size) { // echo $size; // die(); $sum = 0; for( $i = 0; $i < $size; $i++) { $sum += $integers[$i]; } return $sum; } echo '
iterativeArraySum:
'; echo iterativeArraySum ($integers, count($integers)); /*------------------------------------------------------------------------*/ // Vi prøver nu at skrive kode, det er mellem det iterative og den endelig rekursion løsning // Iterativ funktion beholdes og vi skriver en anden, vi kalder den afsender (dispatcher) // Afsender (dispatcher) vil fremsende det meste af arbejdet til en tidligere defineret // iterativt funktion, og derefter vil bruge modtaget information til at løse hele problemet. // Mens vi skriver Afsender (dispatcher), skal vi overholde de to regler: // 1. afsender skal kunne fuldt ud at håndtere de mest trivielle tilfælde // uden behov for den iterative funktionskald. // 2. afsender skal overføre reducered versioner af problemet til den iterative funktion // // ad. 1. I starten skal vi fastlægge det mest trivielle tilfælde: // a) Hvis parameter $size er lige 0, det betyder at vi har et tøm array dvs. // summen af heltal er lige med 0 // b) Hvis parameter $size er lige 1, det betyder at vi har et heltal i arrayet dvs. // summen af heltal er lige det heltal. Det er også en trivielle tilfældet, men // det er nok hvis vi kun bruger den første, så vores funktion kan håndtere // den specielle tilfæld, hvor vi ved allerede kender summen(0) // ad. 2. For at anvende den anden regle, må vi definere hvordan afsender skal // overføre den reducered versioner af problemet til den iterative funktion: // Vi kan nemt at sende en mindre værdi af parameter $size // F.eks. Hvis afsender får et parameter $size med værdi 10, funktion er bed om // at beregne summen af 10 heltal fra arrayet. // Når afsender overfører til den iterative funktion 9 som værdi af parameter $size, // kræver den at det vil blive beregnet en sum for de første heltal fra arrayet. // På den måde kan afsender efter modtagelse af resultat tilføje // det sidste tiende heltal for at udregne det endelig sum af de 10 heltal. // !Bemærk at: reduktion værdi af $size om 1, under kald af den iterative funktion // maksimilisere mængde af arbejde den skal udføres, samtidig minimaliseres det // antallet af handlinger det skal udføres af afsender(dispacher). // // Dette er ANBEFALET fremgangsmåde, hvor afsender (dispacher) // UNDGÅR at udføre den største del af arbejdet!!! :) /******************************************************************************/ // Så efter vi har samlet alle idee, kommer vi frem til vores afsender funktion: // $integers = array(1, 5, 5, 4, 7); function arraySumDelegate($integers, $size) { if ($size == 0) return 0; // 1 $lastNumber = $integers[$size - 1]; // 2 $allButLastSum = iterativeArraySum ($integers, $size - 1); // 3 resultat vi blive gemt i en lokal variable return $lastNumber + $allButLastSum; // 4 } echo '
arraySumDelegate:
'; echo arraySumDelegate ($integers, count($integers)); /******************************************************************************/ /******************************************************************************/ /******************************************************************************/ /******************************************************************************/ // Så har vi næsten vores rekursiv funktion. Det er det det praktiske gå ud på: // "Rigtig god idé for gentagelser" (rekursion) // For at omdane eksisterende iterativ løsning til en rekursiv version, skal det // gøres en til simpel ting, så afsender kan kalde sig selv i linje, hvor det var // kald til den iterative funktion. // Efter vi har gjort det, kan vi fjerne vores nu overflødlige iterative funktion: // iterativeArraySum // $integers = array(1, 5, 5, 4, 7); function arraySumRecursive ($integers, $size) { // 1 if ($size == 0) return 0; $lastNumber = $integers[$size - 1]; $allButLastSum = arraySumRecursive ($integers, $size - 1); // 2 resultat vi blive gemt i en lokal variable return $lastNumber + $allButLastSum; } echo '
arraySumRecursive:
'; echo arraySumRecursive ($integers, count($integers)); // 1. funktions signatur (navn) er blevet ændret // 2. funktion kalder sig selv, hvor vi tidligere har kald den iterative funktion // inspiration og kilde: V. Anton Spraul - "Tænk som progammør - tekniker for den kreative problemløsning" ?>

Overskrift

Link

Link

Link

Link

Link