Frage zu einer rekursiven Funktion

[starbug08]

hallo allerseits, habe eine neue aufgabe, die wie folgt lautet:

F(1) = 12
F(2) = 19
F(n+2) = F(n+1) + F(n)

hierfür soll ich eine rekursive methode schreiben, allerdings bekomme ich dann immer eine stackoverflow exception, was eigentlich ja auch klar ist da sich die werte ja nicht verringern oder???

hier noch mal mein code dazu.

ublic class Funktion {
	
	
	public int funk(int n)
	{
		int erg = 0;
		
		
		if(n==1)
		{
			erg = 12;
			
		}else if (n==2)
		{
			erg = 19;
			
		}else{
			
			erg  = funk(n+1) + funk(n); 
		}
		
		System.out.println(erg);
		return erg;
			
	}
	
	public static void main(String[] args)
	{
		
		
		Funktion f = new Funktion();
		f.funk(3);
		
	}

}

bin für jede antwort dankbar

 

[Andi_CH]

Die gute Nachricht: Du hast perfekt nach der Vorgabe implementiert
Aber ......
:shock:

F(n+2) = F(n+1) + F(n)

hierfür soll ich eine rekursive methode schreiben, allerdings bekomme ich dann immer eine stackoverflow exception, was eigentlich ja auch klar ist da sich die werte ja nicht verringern oder???

Der Fehler liegt, wie du richtig erkennst, schon hier.
Der Rekursive Aufruf mit n+1 führt ja zu immer grösseren Werten und kommt niemals auf 1 oder 2 runter.

Ich vermute es müsste
F(n+2) = F(n-1) + F(n)

heissen, wobei ich mir mit
F(n+2) auch nicht sooooo sicher bin. IMHO müsste das F(n+1) heissen ....

 

[darekkay]

Die Formel lautet:
F(n+2) = F(n+1) + F(n)

Deine Funktion sieht aber so aus:
funk(n) = funk(n+1) + funk(n)

Siehst du, wo das Problem ist?

Anstatt mit "+" musst du mit "-" arbeiten:
funk(n) = f(n-1) + f(n-2)

@Andi: nö, die Formel ist doof geschrieben, aber meiner Meinung nach richtig. f(1) = 12, f(2) = 19, f(1+2) = f(1+1) + f(1) = f(2) + f(1) = 12 + 19 = 31

 

[bygones]

korrekt heißts doch eigentlich
f(0)=x
f(1)=y
f(n)=f(n-1)+f(n-2)

somit läuft man nicht gefahr mit dem parameter n schindluder zu treiben

 

[MQue]

Ich hab mir jetzt die Formel nicht angesehen aber Grundsätzlich zu den Rekursionen,
du brauchst eine Abbruchbedingung, ich hab das jetzt mal für bare Münze genommen, was du da hingeschrieben hast und dann schauts so aus:

package classpathtest;

public class Funktion {

   private int erg;

    public int funk(int n) {
        if(n==1) {
            erg = 12;
            }
        else if (n==2) {
            erg = 19;
            }
        else {
            if(n > 10)   // Abbruchbedingung
                return erg;
            else
                return erg = erg + 1 + funk(n+1);  // da musst du eben was machen mit den einzelnen Rekursionen
            }
        return -1;
        }

    public static void main(String[] args) {
        Funktion f = new Funktion();
        int erg1 = f.funk(3);
        System.out.println("Das ist das Ergebnis: " + erg1);
        }
}

 

[Landei]

Um Rekursion zu vertehen, hier klicken!

 

[starbug08]

danke für die schnellen antworten, ich denke aber auch mal das die aufgabe wohl falsch gestellt ist, hmm das werd ich dann wohl erst morgen sehen

 

[Andi_CH]

So bricht die Rekursion sauber ab, aber das ist die Formel

f(n) = f(n-1)+f(n-2)

Kannst ja mit dem Debugger oder sysouts verfolgen was so passiert ....

public class Rekursion {

	public int funk(int n) {
		int erg;
		if(n==1) {
			erg = 12;
		} else if (n==2) {
			erg = 19;
		} else {
			erg = funk(n-1) + funk(n-2);
		}
		return erg;
	}

	public static void main(String[] args) {
		int erg = 0;
		Rekursion f = new Rekursion();
		for (int i=1; i<5; i++) {
			erg = f.funk(i);
			System.out.println("Das ist das Ergebnis von f("+i+") = " + erg);
		}
	}
}

 

[starbug08]

hallo leute ich habe eine neue aufgabe für eine rekursive funktion bekommen. meine idee wäre eine liste oder array oder sowas aber das soll man wohl nicht verwenden. wäre super wenn mir einer einen tip geben kann. hier mal die aufgabe:

Schreiben Sie eine Java-Methode, die bei einem gegebenen String s (z.B.: "abc") den String zurückgibt, der entsteht, wenn jeder Buchstabe in s verdoppelt wird ("aabbcc"). Nutzen Sie den rekursiven Problemlösungsansatz und implementieren Sie eine rekursive Java-Methode. Hinweis: Die Klasse String kennt die Methoden: char charAt(int index) String subString(int i)).// liefert den Teilstring ab Position i einschließlich int length()
Seite

 

[Andi_CH]

private String doIt ( String str) {
    String resultat = "";
    resultat = ersterChar + ersterChar;
    if (str.length()==1)
        return resultat;
    resultat += doIt(Substring von 1..ende);
}

Viel Vergnügen

It's untested !!!

 

[starbug08]

hallo leute ich hab mal wieder ne tolle aufgabe bekommen aber leider funzt das nich so wie es soll. hier mal die aufgabe:

Für 0 gilt: länge(0) = 1189 mm
breite(0) = 841 mm
für alle n > 0 gilt: länge(n) = breite(n-1)
breite(n)= ½ * länge(n-1)
a) Berechnen Sie die länge(5)
b) Berechnen Sie die länge(4)
c) Schreiben Sie eine rekursive Methode, für die Länge eines beliebigen
Formates.
Hinweis:
Es gilt: länge(n) = breite(n-1) = ½ * länge(n-2).

und hier ist meine lösung:

public int laenge(int n)
{
    int laenge = 0;
    int breite = 0;
    
    if(n==0)
    {
        laenge = 1189;
        breite = 841;
        
    } else { laenge = 1/2*laenge(n-2);
    
    }
      return laenge;   
}

ich bekomme da aber immer einen stackoverflow error und ich weiss nich genau warum. wäre super wenn ihr mir helfen könnt

 

[timbeau]

Immer "int länge = 0" zu setzen dürfte der Fehler in der Überlegung sein.

 

[SlaterB]

hast du eine ungefähre Vorstellung, was das Programm leisten soll, dass aus 1189 dann ein Aufruf mit 1187, 1185 usw. kommt?
dann schaue dir doch ganz einfach mit System.out.println()-Ausgaben oder Debugger ein, was letzlich alles passiert,
besonders beim spannenden vermeintlichen Ende der Rekursion (bzw. bei dir ja gerade nicht)

natürlich kann dir fast jeder hier gleich die Lösung sagen (edit: ok, timbeau ausgenommen hinsichtlich dem Error ),
aber wäre es nicht spannender, das selber herauszufinden?

wenn du zu viele Ausgaben auf einmal erhälst, dann fange mit kleinen Zahlen wie 5 oder 10 an
(edit: 5 und 4 stehen ja auch in der Aufgabe, die 1100 habe ich halb selbst hineininterpretiert),
baue einen Test ein dass nach maximal 10 Durchläufen oder bei n < -100 in jedem Fall alles abgebrochen wird,
oder verwende Thread.sleep() zum verlangsamen, das ist aber schon bisschen schwieriger einzusetzen mit try/catch

 

[timbeau]

Es kommt kein Aufruf mit 1187 usw.

Jeder Aufruf bis auf den mit n=0 wird Länge auf 0 gesetzt und returned.

Da auch jedes laenge(n-2) 0 sein wird bleibts dabei.

Gegen"beweise" nehme ich gerne zur Kentniss.

 

[SlaterB]

der auftretende 'stackoverflow error' ist doch Beweis genug,
na jedenfalls war hier meine anvisierte Lösung, dass bei n ungerade die 0 übersprungen wird 5, 3, 1, -1, -3, ..

 

[Gonzo17]

Ja, die 0 wird übersprungen, da immer in Zweier-Schritten aufgerufen wird. Das lässt sich vermeiden, indem man nicht nur eine Abfrage if(n==0), sondern auch noch eine Abfrage if(n==1) dahinter stellt. Denn die Länge für laenge(1) wissen wir ja per Definition auch, wenn man mal scharf hinschaut.

 

[timbeau]

Ist Beweis wofür?

Das das Programm bei n % 2 = 1 nicht abbricht ok.

Das es bei n%2=0 was sinnvolles macht nicht.

 

[Gonzo17]

Dafür, dass das Programm so nicht korrekt ist.

Das Initialisieren der Variable laenge hat doch garkeine Auswirkung. Wieso sollte es auch? Beim rekursiven Aufruf der Methode wird ja nicht die selbe Variable verwendet, es wird eine neue lokale Variable angelegt.

Das Problem, weshalb das Programm nicht endet, liegt vor allem erstmal im "Überspringen" der 0 bei ungeraden Werten von n, weil das Abbruchkriterium nicht greift. Da muss als zusätzliches Abbruchkriterium einfach if(n==1) hinzugefügt werden.

Edit: Ist übrigens noch ein kleiner Fehler drin. Der Aufruf 1 / 2 * laenge(n-2) wird dir immer 0 liefern. Das liegt daran, dass das laut Rechenvorschriften gelesen wird wie 1 / (2*laenge(n-2)), was wiederrum bedeutet, dass da ein kleiner Wert herauskommt. Da du hier mit int arbeitest, das nur ganze Werte kennt, nehmen ich an, dass gerundet oder abgeschnitten wird, also vermutlich wird da am Ende immer 0 stehen. Von daher, "einfacher" denken und laenge(n-2) / 2 schreiben.

 

[xehpuk]

Edit: Ist übrigens noch ein kleiner Fehler drin. Der Aufruf 1 / 2 * laenge(n-2) wird dir immer 0 liefern. Das liegt daran, dass das laut Rechenvorschriften gelesen wird wie 1 / (2*laenge(n-2)), was wiederrum bedeutet, dass da ein kleiner Wert herauskommt. Da du hier mit int arbeitest, das nur ganze Werte kennt, nehmen ich an, dass gerundet oder abgeschnitten wird, also vermutlich wird da am Ende immer 0 stehen. Von daher, "einfacher" denken und laenge(n-2) / 2 schreiben.

Dass dort immer 0 rauskommt, ist richtig, der von dir genannte Grund aber falsch (woher kommt diese Rechenvorschrift?). Das Problem ist, dass

1 / 2 == 0

wegen

int

.

 

[Gonzo17]

Dass dort immer 0 rauskommt, ist richtig, der von dir genannte Grund aber falsch (woher kommt diese Rechenvorschrift?). Das Problem ist, dass

1 / 2 == 0

wegen

int

.

:rtfm:

Da magst du Recht haben. Dachte wohl, dass ein * stärker bindet als ein /. Hab ich nicht richtig nachgedacht. Natürlich ist es nicht so und du hast Recht mit deiner Erklärung. Aber dass es wohl was mit int ist, das war auch mein Gedanke.

 

[timbeau]

Ich danke übrigens allen Beteiligten, mir wurden die Augen geöffnet.

 

[starbug08]

hi leutz, schon wieder hab ich ne rekursive funktion. und zwar soll eine methode die einen String parameter bekommt, diesen rückwärts wieder ausgeben, also abc = cba halt. hier ist meine lösung aberleider bekomm ich immer nur das c ausgegben und da wollte ich mal fragen was ihr von der methode haltet

public String rev(String s)
{

    String neu = "";
    if(s.length()>0)
    {
        neu = s.charAt(s.length()-1) + rev(neu);

    }
    return neu;
}

 

[SlaterB]

ich halte von der Methode nicht viel,

der Fehler dürfte klar sein, oder?
ansonsten Logging einbauen

 

[timbeau]

Versuchs mal mit einem externen Stringbuffer der den letzten Char speichert. Ist auch keine perfekte Methode aber klappt zumindest.

 

[starbug08]

den fehler seh ich leider so auch nicht aber ich denke mal es geht deshalb nicht weil "neu" ja nur c übergeben bekommt und leider heist es in der aufgabe weiter das man nur charAt() und length() benutzen darf.

 

[SlaterB]

du musst einen Index als rekursiven Parameter herumreichen und dazu s, nicht neu

 

[timbeau]

Statt length-1 ein length-n und der Methode auch immer einen kleineren String übergeben.

Bsp:
Hall(o)
Hal(l)
Ha(l)
H(a)
(H)

 

[JohannisderKaeufer]

Wenn der übergebene String die länge 1 hat ist das ganze trivial.

public String rev(String s){
  if(s.length == 1){
    return s;
  }
}

Besser ist allerdings wenn der übergebene die länge 1 oder weniger hat.
Dann ist das ganze immer noch trivial

public String rev(String s){
  if(s.length <= 1){
    return s;
  }
}

Jetzt fehlt nur noch die funktionalität die den String kleinhaut und weiterverteilt, fals das ganze größer als 1 ist.

public String rev(String s){
  if(s.length <= 1){
    return s;
  }
  int mitte = s.lenght/2;
  String anfang = s.substring(0,mitte);
  String ende = s.substring(mitte);
  
  return rev(ende)+rev(anfang);
}

 

[SlaterB]

zum Glück ist substring nicht erlaubt, nun genug vorgesagt