Informatiker Board | Druckvorschau: Ablauf einer Rekursiven Funktion

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Ablauf einer Rekursiven Funktion (http://www.informatikerboard.de/board/thread.php?threadid=2162)

Geschrieben von Tina92 am 11.03.2015 um 17:16:

Ablauf einer Rekursiven Funktion

Meine Frage:
Hi Leute,

ich hätte mal eine Frage zu den rekursiven Funktionen und wie diese eigentlich genau funktionieren.

Hab als Beispiel einmal die Fakultätsfunktion geschrieben:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:


public class Fakult 
{
	public static void main (String[]args)
	{
		System.out.println(fakult(6)); 
	}

public static double fakult (int zahl)
	{
		if (zahl>0)
		{
			return zahl*fakult(zahl-1);
		}
		else
		{
			return  {1; 
		}
	}
}

Meine Ideen:
Was ich jetzt nicht verstehe, was genau in dieser Zeile passiert:

return zahl*fakult(zahl-1);

Vielen Dank für Eure Hilfe :-)

Geschrieben von eulerscheZahl am 11.03.2015 um 17:33:

Das Programm springt immer wieder in eine Unterfunktion.
Ich habe mal ein paar Kontrollausgaben ergänzt:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:

public static double fakult(int zahl) {
	if (zahl > 0) {
		System.out.println("      ".substring(zahl) + zahl
				+ " vor rekursivem Aufruf");
		double ergebnis = zahl * fakult(zahl - 1);
		System.out.println("      ".substring(zahl) + zahl
				+ " nach rekursivem Aufruf");
		return ergebnis;
	} else {
		return 1;
	}
}



6 vor rekursivem Aufruf
 5 vor rekursivem Aufruf
  4 vor rekursivem Aufruf
   3 vor rekursivem Aufruf
    2 vor rekursivem Aufruf
     1 vor rekursivem Aufruf
     1 nach rekursivem Aufruf
    2 nach rekursivem Aufruf
   3 nach rekursivem Aufruf
  4 nach rekursivem Aufruf
 5 nach rekursivem Aufruf
6 nach rekursivem Aufruf

Das ist der zeitliche Ablauf: die Funktion ruft sich selbst auf, wartet auch ein Ergebnis der Unterfunktion und gibt dieses dann zurück.

Geschrieben von Tina92 am 14.03.2015 um 11:04:

Vielen Dank für deine Antwort.

Geschrieben von Tina92 am 05.04.2015 um 19:37:

Hey :-)

Ich muss das Thema leider noch einmal aufgreifen, da ich nicht weiterkomme.

Den folgenden Code habe ich soeben mal schnell geschrieben:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

public class Rekursiv 
{
	public static void main (String[]args)
	{
	System.out.println(versuch(3));	
	}

	public static int versuch(int zahl)
	{
		int ausgabe = 1;
		if (zahl>0)
		{
			ausgabe = 2+zahl*versuch(zahl-1);	
		}
		else
		{
			return 1;
		}
		return ausgabe; 
	}
}

Könnt ihr mir bitte sagen, wie jetzt hier als Ergebnis 26 rauskommt?

Vielen Dank

Geschrieben von eulerscheZahl am 05.04.2015 um 20:12:

Für zahl = 3 ist das Ergebnis: 2 + 3 * versuch(2)
versuch(2) ist 2 + 2 * versuch(1)
versuch(1) ist 2 + 1 * versuch(0)
versuch(0) ist 1, das Ergebnis eingesetzt ergibt versuch(1) = 2+1*1 = 3
versuch(2) = 2+2*3 = 8
versuch(3) = 2+3*8 = 26

Geschrieben von Tina92 am 05.04.2015 um 21:22:

Vielen Dank für deine Antwort :-)

Geschrieben von Michael90 am 06.04.2015 um 13:12:

Zu diesem Thema hätte ich auch eine Frage:

Warum wird a am Ende wieder positiv und nicht negativ, also -1,-2,-3,-4 ?

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

public class Rekursiv
{
	public static void main(String[] args)
	{
		rekursion(5);
	}
    private static void rekursion(int a)
    {
      	--a;
      	System.out.println(a);
    	if (a!=0) 
    	{
    		rekursion(a);
      	}
    	System.out.println(a); 
    	// Wenn a = 0, dann erfolgt hier die Ausgabe des Wertes 
    	// a wird um eins verringert, somit auf -1,
    	// Warum wird a hier wieder positiv und nicht negativ, also -1,-2,-3,-4 ? 
	}
}

Geschrieben von eulerscheZahl am 06.04.2015 um 13:25:

Du gibst am Ende wider das a der aufrufenden Funktion aus.
rekursion(3) setzt a auf 2, gibt eine 2 aus, ruft rekursion(2) auf (Ausgabe: 1 0 0 1) und gibt die 2 dann erneut aus.

Geschrieben von Michael90 am 12.04.2015 um 12:19:

Danke dir für die Antwort. Also verstehe ich das richtig, dass es folgendermaßen abläuft, dass erst (angenommener Wert = 3) von 3,2,1,0 abläuft und dann wieder 1,2,3 zurückläuft?

Geschrieben von eulerscheZahl am 12.04.2015 um 18:10:

Die Funktion springt in eine Unterfunktion (in dem Fall in sich selbst) rein und arbeitet diese ab. Danach führt sie sich selbst weiter aus. Wie Klammern, die sich gegenseitig umschließen: {[()]}
Und sowohl bei der öffnenden, als auch bei der schließenden Klammer hast du eine Ausgabe.