Wie speichere ich das ursprüngliche Argument in einer rekursiven Funktion in PHP?

Question

Ich bin in PHP arbeiten an einem Euler-Problem. Ich habe diese Funktion so weit:

<?php 
$biggest = 0; 
$counter = 1; 
function test($i){ 
    global $biggest; 
    global $counter; 
    if ($i == 1) { 
     echo "I'm done! Took me $biggest steps"; 
    } 
    else { 
     if ($i%2 == 0) { 
      $counter = $counter + 1; 
      if ($counter>$biggest) { 
       $biggest = $counter; 
      } 
      test($i/2); 
     } 
     else { 
      $counter = $counter + 1; 
      if ($counter>$biggest) { 
       $biggest = $counter; 
      } 
      test(3*$i+1); 
     } 
    } 
} 

test(13); 
?> 

ich das Problem meist geleckt haben, aber ich kann nicht zurück auf den ursprünglichen Eingang zu bekommen scheinen. Die Frage ist: "Wenn Sie eine Zahl haben, wenn ungerade 3n + 1 erhalten, wenn gerade, erhalten n/2, tun, bis 1 zurückgibt. Welcher Startwert ergibt die meisten" Schritte ", bevor Sie zu einem kommen?" Ich gebe derzeit die Anzahl der Schritte zurück, aber ich setze immer $ i zurück, während ich rekursiere, also kann ich nicht aufzeichnen, welche startende # meine größte Anzahl an Schritten hervorgebracht hat.

Wie kann ich diese Nummer behalten, aber nicht bei der nächsten Instanz der Schleife zerstören? (Ich werde schließlich dies in eine Schleife für ($ i = 1, $ i < 1000000, $ i ++) wickeln)

Vielen Dank!

Answer 1

Ein gemeinsamer Ansatz ist das ursprüngliche Argument durch jedes Mal passieren, dass so, wenn schließlich Sie Ihren Basisfall bekommen Sie es noch zur Verfügung haben. Ein primitives (und fast vollständig nicht verwandtes Beispiel):

<?php 

function fact($n) { 
    if($n == 1) return 1; 
    else return $n * fact($n - 1); 
} 

?>

Dies ist eine äußerst einfache Implementierung der Fakultät in PHP. Nun sagen Sie aus irgendeinem Grund den Anfangswert in dem letzten Schritt haben wollte: Sie eine Wrapper-Funktion bauen würde fact($n), die so etwas wie memory_fact($n, $initial) nennen würde:

<?php 

function fact($n) { 
    return memory_fact($n, $n); 
} 

function memory_fact($n, $initial) { 
    if($n == 1) return 1; 
    else return $n * memory_fact($n - 1, $initial); 
} 

?>

Auf diese Weise memory_fact immer weiß, wo es angefangen hat.

Answer 2

Es ist einfach, übergeben Sie es einfach als Parameter! Hier einige Pythons-ish Pseudo-Code:

def func(start, arg): 
    if foo(arg): 
     return func(start, arg+1) 
    else: 
     return [start, arg] 

Answer 3

Sie benötigen die Globals nicht; Globals sind böse. Versuchen Sie, etwas Nützliches von test() zurückzugeben. Außerdem finden Sie oben test() verschwendet viele Zyklen. Versuchen Sie es mit memoization.

Hier ist ein memoization Beispiel für die Berechnung der Fibonacci-Zahlen:

function fib($n) { 
    static $data = array(1, 1); 
    if (!isset($data[$n])) { 
     $data[$n] = fib($n-1) + fib($n-2); 
    } 
    return $data[$n]; 
} 

Beachten Sie, dass es auch andere Zeit-efficent konstanter Raum Ansätze sind Fibonacci-Zahlen zu behandeln (einschließlich eines in O (log n) Zeit), aber die Collatz-Vermutung ist ein wenig komplizierter.