Bild Referenz: https://starecat.com/learn-to-program-make-a-recursive-function-no-exit-condition-fail/
Intro
Hallo, ich bin's @drifter2! Das heutige Thema sind Rekursive Algorithmen die am englischen Artikel "C Recursive Algorithms" basiert sind. Das heißt das es wieder mal eine Übersetzung von einen englischen Artikel in meinen Haupt account @drifter1 sein wird, aber ich werde natürlich auch viel mehr Informationen vom Internet hinzufügen. Also dann fangen wir mal an!
Rekursion
Rekursion ist ein Wort das vom lateinisch "recurrere" abstammt und in Deutsch "zurücklaufen" bedeutet. Eine Rekursion ist also ein abstrakter Vorgang der als Problemlösungsstrategie benutzt wird, da komplexe Sachverhalte oft mit rekursiv formulierten Regeln gelöst werden. Das Grundprinzip ist also das so genannte Zurückführen einer allgemeinen Aufgabe auf eine einfachere (und kleinere) Aufgabe derselben Klasse. Die Rekursive Programmierung ist Bestandteil vieler Programmiersprachen. Prozeduren oder Funktionen können sich selbst aufrufen. Die Rekursive und Iterative Formulierung eines Problems sind gleich-mächtige Sprachmittel.
Der größte Fehler den man bei Rekursiven Funktionen machen kann ist der so genannte infinite Regress oder Endlosschleife. Jeder Aufruf einer rekursiven Funktion wird dadurch in unendlich viele Schritte entfalten. Mann muss also aufpassen das die Rekursion mit eigentlichen Sinn definiert wurde. Es muss also eine Abbruchbedingung haben. Jede Schleife oder rekursive Funktion benötigt diese um nicht endlos zu laufen. Die Existenz dieser Bedingung garantiert den Abbruch aber nicht. Die ist also notwendig aber nicht hinreichend. Das heißt das die Funktion gut formuliert werden muss so das alle Regeln einen Sinn haben. Das ist also sehr ähnlich zu der 'break' und 'continue' Anweisung die wir bei Schleifen (while-loops) benutzen.
Wieso benutzten wir die Rekursionen dann wenn diese gleichwertig zu Iterativen Lösungen sind? Ja, diese Frage ist sehr interessant. Eine Rekursion und Iteration formulieren ein Problem in verschiedenen Wegen. Die eigentliche "Leistung" ist am Problem abhängig. Das heißt das eine Rekursive Lösung manchmal viel schneller als eine Iterative Lösung sein kann. Wenn ein großes Problem leicht und effizient in kleinere Problem "zerlegt" werden kann, dann werden natürlich mehrere kleine Probleme viel schneller als das große Problem gelöst. Manche Probleme sind mit iterativen programmieren viel schneller als mit rekursiven.
Bevor wir über die Implementierung in der Sprache C reden, sollten wir vielleicht die wichtigsten Punkte-Schritte zusammenfassen. Jeder Rekursive Algorithmen benötigt:
- Eine Abbruchbedingung, die dafür sorgt, dass keine Endlosschleife entsteht.
- Ein kleiner Teil des Problems wird in der Funktion selbst gelöst. Der Rest wird durch die Rekursion von sich selbst gelöst.
- Wenn nötig kombinieren wir die kleineren Lösungen
Rekursion in C
Eine Rekursive Funktion in C wird wie folgend formuliert:
Rückgabetyp Funktionsname(//Parameter){ if (//Abbruchbedingung) return value; // Wert den die vorherige Rekursion benutzt else // Funktion Rekursiert return Funktionsname(//Andere Parameter);}Note: All dass kann manchmal auch andersrum sein!
Manche Probleme und Rekursive Algorithmen geben keinen Wert zurück. In solchen Problem spezifizieren die Parameter die "Größe" des kleineren Problems.
Damit ihr alles besser versteht müssen wir ein paar Beispiel Algorithmen erwähnen...
Algorithmen Beispiele
Die leichtesten Algorithmen dieser Kategorie sind:
- Der Fakultät (!) von Mathematik
- Die Binäre Suche eines Werts in einem Feld-Array
Fakultät (Factorial)
Der Fakultät in Mathematik ist das Produkt der Ganzzahlen von 1 bis N (1*2*...*Ν) das mit N! notiert wird. Der Fakultät von 1 gibt natürlich 1 (1! = 1). Der Fakultät von 0 gibt auch 1 (0! = 1) und ist dadurch die Abbruchbedingung von dem Algorithmus. Damit wir mit 0 enden und da der erste Wert den wir als Parameter bekommen die Ganzzahl N ist, wird das Produkt mit dekrementierten Ganzzahlen gebildet.
Die Fakultät von Vier ist dadurch: 4! = 4 * 3 * 2 * 1 = 24.
Der Code in C ist:
long int factorial (int n){ if(n >= 1){ // wir geben den Wert von n * (n - 1)! zurück, // der zweite Part bekommt den Wert erst wenn wir "zurückgeben" return n * factorial(n - 1); // Rekursion } else{ // Abbruchbedingung (n <= 0) // bei 0 fängt der Algorithmus mit der Rückgabe der Werte an // und multipliziert dadurch in der Reihenfolge 1*2*...*n // am Ende werden wir dadurch die Fakultät bekommen return 1; }}Diese Methode der Problemlösung heißt Decrease-and-Conquer oder Verringern-und-Erobern auf Deutsch. Der nächste Algorithmus benutzt die Methode: Divide-and-Conquer oder Teilen-und-Erobern auf Deutsch.
Binäre Suche (Binary search)
Ein weiterer leichter und rekursiver Algorithmen ist die so genannte Binäre Suche. Dieser Algorithmus findet eine Nummer in einem sortierten Feld-Array in dem effizientesten Weg des es gibt. Wir "zerteilen" das Problem genau in der Mitte und gehen zu der richtigen Seite (links oder rechts) nach einer Bedingung. Wenn der mittlere Wert kleiner ist als die gesuchte Nummer gehen wir natürlich nach rechts. Wenn der mittlere Wert größer ist gehen wir nach links. Wenn der mittlere Wert genau der Wert denn wir suchen ist, dann hört der Algorithmus auf. Natürlich müssen wir auch aufpassen das der Algorithmus auch aufhört wenn der gesuchte Wert nicht gefunden wird.
Sagen wir mal wir haben das folgende Feld:
A = [3, 5, 8, 9, 11, 15]
Wir wollen den Wert 11 finden. Wir könnten von Anfang oder Ende des Feldes anfangen und alle Werte mit dem gesuchten Wert abgleichen oder den erwähnten Algorithmus der Binären Suche verwenden. Die Ausführung sieht wie folgend aus:
Mittel-Index = 6/2 = 3 => A[3] = 9 < 11 also gehen wir zu der rechten Seite.
Dadurch ist das Feld nur zum Feld B = [11, 15] reduziert worden.
Der Mittel-Index ist jetzt 2/2 = 1 und B[1] = 15 < 11 und wir gehen zur linken Seite.
Das Feld ist jetzt eine einzige Zahl C = [11], wo 11 == 11
Also haben wir den gesuchten Wert gefunden.
Natürlich werden wir keine neuen Felder-Arrays deklarieren sondern links und rechts Indikatoren benutzen die Feld-Regionen anzeigen werden. Dadurch kann die nicht Existenz des Werts sehr leicht mit links == rechts gecheckt werden. "Links == Rechts" und "Links < Rechts" sind dadurch die Abbruchbedingungen des Algorithmus.
Der Code ist wie folgend:
int binary_search(int A[], int left, int right, int value){ if(left == right){ // nur ein Wert im Feld // Wenn es der korrekte Wert is if(A[left] == value){ return left; // Index zurueckgeben } else{ return -1; // Nicht gefunden (also -1 Index) } } else if(left > right){ // Abbruchbedingung return -1; // Nicht gefunden (also -1 Index) } int middle = (left + right)/2; // Mittel Index finden // Wenn Mittel den Wert hat if(A[middle] == value){ return middle; // Mittel-Index zurueckgeben } else if(A[middle] > value){ // kleiner -> Rekursion return binarysearch(A, left, middle, value); } else{ // groesser -> Rekursion return binarysearch(A, middle + 1, right, value); }}Wie ihr sehen könnt gibt diese Funktion nun einen Wert zurück. Dieser Wert zeigt uns die eigentliche Position des gefundenen Werts im Feld. Mit nen Wert von '-1' wissen wir dadurch das der Wert nicht gefunden wurde.
Referenzen:
- https://de.wikipedia.org/wiki/Rekursion
- https://de.wikipedia.org/wiki/Abbruchbedingung
- https://perlgeek.de/de/artikel/rekursion
- http://www.c-howto.de/tutorial/funktionen-teil-2/rekursion/
- http://www.saar.de/~awa/jrekursion.html
- https://de.wikiversity.org/wiki/Kurs:Algorithmen_und_Datenstrukturen/Vorlesung/Bin%C3%A4re_Suche
Vorherige Artikel
Einführung -> Programmiersprachen, die Sprache C, Anfänger Programme
Felder -> Felder, Felder in C, Erweiterung des Anfänger Programms
Zeiger, Zeichenketten und Dateien -> Zeiger, Zeichenketten, Dateiverarbeitung, Beispielprogramm
Dynamische Speicherzuordnung -> Dynamischer Speicher, Speicherzuweisung in C, Beispielprogramm
Strukturen und Switch Case -> Switch Case Anweisung, Strukturen, Beispielprogramm
Funktionen und Variable-Gueltigkeitsbereich -> Funktionen, Variable Gueltigkeitsbereich
Schlusswort
Und das war's dann auch mit dem heutigen Artikel und ich hoffe ich hab alles verständlich erklärt. Νächstes mal werden wir mit Datenstrukturen anfangen, wo die erste und leichteste die so genannte Liste ist! Dieser ganzen Artikel diente dazu das ihr eine gewisse Ahnung über Rekursionen habt, da die Algorithmen in Datenstrukturen leicht mit der Hilfe von Rekursionen implementiert werden können.
Keep on drifting! ;)