Php rekursiv

Computer: Software & Programmierung PHP
#1

Liebe/-r Experte/-in,

ich habe eine Frage bezüglich rekursivem Programmieren in PHP. Und zwar muss ich ein Skript für die UNI schreiben, in der ich eine Funktion habe, die integer werte annimmt und dann die Summe ausgibt. Die Summe der ersten $x-Zahlen müssen berechnet werden (positive natürliche Zahlen).
Die Funktion soll rekursiv programmiert werden.

Eingabe 3->1+2+3 = 6
Eingabe 4->1+2+3+4 = 10
Eingabe 5->1+2+3+4+5 = 15

So soll das ungefähr beispielhaft aussehen.

Bis jetzt sieht mein Skript wie folgt aus:

<?php $int1 = 1;
$int2 = 2; $int3 = 3; function summe($int1,$int2){ global $int1; global $int2; echo $result = $int1 + $int2; } summe($int1,$int2); ?\> Ausgegebn wird lediglich die Summe der 2 Integer-Zahlen. Wie realisiere ich die Funktion jedoch rekursiv ? Vielen Dank für die Hilfe im Voraus. Mit freundlichen Grüßen
#2

Wenn ich das jetzt richtig verstanden habe und die Funktion nur die Summe der übergebenen Zahlen zurückgeben soll, dann ginge das z.B. so:

<?php function summe($var = array()) {
foreach ($var as $v) { $summe = $summe + $v; } return $summe; } echo summe($array); ?\> Die zu addierenden Zahlen müssten der Funktion dann als Array übergeben werden. Oder ist es eher so zu verstehen: Die ersten Zahlen ab 1 bis $x sollen addiert werden? Das sähe eher so aus: <?php function summe($x) {
for ($i = 1; $i = $x; $i++) { $v = $v + $i; } return $v; } echo summe($x); ?\>
#3

Hallo Rufat

Ich verstehe deinen Ansatz nicht ganz. Du hast die Funktion summe und der übergibst du zwei Prameter int1 und int2.
Danach überschreibst du die beiden Parameter, die du übergeben hast mit den Global Werten. Wieso?
Und der Output ist dann int1+int2…

Bis jetzt ist an deiner Funktion nichts rekursiv. Damit sie rekursiv ist, must du ja irgendwo in der Funktion die Funktion selber wieder aufrufen.

Bsp:

iAmRecursiv(5);
function iAmRecursiv($foo){
iAmRecursiv($foo);
}
Diese Methode ist natürlich endlos und das Programm wird abstürzen.
Damit eine Rekursion funktioniert muss sie endlich sein und irgendwann auch terminieren.
Also braucht sie eine Abbruchbedingung.

iAmRecursiv(5);
function iAmRecursiv($foo){
if($foo>0){
iAmRecursiv($foo-1);
}
}

Ich hofffe dir etwas weitergeholfen haben zu können. Sonst fragst du einfach nochmal.

Gruss
Mordog

#4

Hallo Rufat.

Der Kniff bei der Rekursion ist, dass sich eine Funktion selbst aufruft. Du sollst alle Zahlen von 1 bis $x summieren. Das lässt sich so ausdrücken:

summe(0) = 0
summe(1) = 0+1 = 1 = summe(0) + 1
summe(2) = 0+1+2 = 3 = summe(1) + 2
summe(3) = 0+1+2+3 = 6 = summe(2) + 3

oder allgemein

summe($x) = summe($x - 1) + $x

damit könnte man dann eine Funktion dieser Art bauen:

<?php function summe($x) {<br /> // Wenn $x Null ist, gib den definierten Wert 0 zurück
 if ($x == 0) return 0;
 // Ansonsten: Wende die Rekursive vorschrift zur Berechnung an
 return (summe($x - 1) + $x);
}

echo "Summe von 0 bis 4:";
echo summe(4);
?\>

Beim Aufruf von summe(4) passiert dann folgendes:

summe(4) = summe(3) + 4

auf der rechten seite muss nun zunächst summe(3) aufgelöst werden

summe(4) = (summe(2) + 3) + 4

und so weiter…

summe(4) = ((summe(1) + 2) + 3) + 4
summe(4) = (((summe(0) + 1) + 2) + 3) + 4

Summe(0) haben wir als die Abbruchbedingung der Rekursion definiert - für summe(0) kommt als Ergebnis nach Definition 0 heraus.
also:

summe(4) = (((0 + 1) + 2) + 3) + 4
 = 0 + 1 + 2 + 3 + 4
 = 10

Alternativ kannst du auch summe(1) = 1 als Abbruchbedingung definieren.

Hoffe, das hat geholfen.

#5

Ausgegebn wird lediglich die Summe der 2 Integer-Zahlen. Wie
realisiere ich die Funktion jedoch rekursiv ?

Hallo Rufat … damit deine Funktion rekursiv arbeitet musst du dir über folgende Dinge bewusst sein:

  1. Wie lange läuft die Rekursion, d.h. an welchem Punkt wird sie unterbrochen und gibt in umgekehrter Reihenfolge das Ergebnis zurück? und
  2. Was heißt überhaupt Rekursion?

Sinnvollerweise sollte deine Funktion nur einen Wert übergeben bekommen, nämlich die Zahl „n“, die als nächstes summiert wird. Die Rekursion kommt dann dadurch zustande, dass diese Zahl „n“ mit dem Ergebnis der Funktion mit dem Parameter „n-1“ addiert wird und zurückgegeben wird. An irgendeinem Punkt muss dieses ständige Aufsummieren natürlich enden. In deinem Fall gibt die Spezifikation „positive/natürliche Zahlen“ diesen „Abbruch“ an: Sobald dein „n“ den Wert 0 erreicht ist die letzte Stufe der Rekursion erreicht. Für den Fall n=5 würde das also so aussehen:

summe(5) -\> 5 + summe(5-1)
 -\> 5 + (4 + summe(4-1))
 -\> 5 + (4 + (3 + summe(3-1)))
 -\> 5 + (4 + (3 + (2 + summe(2-1))))
 -\> 5 + (4 + (3 + (2 + (1 + summe(1-1)))))
 -\> 5 + (4 + (3 + (2 + (1 + (0))))

Die Null in der letzten Zeile signalisiert den Abbruch. Jetzt wird schrittweise von unten nach oben der Wert in der am weitesten links stehenden Klammer zurückgegeben und mit der „nächsthöheren“ Klammer addiert. Sind wir ganz oben angekommen ist die Rekursion vollständig beendet und es wird der Wert 5+4+3+2+1=15 zurückgegeben:

<?php function summe($n) {<br /> if($n \> 0)
 return $n + summe($n-1);
 else
 return $n;
 // return 0; hätte denselben Effekt
}

// Aufruf
echo summe(5); // --\> 15
?\>

Das wichtigste dass du dir zur Rekursion merken solltest ist, dass du a) immer ein Ende, also einen Zweig benötigst in dem kein Aufruf der Funktion selbst statt findet und b) dass Rekursion immer bedeutet, dass sich an irgendeiner Stelle die Funktion selbst aufruft, meist mit einem anderen Wert für den/die Parameter.

Ich hoffe ich konnte dir helfen und dir die Funktionsweise dieser Implementierungsform näher bringen!