Kleines Problem mit der Rekursion

[muff-in]

Hallo,

Ich habe hier ein kleines Problem mit meiner Funktion Rekursion1. Es sollte eingentlich ganz einfach sein, warum funktioniert das denn nicht??

public class rekusion1 {
	public rekusion1(){
		rekursion0(3);}
	
	public int rekursion0(int x){
		if (x == 1){
			return 1;	
		} else if (x >= 1){
			return rekursion0((x-1)+2x-1);
		}
	}
}

Danke schonmal =)

 

[Helgon]

ka wo du das her hast, aber das die main methode fehlt fällt dir nicht auf?
edit:
und "wo ist der fehler" ist kein konkretes problem

 

[muff-in]

Es geht nicht um die main() Methode, ich weiß das sie fehlt, hab den Code ja gekürzt.
Das Problem entsteht, wenn die Funktion sich rekursiv aufruft, in der 2. if Schleife.

 

[Marcinek]

Ist die Methode überhaupt kompilierbar?

Welcher Fehler kommt?

 

[muff-in]

Hat sich erledigt, war ein Mathematischer Fehler.

Edit: Nein, es hat sich doch nicht erledigt.
Komisch, wenn ich den Code so verändere

[...] return rekursion0(x-1+2*x-1);

gibt BlueJ beim complieren missing return statement raus,

und ansonsten, wenn man den Code so lässt wie er ist, also:

public class rekusion1 {
	
	public rekusion1(){
		rekursion0(3);}
	
	public int rekursion0(int x){
		
		if (x == 1){
			return 1;	
		} else if (x >= 1){
			rekursion0((x-1)+2x-1);
		}
	}
}

sagt er in Eclipse: Syntax Error on token "x", delete this token. + Linebreakpoint rekursion1: [line 12] - rekursion0(int)

 

[Final_Striker]

in der 2. if Schleife.

if-schleife


Ich würde mal sagen, dass dir beim zweitem if noch ein else fällt.

 

[muff-in]

Ich glaube das muss 2*x sein, kann das sein?

 

[Marcinek]

jo 2x ist für eine Variable ungültig.

 

[muff-in]

Weiß denn einer wie ich aus einer Methode, eine weitere Methode zürückgeben kann?
Also was ich anstelle dem unterstrichenen Wort eingeben müsste damit die Methode als Rückgabewert sich selbst besitzt?

public class rekusion1 {
	public rekusion1(){
		rekursion0(3);}
	
	public [U]int[/U] rekursion0(int x){
		if (x == 1){
			return 1;	
		} else if (x >= 1){
			[B]return rekursion0(x-1+2*x-1);[/B]
		}
	}
}

 

[JCODA]

Dein Problem ist, dass du kein Wert für x <= 0 zurückgibst, deswegen muss noch ein weiterer else zweig rein (ohne Bedingung).

 

[Marcinek]

Wie meinst du das? Was willst du erreichen?

Das ginge via Reflection, aber ich glaube nicht, dass du das meinst ^^.

 

[muff-in]

Stimmt, so lässt sich die Klasse komplieren:

public class rekusion1 {

    public rekusion1() {
        rekursion0(3);
    }

    public int rekursion0(int x) {

        if (x == 1) {
            return 1;
        } else if (x >= 1) {
            return rekursion0((x - 1) + 2 * x - 1);
        } else {
            return rekursion0(x);
        }
    }
}

Aber es kommen sehr viele StackOverFlow Errors.

 

[muff-in]

Also meine Frage war, was ich anstelle dem int in der Methode rekursion0 eingeben müsste, damit sie funktioniert.
Das int vor dem Methodennamen ist ja der Rückgabewert, was die Methode zum Schluss rausgibt.
Wie müsste ich das int ersetzen, damit meine Rekursive Methode funktionert, also sozusagen den Befehl sich selbst wieder aufzurufen als Rückgabewert hat?

 

[Firephoenix]

public rekusion1() {
        rekursion0(3);
    }

Ist aber ziemlich sinnfrei, damit produzierst du einen int ohne irgendwas damit zu machen.

Die Stackoverflow kommen dadurch zustande, dass dein programm nie terminiert, es wird ein Aufruf auf den nächsten gepackt bis der Stack platzt.

Für x = 1 gibst du 1 aus, und für x >= 1 (warum eigentlich >= , erklär mir mal wie x an der stelle 1 sein kann?) rufst du die Funktion mit x = (x - 1) + 2 * x - 1 wieder auf mit den gleichen Regeln.
Für negative x packst du das x gerade wieder in die Funktion.

Also gilt:
für x = 1 ist deine Funktion 1
Für alle x <= 0 hast du eine schicke endlosschleife
und für alle x > 1 wird x immer größer, irgendwann läuft die variable über und du landest im endlosfall für negative werte (hier mal die ersten Aufrufe):
1. Aufruf, x = 3
2. Aufruf, x = 7
3. Aufruf, x = 19
4. Aufruf, x = 55
5. Aufruf, x = 163
6. Aufruf, x = 487
7. Aufruf, x = 1459
8. Aufruf, x = 4375
9. Aufruf, x = 13123
10. Aufruf, x = 39367
usw.

Vielleicht erklärst du einfach mal was du machen willst das ist vielleicht einfacher.
Gruß

 

[JCODA]

(x - 1) + 2 * x - 1 das ist das gleiche wie 3*x -2, sicher, dass die Formel richtig ist?

achja: 3*x-2 gibt bei x = 3, 3*3-2 = 7 aus, und die folge ist monoton steigend, also würde am ende sowas wie unendlich rauskommen, also fehlt dir eine sinnvolle Abbruchbedingung.

 

[Fant]

Verrate du doch zunächst mal, was du da überhaupt berechnen willst.

Das "int" ist nicht das Problem, sondern viel mehr die Tatsache, dass du da einfach Blödsinn berechnest.
Für x=1 gibst du sofort 1 zurück und in (vermutlich fast) allen anderen Fällen rutscht du in eine "Endlosschleife".

 

[muff-in]

Also, das was ich eigentlich machen wollte, war diese Aufgabe aus de Seite:
Java-Programmieraufgaben - Rekursion

[...]
Rekursive Funktion implementieren

Schwierigkeit 2

Gegeben sei folgende rekursiv definierte Funktion f:

f(n) := 1, für n = 1
f(n) := f(n-1) + 2n - 1, für n > 1
Implementieren Sie eine rekursive Java-Methode, die f(n) berechnet (ohne Iterationen).

Um welche Form von Rekursion handelt es sich?
[...]

Da ist auch die Lösung, aber ich wollte es selber ausprobieren, deswegen hab ich noch nicht nachgeschaut. -.-

Bis jetzt siehst so aus (mit ganz vielen StackOverFlowErrors), aber ich arbeite ja noch dran

public class rekusion1 {

	public rekusion1() {
		rekursion0(3);
	}

	public int rekursion0(int x) {

		if (x == 1) {
			return 1;
		} else if (x > 1) {
			return rekursion0(x - 1) + 2 * x - 1;
		} else {
			return rekursion0(x);
		}
	}
}

 

[muff-in]

Okay ich gestehe das mit >= und der falschen implementierung der Formel, waren Leichtsinnkeitsfehler.
Tut mir leid wegen der Aufruhe.

 

[muff-in]

Hey, ich habs glaub ich.

Also in BlueJ klappt das. (In Eclipse noch nicht)

public class rekusion1 {

    public rekusion1(int x) {
        rekursion0(x);
    }

    public int rekursion0(int x) {

        if (x == 1) {
            return 1;
        } else if (x > 1) {
            return rekursion0(x - 1) + 2 * x - 1;
        } else {
            return rekursion0(x);
        }
    }
}

Edit: Naja es gibt wenigstens keine Fehlermeldungen.

 

[Fant]

Du hast da immer noch ne Endlosschleife für negative x-Werte drin. pack in den letzten else-Block einfach ein return -1 oder so rein. Abgesehen davon sollte deine Methode jetzt aber das berechnen, was sie berechnen soll.

 

[Firephoenix]

Hier wäre noch eine Möglichkeit mit Exception, für den nicht-definierten Bereich passt das denke ich etwas besser als sich die Funktion dafür "umzudefinieren"

public static int rekursion0(int x) {
    	if(x < 1){
    		throw new IllegalArgumentException("Funktion ist nur für x >= 1 definiert");
    	}
        if (x == 1) {
            return 1;
        } else{
            return rekursion0(x - 1) + 2 * x - 1;
        }
    }

Was die Funktion berechnet ist aber auch interessant (vorsicht, evtl Spoiler ^^)
f(x) = x*x = (x-1)*x+x = (x-1)*(x-1)+x+x-y = (x-1)*(x-1)+2 * x - 1 = f(x-1) + 2*x-1