Beispiele für Rekursion

D

digitalspecht

Mitglied
Hallo Leutz,

habe da mal eine Frage: Wo finde ich Beispiele, wo Rekursion angewandt wird. Also bis jetzt habe ich das Beispiel mit dem Turm von Hanoi und die Fibonacci-Zahl und die Fakultät.

Wo kann man das noch anwenden und wenn ja, wo gibt es den entsprechenden Quelltext?

Viele Grüße und Danke im Vorraus,
der Digi
 
Beim Auslesen von Baumstrukturen (z.B. XML) würde sowas Sinn machen. Quellcode hab ich jetzt nich da. :D
 
Noch eine Baumstruktur:
Ordner samt Unterordner auf der Festplatte auslesen. Sorry, aber ein Code-Beispiel habe ich auch gerade nicht parat.

Computergegner in Spielen, wie TicTacToe, Dame oder gar Schach können rekursiv arbeiten, indem Sie den Zug des Gegners mit der selben Funktion berechnen, wie sie ihren eigenen berechnen und dann wieder ihren nächsten eigenen und den übernächsten des Gegners usw. um den Spielverlauf vorauszuahnen. Bei Schach benötigt das aber Abbruchkriterien und dann nennt man das meines Wissens nicht mehr Rekursion, sondern irgendwie anders, aber ich komme grad nicht auf den Namen.
 
Für ne Rekursion brauch man doch immer ein Abbruchkriterium, oder?

quasi so:
Code: 
 public void doSth(int i) {
  if(i <=1) {
 //irgendwas
 } else {
 doSth(i--);
 }
 }

Richtig? Oder ist meine Sicht wieder viel zu beschränkt? (Wäre ja nix neues :-( )
 
Hi

Nicht jede Rekursion braucht ein Abbruchkriterium aber die meisten schon dein Beispiel ist richtig.

Weiter Rekursionsanwendugen wären noch:

Priemzahlensieb (Endlosrekursion oder nur bis zu einer zahl n)
Backtracking
und soweit ich weiß ist jede For - bzw. While - Schleife als Rekursion möglich jedoch andersrum gehts nicht immer.

mfg 4men
 
Hi

Code: 
public class Priemzahlensieb
{
private static Naturals normal;
 
public static void main (String args[])
{
normal = new Naturals(0, 100);
System.out.println(normal.getNext());
priemZahlenSieb(normal.getNext());
}
 
private static void priemZahlenSieb(int next)
{
System.out.println(next);
normal = new Multi(normal, next);
priemZahlenSieb(normal.getNext());
}
 
static class Naturals
{
private int count;
private int stop;
Naturals ident;
 
Naturals()
{
this(0);
}
 
Naturals(int start)
{
this(start,Integer.MAX_VALUE);
}
 
Naturals(int start, int ende)
{
count = start;
stop = ende;
}
 
Naturals(Naturals input)
{
ident = input;
}
 
int getNext()
{
count++;
if(count == stop)
	System.exit(0);
return count;
}
}
static class Multi extends Naturals
{
int filter;
 
Multi(int raus)
{
super();
filter = raus;
}
 
Multi(int start, int raus)
{
super(start);
filter = raus;
}
 
Multi(Naturals input, int raus)
{
super(input);
filter = raus;
}
 
int getNext()
{
int next = ident.getNext();
if(next%filter == 0)
	next = ident.getNext();
return next;
}
} 
}

Zu Backtracking gibts ein ganz bekanntes Problem dazu:

Du hast ein n auf n Feld und musst n Damen so positionieren das sie sich nicht schlagen können. Backtracking versucht nun jede Möglichkeit wie die Damen stehen könnten und sobald er eine Lösung hat beendet er die Rekursion.

mfg 4men
 
Danke, Backtracking war das Wort, das mir fehlte.
Backtracking ist eine Rekursion, die nicht alle Möglichkeiten des Problems testet, sondern sich mit einer bestimmten Lösung, also z.B. der ersten zulässigen Lösung (erste Lösung des Dameproblems) oder einer Lösung, die ein bestimmtes Lösungsniveau erreicht oder einfach nach einer bestimmten Tiefe (z.B. ein Computergegner testet alle Möglichkeiten der nächsten fünf Züge) oder, wenn eine Unzulässigkeit unvermeidbar ist, zufrieden gibt.
Eine "reine" Rekursion läuft bis zu den Blättern des Baumes, z.B. alle Unterordner auslesen oder alle möglichen folgenden Spielzüge probieren (bei TicTacToe kein Problem, aber bei Schach dauert es wohl zu lange).
Man kann z.B. das Dameproblem auch mit einer Rekursion lösen, dann kann man alle Lösungen ermitteln. Allerdings ist in diesem Fall Backtracking auch sinnvoller, da man einen Versuch, der Rechenzeit wegen, besser bei der ersten Bedrohung abbricht.

Gruß hpvw
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück