Rekursion - Versionsgeschichte

Anthoney: /* Definition */ zwei Allerwerltsweißheiten

2011-11-09T14:32:27Z

Definition: zwei Allerwerltsweißheiten

← Nächstältere Version		Version vom 9. November 2011, 14:32 Uhr
Zeile 3:		Zeile 3:

	== Definition ==		== Definition ==
			* „Um Rekursion zu verstehen, muss man erst einmal Rekursion verstehen.“
			* Kürzeste Definition für Rekursion: „siehe Rekursion.“
	* Bei einer Rekursion wird ein Problem damit gelöst, dass man Zwischenergebnisse wiederum nach gleichem Muster weiterverwendet.		* Bei einer Rekursion wird ein Problem damit gelöst, dass man Zwischenergebnisse wiederum nach gleichem Muster weiterverwendet.
	* Es gibt die Direkte Rekursion und eine Indirekte		* Es gibt die Direkte Rekursion und eine Indirekte
Zeile 9:		Zeile 11:
	* Primitive Rekursion ist stets durch eine Iteration ersetzbar; Der Aufruf-Baum enthält keine Verzweigungen (Aufruf-Kette)		* Primitive Rekursion ist stets durch eine Iteration ersetzbar; Der Aufruf-Baum enthält keine Verzweigungen (Aufruf-Kette)
	* Rekursion tritt am Anfang oder am Ende auf. (Hinweis)		* Rekursion tritt am Anfang oder am Ende auf. (Hinweis)


	== Praktisches Leben ==		== Praktisches Leben ==

Pfitzi: /* Beispiele */

2011-11-04T16:30:38Z

Beispiele

← Nächstältere Version		Version vom 4. November 2011, 16:30 Uhr
Zeile 30:		Zeile 30:

	* Fakultät n! = n * (n-1)! bis n=0 und n!=0 ist 1		* Fakultät n! = n * (n-1)! bis n=0 und n!=0 ist 1
	~~fakulät_rekursiv~~ (n)		fakultät_rekursiv (n)
	if n <= 1		if n <= 1
	then return 1		then return 1

Pfitzi: /* Beispiele */

2011-11-04T16:26:15Z

Beispiele

← Nächstältere Version		Version vom 4. November 2011, 16:26 Uhr
Zeile 35:		Zeile 35:
	else return n * fakultät_rekursiv (n-1)		else return n * fakultät_rekursiv (n-1)

	Eine iterative Lösung sieht ~~wei~~ folgt aus;		Eine iterative Lösung sieht wie folgt aus;
	fakultät_iterativ (n)		fakultät_iterativ (n)
	fakultät := 1		fakultät := 1

Pfitzi: Falscher Bezeichner ... Weiter unten wird es "fakultät_rekursiv" genannt ...

2011-11-04T16:25:38Z

Falscher Bezeichner ... Weiter unten wird es "fakultät_rekursiv" genannt ...

← Nächstältere Version		Version vom 4. November 2011, 16:25 Uhr
Zeile 30:		Zeile 30:

	* Fakultät n! = n * (n-1)! bis n=0 und n!=0 ist 1		* Fakultät n! = n * (n-1)! bis n=0 und n!=0 ist 1
	~~fakutlätt_rekursiv~~ (n)		fakulät_rekursiv (n)
	if n <= 1		if n <= 1
	then return 1		then return 1

Pfitzi: Fehlende schließende Klammer ...

2011-11-04T16:23:56Z

Fehlende schließende Klammer ...

← Nächstältere Version		Version vom 4. November 2011, 16:23 Uhr
Zeile 19:		Zeile 19:

	=== Beispiele ===		=== Beispiele ===
	* Die Summe von Zahlen ist: sum(x) = x + sum(x-1) wenn (0 dann 0		* Die Summe von Zahlen ist: sum(x) = x + sum(x-1) wenn (0 dann 0)
	sum(n)		sum(n)
	= 0 (falls n = 0 Rekursionsanfang)		= 0 (falls n = 0 Rekursionsanfang)
Zeile 43:		Zeile 43:
	faktor := faktor + 1		faktor := faktor + 1
	return fakultät		return fakultät




	== Links und Quellen ==		== Links und Quellen ==

Anthoney: Init

2011-11-04T09:50:20Z

Init

Neue Seite

{{Dieser Artikel|erläutert die Technik der rekursiven Definition; zum Begriff '''rekursive Menge''' siehe [[entscheidbar]].}}
Rekursion (Rekurrenz, Rekursivität) stammt vom lateinischen recurrere (zurücklaufen; englisch recursion)

== Definition ==
* Bei einer Rekursion wird ein Problem damit gelöst, dass man Zwischenergebnisse wiederum nach gleichem Muster weiterverwendet.
* Es gibt die Direkte Rekursion und eine Indirekte

=== Primitive Rekursion ===
* Primitive Rekursion ist stets durch eine Iteration ersetzbar; Der Aufruf-Baum enthält keine Verzweigungen (Aufruf-Kette)
* Rekursion tritt am Anfang oder am Ende auf. (Hinweis)

== Praktisches Leben ==
* "Dieser Satz ist unwahr." (Selbstbezug) (Direkt)
* "Der folgende Satz ist wahr. Der vorhergehende Satz ist unwahr". (Indirekt)

== Programmierung ==
Rekursion tritt beim [[Computerprogramm|Programmieren]] auf. Hier wird immer wieder dieselbe Funktion aufgerufen.

=== Beispiele ===
* Die Summe von Zahlen ist: sum(x) = x + sum(x-1) wenn (0 dann 0
sum(n)
= 0 (falls n = 0 Rekursionsanfang)
oder sum(n-1) + n (Wenn n>=1 Rekursionsschritt)
sum(3) = sum(2) + 3
sum(2) = sum(1) + 2
sum(1) = sum(0) + 1
sum(0) = 0
--> 0+1+2+3 = 6

* Fakultät n! = n * (n-1)! bis n=0 und n!=0 ist 1
fakutlätt_rekursiv (n)
if n <= 1
then return 1
else return n * fakultät_rekursiv (n-1)

Eine iterative Lösung sieht wei folgt aus;
fakultät_iterativ (n)
fakultät := 1
faktor := 2
while faktor <= n
fakultät := fakultät * faktor
faktor := faktor + 1
return fakultät

== Links und Quellen ==
=== Siehe auch ===
=== Weblinks ===
=== Quellen ===
=== Literatur ===
=== Einzelnachweise ===
<references/>
----

[[Kategorie:Rekursion| ]]

{{Vorlage:PPA-Eisen|Txt=Rekursion}}