Programmieren in C Rekursive . Dr. Nikolaus Wulff Programmieren in C 3 Verkettung von Funktionen •Rekursion mglicht eine ganz neue Klasse von Algorithmen, diese gehen ber die

  • Published on
    06-Feb-2018

  • View
    214

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>Prof. Dr. Nikolaus Wulff</p><p>Programmieren in CProgrammieren in C</p><p>Rekursive Funktionen</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 2</p><p>Rekursive Funktionen</p><p> Jede C Funktion besitzt ihren eigenen lokalen Satz an Variablen. </p><p> Dies bietet ganze neue Mglichkeiten Funktionen zu implementieren, die bis lang noch nicht betrachtet wurden.</p><p> Ein Funktion kann sich selbst rekursiv aufrufen!</p><p> Dies ist ein mchtiges Konzept der Sprache C, das nicht in jeder Programmiersprache mglich ist. Fortran oder Cobol kennen dies nicht...</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 3</p><p>Verkettung von Funktionen</p><p> Rekursion mglicht eine ganz neue Klasse von Algorithmen, diese gehen ber die bis lang betrachteten einfachen Schleifen hinaus.</p><p> Aus der Mathematik ist uns ein der Rekursion hnliches Verfahren, die Verkettung zweier Funktionen f und g zu einer Funktion h, bekannt:</p><p> Der Spezialfall f g ergibt genau die Konstellation, dass sich die Funktion f selber aufruft.</p><p> Allerdings ist dies keine Rekursion!</p><p>h(x) := (f g)(x) = f(g(x)) </p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 4</p><p>Verkettung versus Rekursion</p><p> Eine Gleichung der Form f(x) = h(x, f (g(x))) fhrt zu einer Rekursion.</p><p> Meist verknpft mit einer weiteren Funktion g, die das Argument x modifiziert und einer Funktion h.</p><p> Rekursion liegt vor, wenn die Funktion f sowohl auf der linken als auch der rechten Seite vorkommt!</p><p> Eine solche Funktion f kann sich unter Umstnden beliebig oft aufrufen.</p><p> Meist mit modifizierten Argument x g(x) Damit ein solcher Algorithmus terminiert muss der </p><p>Rekursion eine geeignete Grenze gesetzt werden.</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 5</p><p>Rekursive Algorithmen</p><p> Wir wollen einen Algorithmus sum entwickeln, der alle Zahlen von 1 bis n aufsummiert:</p><p> Die Definition (n) fr den Algorithmus sum legt eher einen Algorithmus nahe, der eine Schleife verwendet.</p><p> Es kostet einige berlegungen hierfr einen rekursiven Algorithmus zu finden...</p><p>n=j=1</p><p>n</p><p>j</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 6</p><p>sum als Schleife</p><p> Die folgende Implementierung von sum entspricht unserem bisherigen Programmierstil, wir verwenden eine Schleife:</p><p> Es ist offensichtlich, dass diese Implementierung eine direkte Umsetzung der Definition der Formel (n) der letzten Folie ist.</p><p>int sum(unsigned int n){ int j, s = 0; for(j=1; j</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 7</p><p>Aus Schleife wird Rekursion...</p><p> Ein rekursiver Algorithmus lsst sich aus der Analyse der definierenden Formel gewinnen:</p><p>n =j=1</p><p>n</p><p>j</p><p>n = nn121</p><p>n = nj=1</p><p>n1</p><p>j</p><p>n = n n1</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 8</p><p>sum per Rekursion</p><p> Die folgende Implementierung berechnet die Summe per Rekursion:</p><p> Um den Algorithmus besser zu verstehen, macht es Sinn ihn mit etwas Debug Output zu versehen...</p><p>int sum(unsigned int n) { if(n&gt;1) { return n + sum(n-1); } return n;}</p><p>sum(n) = n + sum(n-1)Verankerung sum(0) = 0 sowie sum(1) = 1</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 9</p><p>sum per Rekursion</p><p> Die Rekursionstiefe wird mit der statischen Variablen depth gezhlt.</p><p> Jeweils beim Eintritt und vor dem Verlassen der Methode werden depth, x und y ausgegeben.</p><p>static int depth = 0;</p><p>int sum(unsigned int x) { depth++; printf("BEG %d x: %d \n", depth, x); int y = x; if(x&gt;1) { y += sum(x-1); } printf("END %d sum(%d)=%d \n", depth, x, y); depth--; return y;}</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 10</p><p>Rekursive Sum in Aktion</p><p> Die folgende main Routine</p><p> liefert als Ausgabe: </p><p>int main() { int y, x = 5; y = sum(x); printf("\nResult: sum(%d)=%d\n", x, y); return 0; } BEG 1 x: 5BEG 2 x: 4</p><p>BEG 3 x: 3BEG 4 x: 2BEG 5 x: 1END 5 sum(1)=1END 4 sum(2)=3END 3 sum(3)=6END 2 sum(4)=10END 1 sum(5)=15</p><p>Result: sum(5)=15</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 11</p><p>Call Graph von sum</p><p>depth =1 sum(5)depth =1 sum(5) return 5 + 10 = 15</p><p>depth =2 sum(4) return 4 + 6 = 10</p><p>depth =3 sum(3) return 3 + 3 = 6</p><p>depth =4 sum(2) return 2 + 1 = 3</p><p>depth =5 sum(1) return 1</p><p>sum(1) = 1 sum(x) x + sum(x-1) fr x &gt; 1</p><p>Aufruf mit Argument 5 liefert nach 5 Rekursionen das Ergebnis 15</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 12</p><p>Die Fakultt</p><p> Die Fakultt Funktion n! besitzt sowohl eine Definition per Produkt:</p><p> als auch eine rekursive Definition:</p><p>n! := </p><p>1! := 1n! := n*(n-1)!</p><p>j=1</p><p>n</p><p>j</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 13</p><p>Fakultt rekursiv</p><p> Die rekursive faktorial Implementierung der Fakultt ist hnlich zur sum Funktion strukturiert.</p><p> Wichtig bei rekursiven Funktionen ist es, eine geeignete Abbruchbedingung vorzusehen, ansonsten terminiert der Algorithmus nie. =&gt; Stackoverflow</p><p> Dies ist vollkommen analog zur Problematik bei falsch programmierten Schleifen...</p><p>long factorial(long n) { if (n&gt;1) { return n*factorial(n-1); } return 1;}</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 14</p><p> Die beiden Beispiele besitzen die Struktur:</p><p> Mit der Funktion g(n)=n-1 und den Funktionen h1(n,m) = n+m fr die Summe und h2(n,m)=n*m fr die Fakultt.</p><p> Die Funktion g garantiert durch Verkleinerung von n, dass die Abbruchbedingung erreicht wird.</p><p>Gemeinsamkeiten</p><p>f n=hn , f g n</p><p>n=h1n , g n=n g n=n n1n!=h2n , g n!=n g n!=n n1!</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 15</p><p>Binrdarstellung </p><p> Ein Ganzzahl x soll binr dargestellt werden:</p><p> Die Entwicklungskoeffizienten lassen sich mit dem Pseudo-Algorithmus</p><p> ermitteln, allerdings in der falschen Reihenfolge!</p><p>x=j=0</p><p>n</p><p>b j 2j</p><p>b j{0,1 }</p><p>while(x) { b = x mod 2 x = x/2 print(b)}</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 16</p><p>Rekursive Binrdarstellung</p><p> Ein rekursiver Algorithmus ermglicht eine einfache Implementierung ohne revers Operation...</p><p>void printBinaery(unsigned int x) { if (x</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 17</p><p>Rekursive Sortierung</p><p> Quicksort ist ein rekursiver Algorithmus. Aus einem unsortierten Feld wird ein Element p </p><p>ausgewhlt und der Rest in zwei Untermengen aufgeteilt. Eine Menge mit Elementen grer als das ausgewhlte Element p, die andere mit Elementen kleiner gleich dem ausgewhlten Element. </p><p> Diese Unterteilung wird so lange vorgenommen bis die Teilmengen weniger als zwei Elemente haben, dann terminiert die jeweilige Rekursion.</p><p> Am Ende aller Rekursionen ist das Feld sortiert.</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 18</p><p>Rekursiver Quicksortvoid qindex(int v[], int left, int right);</p><p>void qsort(int v[], int left, int right) { if (left&gt;=right) return;/* Terminator */ int p = qindex(v, left, right); qsort(v, left, p-1); qsort(v, p+1, right);}</p><p>void sort(int v[], int length) { qsort(v, 0, length);}</p><p> sort initialisiert den rekursiven qsort Algorithmus. Dieser verwendet die Hilfsfunktion qindex, um </p><p>rekursiv das Feld in zwei Teilbereiche zu unterteilen und zu sortieren.</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 19</p><p>Pivot Element ermitteln</p><p>void qswap(int a[], int x, int y) { int tmp=a[x]; a[x]=a[y]; a[y]=tmp;}</p><p>int qindex(int v[], int left, int right) { int i, p, mid = (left+right)/2; qswap(v, left, mid); /* store pivot element */ p = left; for(i=left+1; i</p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 20</p><p>Der Einfluss von qswap Was die bersich bei der Rekursionsfolge </p><p>erschwert, ist dass qindex mehrmals qswap aufruft.</p><p> Nach dem Aufruf von qindex liegt also die Folge {431502}&lt; 6 </p></li><li><p>Prof. Dr. Nikolaus Wulff Programmieren in C 21</p><p>Rekursion kann kompliziert sein...</p><p> Die Rekursion dieses Algorithmus ist nicht mehr so einfach nachzuvollziehen:</p><p> Vorbelegung Es resultiert die folgende Folge von Rekursionen:</p><p> int v[]={5,3,9,1,6,7,0,2,8,4};</p><p> {5,3,9,1,6,7,0,2,8,4}</p><p> {4,3,1,5,0,2} {7,8,9}</p><p> {0} {4,5,3,2} </p><p>{2,4,3} </p><p>{3,2} </p><p>{2} </p><p> {7} {9}</p><p>Programmieren in CFolie 2Folie 3Folie 4Folie 5Folie 6Folie 7rekursive sumFolie 9Folie 10Folie 11Folie 12Folie 13Folie 14Folie 15Folie 16qsortFolie 18Folie 19Folie 20Folie 21</p></li></ul>

Recommended

View more >