q1:java-rekursion

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
Nächste Überarbeitung		 Vorhergehende Überarbeitung
q1:java-rekursion [2017/07/11 09:28] – admin03q1:java-rekursion [2017/12/04 08:51] (aktuell) – admin03
Zeile 1: Zeile 1:
 In Kapitel 9 wurde die Berechnung der Fakultät als Beispiel für die Einführung von Methoden benutzt. Die eigentliche Berechnung erfolgte damals mit Hilfe einer Schleife. Die Berechnung der Fakultät lässt sich jedoch auch anders auffassen: Fakultät von 20 ist nichts anderes als 20- mal Fakultät von 19, Fakultät von 19 ist 19-mal Fakultät von 18, usw. Eine solche Definition setzt allerdings voraus, dass man mindestens einen konkreten Wert der Fakultät kennt (z.B. ist 1!=1). Zusammengefasst mit der Abkürzung fak für Fakultät gilt also In Kapitel 9 wurde die Berechnung der Fakultät als Beispiel für die Einführung von Methoden benutzt. Die eigentliche Berechnung erfolgte damals mit Hilfe einer Schleife. Die Berechnung der Fakultät lässt sich jedoch auch anders auffassen: Fakultät von 20 ist nichts anderes als 20- mal Fakultät von 19, Fakultät von 19 ist 19-mal Fakultät von 18, usw. Eine solche Definition setzt allerdings voraus, dass man mindestens einen konkreten Wert der Fakultät kennt (z.B. ist 1!=1). Zusammengefasst mit der Abkürzung fak für Fakultät gilt also
- +$$fak(n)=n\cdot fak(n-1)$$ und $$fak(1)=1.$$
-$$fak(n)=n\cdot fak(n-1) und fak(1)=1.$$+
  
 Eine solche Definition einer Funktion bezeichnet man als rekursiv („rückbezüglich“). Viele Programmiersprachen erlauben die unmittelbare Umsetzung einer solchen Funktionsdefinition. Bei speziellen Sprachen wie PROLOG gibt es überhaupt keine Schleifen, diese müssen dann immer durch rekursive Funktionen nachgebildet werden. Eine solche Definition einer Funktion bezeichnet man als rekursiv („rückbezüglich“). Viele Programmiersprachen erlauben die unmittelbare Umsetzung einer solchen Funktionsdefinition. Bei speziellen Sprachen wie PROLOG gibt es überhaupt keine Schleifen, diese müssen dann immer durch rekursive Funktionen nachgebildet werden.
Zeile 47: Zeile 46:
  
  
-{{ :q1:fakultaetablauf.jpg?direct&400 |}}+{{ :q1:fakultaetablauf.jpg?direct&300 |}}
  
 Als komplexeres Problem sollen die sog. „Kinderkreise“ betrachtet werden. Jeder Kreis hat dabei links und rechts zwei Kinder, diese haben wiederum Kinder, usw. Wenn eine gewisse Größe unterschritten wird, gibt es keine Kinder mehr: Als komplexeres Problem sollen die sog. „Kinderkreise“ betrachtet werden. Jeder Kreis hat dabei links und rechts zwei Kinder, diese haben wiederum Kinder, usw. Wenn eine gewisse Größe unterschritten wird, gibt es keine Kinder mehr:
  
-{{ :q1:kinderkreise.png?direct&400 |}}+{{ :q1:kinderkreise.png?direct&600 |}}
  
 Diese Grafik soll mit einer rekursiven Methode erstellt werden.  Diese Grafik soll mit einer rekursiven Methode erstellt werden. 
Zeile 158: Zeile 157:
 Erstelle ein Java-Programm, das die n-te Fibonaccizahl rekursiv berechnet. Schreibe zur Übung auch ein Programm, das klassisch mit einer Schleife rechnet. Ein interessanter Test zeigt, dass schon fibo(50), rekursiv berechnet, eine sehr lange Rechenzeit braucht, während dieselbe Zahl iterativ berechnet praktisch sofort erscheint. Erkläre dieses Phänomen! Erstelle ein Java-Programm, das die n-te Fibonaccizahl rekursiv berechnet. Schreibe zur Übung auch ein Programm, das klassisch mit einer Schleife rechnet. Ein interessanter Test zeigt, dass schon fibo(50), rekursiv berechnet, eine sehr lange Rechenzeit braucht, während dieselbe Zahl iterativ berechnet praktisch sofort erscheint. Erkläre dieses Phänomen!
  
-==== Aufgabe 4====+===== Aufgabe 4=====
 Erkläre die Funktionsweise des folgenden Konsolen-Programms: Erkläre die Funktionsweise des folgenden Konsolen-Programms:
 <code JAVA> <code JAVA>
Zeile 175: Zeile 174:
 } }
 </code> </code>
-==== Aufgabe 5 ====+===== Aufgabe 5 =====
 Welche Ausgabe erzeugt folgende Methode, wenn man sie mit p(5) aufruft? Welche Ausgabe erzeugt folgende Methode, wenn man sie mit p(5) aufruft?
 <code JAVA> <code JAVA>
Zeile 190: Zeile 189:
   }   }
 </code> </code>
-==== Aufgabe 6 ====+===== Aufgabe 6 =====
 Der Turm von Hanoi ist ein Denkspiel, das aus drei Stäben und einem Turm besteht. Der Turm ist aus n Scheiben aufgebaut, die zu Beginn auf dem ersten Stab aufgefädelt sind, so dass die Scheibengröße von unten nach oben abnimmt:Ziel des Spiels ist es, den Turm vom ersten auf den zweiten Stab zu bewegen, wobei immer nur eine Scheibe auf einmal bewegt werden und nie eine größere auf eine kleinere gelegt werden darf. Der Turm von Hanoi ist ein Denkspiel, das aus drei Stäben und einem Turm besteht. Der Turm ist aus n Scheiben aufgebaut, die zu Beginn auf dem ersten Stab aufgefädelt sind, so dass die Scheibengröße von unten nach oben abnimmt:Ziel des Spiels ist es, den Turm vom ersten auf den zweiten Stab zu bewegen, wobei immer nur eine Scheibe auf einmal bewegt werden und nie eine größere auf eine kleinere gelegt werden darf.
  
Zeile 203: Zeile 202:
  
 Schreibe ein rekursives Java-Programm, das eine Lösung für einen Turm der Höhe n ausgeben kann! Schreibe ein rekursives Java-Programm, das eine Lösung für einen Turm der Höhe n ausgeben kann!
 +
 +===== Aufgabe 7 =====
  
 Es gibt viele weitere grafische Beispiele zur Rekursion. Ein  anspruchsvolles Beispiel ist der Baum des Pythagoras (Bundeswettbewerb Informatik 1986). Finde heraus, wie er erzeugt wird, und programmiere ihn mit Java! Es gibt viele weitere grafische Beispiele zur Rekursion. Ein  anspruchsvolles Beispiel ist der Baum des Pythagoras (Bundeswettbewerb Informatik 1986). Finde heraus, wie er erzeugt wird, und programmiere ihn mit Java!
  • /var/www/infowiki/data/attic/q1/java-rekursion.1499765292.txt.gz
  • Zuletzt geändert: 2017/07/11 09:28
  • von admin03