Tilman
85 lines
3.6 KiB
PHP
85 lines
3.6 KiB
PHP
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
|
|
<html>
|
|
<head>
|
|
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
|
|
<link rel="stylesheet" type="text/css" media="all" href="stylesheet.css">
|
|
<title>Rekursion</title>
|
|
</head>
|
|
<body>
|
|
<span id="menu"><a href="index.php">zurück zur Liste</a></span>
|
|
|
|
<div id="buttons">
|
|
<form action="edit.php" method="POST">
|
|
<input type="hidden" name="filename" value="<?php echo $_SERVER['SCRIPT_FILENAME']?>">
|
|
<p>
|
|
<input type="submit" value="Seite bearbeiten">
|
|
</p>
|
|
</form>
|
|
</div>
|
|
|
|
<h1>Rekursion</h1>
|
|
<p>
|
|
(Unter-)Programme sind <b>rekursiv</b>, wenn sie sich selbst direkt oder indirekt aufrufen. Eine Rekursion läuft, bis sie durch einen <b>Rekursionsanker</b>, eine Abbruchbedingung für eine Rekursion endet. Man unterscheidet zwischen <b>linearen</b> und <b>nicht linearen</b> Rekursionen.
|
|
</p>
|
|
|
|
<h2>Lineare Rekursion</h2>
|
|
<p>
|
|
Eine Funktion ist linear rekursiv, wenn nur ein rekursiver Aufruf erfolgt. Für die Fakultätsfunktion könnte das so aussehen:<br>
|
|
<pre>
|
|
fakul 0 = 1
|
|
fakul n = n(fakul n-1)
|
|
</pre>
|
|
Der Computer würde bei Aufruf <span id="syntax">fakul 3</span> im ersten Schritt alle Aufrufe auf den Stack legen:
|
|
<pre>
|
|
1. fakul 3 = 3 *
|
|
2. ( 2 *
|
|
4. ( 1 *
|
|
5. ( 1 ) ) )
|
|
</pre>
|
|
und nach erreichen des Rekursionsankers <span id="syntax">fakul 0 = 1</span> alle auf dem Stack abgelegten Zahlen aufmultiplizieren:
|
|
<pre>
|
|
5. ( 1 ) ) )
|
|
6. ( 1 *
|
|
7. ( 2 *
|
|
8. 3 *
|
|
9. 6 =
|
|
</pre>
|
|
Die Rekursion wird also einmal hin und zurück durchlaufen.<br>
|
|
<br>
|
|
Lineare Rekursionen, die nicht noch einmal "zurücklaufen", nennt man <b>endrekursiv</b> (tail recursion). Man unterscheidet also zwischen endrekursiven und nicht-endrekursiven linearen Rekursionen. Die Fakultätsfunktion lässt sich auch endrekursiv implementieren:
|
|
<pre>
|
|
fakul 0 a = a
|
|
fakul n a = fakul (n-1) (a*n)
|
|
</pre>
|
|
Die Variable <span id="syntax">a</span> läuft bei der Rekursion mit und summiert das Endergebnis auf, so dass beim erreichen des Rekursionsankers das Endergebnis bereits feststeht (<b>Akkumulatortechnik</b>). Diese Variante braucht kaum Speicher, das der Stack nicht mit den rekursiven Aufrufen gefüllt wird.
|
|
</p>
|
|
|
|
<h2>Nicht-lineare Rekursion</h2>
|
|
<p>
|
|
Eine rekursive Funktion ist nicht-linear rekursiv, wenn die Ausführung zu mehr als einem rekursiven Aufruf führt.
|
|
|
|
<p>
|
|
Ein Beispiel für eine nicht-lineare Rekursion ist die Fibonaccifunktion in dieser Form:
|
|
<pre>
|
|
fibo 0 = 0
|
|
fibo 1 = 1
|
|
fibo n = fibo (n-1) + fibo (n-2)
|
|
</pre>
|
|
Bei der Ausführung spaltet sich die Auswertung der rekursiven Aufrufe logisch in einen Baum:
|
|
<p>
|
|
<img src="fibo5.gif">
|
|
</p>
|
|
</p>
|
|
</p>
|
|
|
|
<h2>Entrekursivierung</h2>
|
|
<p>
|
|
Endrekursive Algorithmen können entrekursiviert werden. Dazu überführt man den Algorithmus in eine Schleife.<br>
|
|
Lineare Algorithmen müssen erst mittels Akkumulatortechnik in eine endrekursive Form überführt werden, um sie entrekursivieren zu können. Nicht-lineare Rekursionen können nicht einfach durch Anwendung eines Schemas entrekursivieren.
|
|
</p>
|
|
|
|
<h2>Links</h2>
|
|
<a href="http://www.vameo.de/uni/tutorium/rekursionen.pdf">Merkblatt zu Rekursion von Augustin</a>
|
|
|
|
</body>
|
|
</html> |