Frage zur Rekursion

[anno]

Hallo Forum,

[Java]
public static int func_p (int n)
{
if (n==0)
return 0;
else
return n-1;
}

public static int func_s(int m, int n)
{
if(n==0)
return m;
else
return func_p(func_s(m,n-1));
}
[/Java]

Unzwar soll ich die Funktionswerte jeweils rekursiv entsprechend der obigen Methoden berechnen.
Für:

func_s(7,2) und func_s(5,4)


Nun hab ich es versucht zu lösen (Bild 0562) und dann habe ich noch eine Lösung vom Kollegen (Bild 0563). Nun weiß ich nicht wie er zum Beispiel in Aufgabe 1 auf die Werte 6 und 5 kommt (Er ist im Urlaub daher kann ich ihn schlecht fragen).
Könntet Ihr mir bitte helfen?
danke

 

[kaoZ]

Um Rekursion zu verstehen , musst du zunächst die Rekursion verstehen :lol:


Das Ergebnis der ersten Aufgabe ist , insofern deine Methoden oben korrekt sind 7, da sich der Wert von m nie verändert, da er lediglich als Eingabeparameter für deine Methode dient, das ganze wird 2 mal ausgeführt, da die Bedingung erfüllt ist wenn n (2) == 0 ist.

Die Zweite Aufgabe ergibt ebenfalls 5 , da auch hier unter Verwendung deiner oben angegebenen Methoden der Wert von m nie verändert oder in die Berechnung mit einbezogen wird.

Sinnig wäre m um eben die Anzahl an benötigten Durchläufen zu dekrementieren.

Zudem ist die Ersten Methode nicht rekursiv, da sie sich nicht selbst aufruft.

Das ist quasi das was du da programmiert hast, insofer der Code nicht aus irgendwelchen Büchern stammt.

	public static int methode1(int n){
		return n != 0 ? --n : 0;
	}
	
	public static int methode2(int m, int n){
		if(n == 0 ) {
			return m;
		}
		else{
			System.out.println(n);
			return methode2(m,Foo.methode1(n));
		}
	}

m ändert sich hier ebenfalls nie..... ich hab mal ein sysout eingebaut, damit du sehen kannst das sich zwar n verändert aber du m nicht mit in die Rechnung einbeziehst.

Nun meine 'vorsichtige' Frage, hast du nicht eher versucht diese "Funktion" auf eine Methode abzubilden und dabei ist obiger, augenscheinlicher falscher Code bei entstanden, oder liege ich nun völlig daneben und hab was übersehen ?

 

[anno]

Die Aufgabe stammt aus einer Klausur. Mich hat die Lösung vom Kollegen verwirrt. Ich weiß das die 7 sich nie ändert. Es ändert sich immer das n. Ist die lösung vom Kollegen falsch? Ich habe mir gedacht das er davon ausgegangen ist das in der ersten Methode er anstatt n m benutzt hat.

 

[kaoZ]

Also wenn du nun nur den Rechenweg aufschreiben sollst, ist dieser relativ einfach nachzuvollziehen, da wie gesagt n die einzige Variable ist die ihren Wert ändert, dennoch hat m immer den gleichen Wert wie schon beim Übergabe an die Methode, sprich

er hat 'vermutlich' einfach nicht gesehen das n, die Abbruchbedingung ist und nicht m, und es somit den Wert von m notiert, und nicht den Wert den er hätte eigentlich notieren müssen (n), meine ich zumindest, anders würde es ja eigentlich auch keinen Sinn machen, da wie gesagt sich m hier ( laut der Methoden) ja nie verändert.

Ansonsten poste die Aufgabe doch mal ins Matheforum , da sind teilweise einige cracks unterwegs

 

[stg]

Da muss ich kaoz widersprechen, die Lösung von deinem Freund ist richtig!

Das Ergebnis von der ersten Aufgabe ist 5, von der zweiten Aufgabe 1. Berechnet und ausgegeben wird die Differenz von m und n, sofern m größer als n ist.

also

func_s(7,2) = 7-2 = 5
func_s(5,4) = 5-4 = 1

 

[stg]

Ein bisschen ausführlicher für den ersten Fall.

Du startest mit:

    func_s(7,2)

Zurückgegeben wird:

    func_p(func_s(7,1))

Nun wird "von innen nach außen", also zunächst der
Ausdruck func_s(7,1) ausgewertet. Daher kommen wir zu

    func_p(func_p(func_s(7,0))

Nun gibt func_s den Wert 7 zurück und wir haben:

    func_p(func_p(7))

Für 7 gibt func_p nun den Wert 6 zurück, also:

    func_p(6)

Und schließlich erhalten wir:

    5

 

[kaoZ]

bist du von den Aufgaben auf dem Papier ausgegangen oder von dem oben geposteten Code, macht natürlich sinn das man keine Methode erstellt die eigentlich keine funktion hat ^^

Mein Grundgedanke war ja das dort die Differenz rekursiv errechnet werden soll.

show me the light plz, vielleicht hab ichs auch einfach nur übersehen.

 

[stg]

@kaoZ:
Meine Antwort bezieht sich auf den im Startbeitrag geposteten Quellcode.

 

[kaoZ]

Jep, hast recht ich hätte es gleich mal richtig aufräumen sollen.............

public class Foo{
	public static int func_p (int n){
		return n == 0 ? 0 : n-1;
	}
	 
	public static int func_s(int m, int n){
		return n == 0 ? m : func_p(func_s(m, n-1));
	}
	
	public static void main(String[] args){
		System.out.println(Foo.func_s(7,2));
	}
}

Gibt die Differenz aus.

Antworten sind zu

1 = 5

2 = 1

ich hatte hier beim umschreiben übersehen

public static int methode2(int m, int n){
		if(n == 0 ) {
			return m;
		}
		else{
			System.out.println(n);
			return methode2(m,Foo.methode1(n));

das nicht methode2 sondern methode1 mit Rückgabwert von Methode2 ausgeführt wird.

Mein Fehler


kleiner Tip @TO :

verwenden braces

{}

dann kann man das auch gleich vernünftig lesen