PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : rekursive Methode? - Was ist es genau


Gast
2005-12-21, 19:17:10
Hallo, ich soll folgende Aufgabe in Java lösen:

Erstellen Sie eine rekursive Methode, die die Summe der ungeraden Zahlen zwischen 0 und n (eingeschlossen) berechnet.

import Prog1Tools.IOTools;
public class P41 {
public static void main (String []args ) {


int n = IOTools.readInteger ("Berechnung der ungeraden Zahlen zwischen 0 und ?: ");
int sum=0;
for ( int i = 0; i<=n ;i++) {

if (i % 2 != 0) {
sum = sum + i ;
}

// System.out.println(i); // Liste der ungeraden Zahlen

}
System.out.print(sum);
}
}


Ist dies nun rekursiv? oder ist es ganz was anderes? Hab kein plan .. pls help :/

SgtDirtbag
2005-12-21, 19:22:25
Rekursiv ist eine Methode,wenn sie sich selbst mit einem anderen Startparameter aufruft.

Ich seh bei dir aber nur ne for-Schleife mit if-Anweisung. : (

Hier ist Rekursivität am Beispiel der Fibonaccizahlen erklärt:
http://www.pohlig.de/Unterricht/Inf2003/Tag16/15.7_Fibonacci_rekursiv.htm

MadMan2k
2005-12-21, 19:25:59
nö - aber ehrlich gesagt, kann ich mir auch nicht so recht vorstellen, was man da groß rekursiv machen sollte...

höchstens:

function fook(n) {
while(n % 2 == 0) {
if(n == 0) return 0;
n -= 1;
}

return n + fook(n-1);
}

Trap
2005-12-21, 19:34:18
f(x,y) =
x>y| 0
true | x+f(x+2,y)

x(n)=f(1,n)

Achso, das ist pseudocode, x|y soll sein y wenn x.

Editx: Es soll die Summe der ungeraden Zahlen sein, nicht die Anzahl...

zeckensack
2005-12-21, 20:11:47
private static int blargh(int n) {
if (n<=0) return(0);
else
if (n==1) return(1);
else
if ((n%2)==0) return(blargh(n-1));
else return(n+blargh(n-2));
}

public static void main(String[] args) {
int n = IOTools.readInteger ("Hmmm? ");
System.out.print(blargh(n));
}

Trap
2005-12-21, 20:14:44
@Zeckensack:
Dein Code ist sicher falsch.

Der PHP-Code sieht zumindest merkwürdig aus, ich würde spontan bezweifeln das er funktionert.

Edit: Nochmal über den PHP-Code geguckt, ziemlich umständlich geschrieben, sollte aber funktionieren wenn n=n-- das richtige macht (keine Ahnung von PHP).

zeckensack
2005-12-21, 20:26:05
@Zeckensack:
Dein Code ist sicher falsch.Jawoll. Ich hab's ausgebessert.
Rekursiv ist in dem Fall echt ein umständliches Gefrickel. Typisch Lehramt :rolleyes:
Ansonsten noch ein sinnvoller Beitrag @ Topic:Rekursiv ist eine Methode,wenn sie sich selbst mit einem anderen Startparameter aufruft.Ack.

Gast
2005-12-21, 20:53:19
hi again, also ich verstehe bei der sache eines noch nicht ganz und zwar warum prüfst du

if (n<=0) return(0);
else
if (n==1) return(1);

ist das nur für die sonderfälle n = 0, n=1 oder hat es andere Zwecke?

wie müsste man sich das im speichermodell vorstellen..?

z.b . zelle x für bei n = 5 , 5->5+3->5+3+1->9 ?

Trap
2005-12-21, 20:55:27
Die Definition von rekursiv ist "ruft sich selbst auf". Wie sie sich selbst aufruft ist völlig egal.

int b() { return b();} // ist rekursiv

bool odd(int n){ // ist gegenseitig rekursiv
return even(n-1);
}

bool even(int n) { // ist gegenseitig rekursiv
if(n==0)return true;
else return odd(n-1);
}

Monger
2005-12-21, 21:48:42
Wie war das doch?

"Um Rekursion zu verstehen, muss man zuerst Rekursion verstanden haben!" :D

Ich finde Rekursion hässlich. Zweifellos manchmal notwendig, aber hässlich.

Coda
2005-12-21, 22:09:18
Ohje, dann halte dich von funktionalen Sprachen fern :D

Gast
2005-12-21, 22:13:19
Wie war das doch?

"Um Rekursion zu verstehen, muss man zuerst Rekursion verstanden haben!" :D

Ich finde Rekursion hässlich. Zweifellos manchmal notwendig, aber hässlich.Nein, unendlich schön... Schon mal einen Baum "rekursiv" traversiert ohne Rekursion? Igitt igitt, dies *ist* hässlich ohne Ende.

Monger
2005-12-21, 22:24:37
Ohje, dann halte dich von funktionalen Sprachen fern :D

Glaub mir, das versuche ich auch so um jeden Preis! ;)

Nein, unendlich schön... Schon mal einen Baum "rekursiv" traversiert ohne Rekursion? Igitt igitt, dies *ist* hässlich ohne Ende.

Was ich meine ist: Rekursion ist beschissen zu entwickeln. Ein rekursiver Code sieht nicht aus als wäre er rekursiv, deshalb ist er mies zu schreiben, zu warten und zu erweitern.

Senior Sanchez
2005-12-21, 22:25:39
Die Definition von rekursiv ist "ruft sich selbst auf". Wie sie sich selbst aufruft ist völlig egal.

int b() { return b();} // ist rekursiv

bool odd(int n){ // ist gegenseitig rekursiv
return even(n-1);
}

bool even(int n) { // ist gegenseitig rekursiv
if(n==0)return true;
else return odd(n-1);
}

Naja, ruft sich selbst auf stimmt nicht ganz mit der Definition überein die ich kenne ;)

Eine Funktion oder eine Datenstruktur ist rekursiv wenn sie vollständig oder teilweise durch sich selbst definiert wird.

Gast
2005-12-21, 22:33:44
Naja, ruft sich selbst auf stimmt nicht ganz mit der Definition überein die ich kenne ;)

Eine Funktion oder eine Datenstruktur ist rekursiv wenn sie vollständig oder teilweise durch sich selbst definiert wird.Ich denke Rekursion wird viel mehr verwendet als man gemeinhin denkt. z.B. sind Politiker extrem rekursiv: Sie wollen immer wieder gewählt werden. :smile: Jegliche Art von Fortpflanzung ist zumindest ansatzweise :smile: rekursiv. Also ein virtuelles perpetuum mobile (ohne energiesätze zu berücksichtigen :smile:)

Trap
2005-12-21, 22:39:02
Wenn eine Funktion sich selbst aufruft ist sie doch durch sich selbst definiert.

Bei Funktionen stimmt "ruft sich selbst auf" genau mit "ist durch sich selbst definiert" überein.

zeckensack
2005-12-22, 05:02:28
hi again, also ich verstehe bei der sache eines noch nicht ganz und zwar warum prüfst du

if (n<=0) return(0);
else
if (n==1) return(1);

ist das nur für die sonderfälle n = 0, n=1 oder hat es andere Zwecke?Der erste Test ist der Sonderfall für "ungesunde" Eingaben, in dem Fall wenn der User es fertigbringt, eine negative Zahl einzutippen.
Wäre mir das egal, hätte ich folgendes gewählt:if (n<2) return(n);Der zweite Test (bzw die gerade erwähnte mögliche Kombination) ist kein Sonderfall, sondern das Terminal. Eine Rekursion die nicht terminiert nützt dir nämlich garnichts (=>Stack Overflow =>Absturz).
wie müsste man sich das im speichermodell vorstellen..?

z.b . zelle x für bei n = 5 , 5->5+3->5+3+1->9 ?Genau. Ich würd's jetzt mal so darstellen:
blargh(5)=
5+blargh(3)= //>> Rekursion
5+3+blargh(1)= //>> Rekursion
//<< blargh(1) gibt 1 zurück
5+3+ 1= //<< blargh(3) gibt 4 zurück
5+4= //<< blargh(5) gibt 9 zurück
9

HAL
2005-12-22, 09:43:28
Was ich meine ist: Rekursion ist beschissen zu entwickeln. Ein rekursiver Code sieht nicht aus als wäre er rekursiv, deshalb ist er mies zu schreiben, zu warten und zu erweitern.
Also wenn ich ne rekursive Methode schreibe, steht da groß dick und fett drüber: "Achtung Rekursiv!" ;)

Aber schlimm finde ich Rekursion nicht. Für manche Aufgaben ist rekursiver Code einfach ne Offenbarung, sofern passend verwende ich sehr gerne Rekursionen. Ich finde ihn auch nicht mies zu schreiben, im Gegenteil, oft wäre es ohne Rekursion ne Plackerei.

PS: OK, Debuggen ist auf jeden Fall die Hölle... :D

Muh-sagt-die-Kuh
2005-12-22, 10:41:52
Es gibt Probleme, die lassen sich iterativ einfach(er) lösen und es gibt ebenso Probleme, die sich rekursiv einfach(er) lösen lassen.....man muss einfach nur die passende Methode wählen.

Fibonacci rekursiv zu berechnen ist genauso Schwachsinn wie das iterative Erzeugen eines k-d-Baums ;)

mithrandir
2005-12-22, 11:04:15
Was wäre ein Beispiel, wo Rekursion sinnvoll ist? Mir fällt da z.B. spontan ein XML(o.ä.)-Parser oder andere Baum-Abbildungen ein.

Ansonsten bin ich bislang mit nur sehr wenigen Ausnahmen auch ohne Rekursionen durchs Programmier-Leben gekommen ; - )

Gast
2005-12-22, 12:32:58
Was wäre ein Beispiel, wo Rekursion sinnvoll ist? Mir fällt da z.B. spontan ein XML(o.ä.)-Parser oder andere Baum-Abbildungen ein.

Um bei PHP ein Array mit n Dimensionen zu prüfen (da bei PHP die Anzahl der Dimension nicht bekannt sein muss) und die Werte in jeder Dimension zu bearbeiten.

function edit_array($val)
{
if(is_array($val))
{
while(list($key, $value) = each($val))
{
$val[$key] = edit_array($vars[$key]);
}
reset($val);
}
else
{
$val = something($val);
}
return $val;
}

Gast
2005-12-22, 12:50:19
Verschrieben:

$val[$key] = edit_array($vars[$key]);

soll

$val[$key] = edit_array($val[$key]);

heißen.

Neomi
2005-12-22, 19:49:32
Was wäre ein Beispiel, wo Rekursion sinnvoll ist?

Das Minispiel Minesweeper ist ein nahezu perfektes Beispiel für Rekursion. Öffnet man ein Feld, das an keine Bombe angrenzt, öffnet es die acht umliegenden Felder ebenfalls. Ungefähr so:

struct Field
{
bool Opened;
bool HasMine;
int AdjacentMines;
};

Field * pMineField;
int FieldSizeX;
int FieldSizeY;

void OpenField (int x, int y)
{
Field * pField;

if ((x < 0) || (x >= FieldSizeX) || (y < 0) || (y >= FieldSizeY))
return;

pField = &pMineField [y * FieldSizeX + x];

if (pField->Opened)
return;

pField->Opened = true;

if (pField->HasMine)
{
// Boom!

return;
}

if (pField->AdjacentMines == 0)
{
OpenField (x - 1, y - 1);
OpenField (x, y - 1);
OpenField (x + 1, y - 1);
OpenField (x - 1, y);
OpenField (x + 1, y);
OpenField (x - 1, y + 1);
OpenField (x, y + 1);
OpenField (x + 1, y + 1);
}

return;
}

Wanginator
2005-12-22, 20:28:48
Rekursion ist ein sehr sinnvolles Prinzip, man sollte es nicht verachten. In den meisten iterativen Sprachen, wie z.B. bei Java, ist es evtl. stilistisch nicht toll zu gebrauchen, da eine iterative Variante effizienter wäre. In funktionalen Sprachen ist aber ohne Rekursion nichts möglich. Und obwohl Rekursion meist speicheraufwendiger ist, lassen sich damit Algorithmen sehr elegant ausdrücken, z.B. QuickSort, naive Defintion/Berechnung der Fibonacci-Zahlen. Letzlich ist Rekursion notwendig für das Entwerfen effizienter Lösungsstrategien, wie z.B. Divide-and-Conquer, oder auch Dynamisches Programmieren. Ebenfalls lassen sich Pseudo-Code-Algorithmen schnell beschreiben durch eine Abbruchsbedingung und einer Rekursionsschleife.
Als Bespiel seien hier mal Sortieralgorithmen aufgeführt, die iterativ sehr umfangreich aussehen, während rekursiv schlank und verständlich. Anderes Beispiel: Traversieren von Bäumen: Tiefensuche und Breitensuche sind rekursiv sehr leicht zu implementieren.

zur Frage des Threaderstellers:
public static int foo(int n) {
if (n <= 0) return 0;
if (n%2 == 0) return foo(n-1);
return n + foo(n-2);
}

EDIT: Dabei ist diese Lösung noch nicht endrekursiv, wer will darf sie gerne in endrekursive Form bringen :)