Prof. Dr. Nikolaus Wulff

Programmieren in CProgrammieren in C

Rekursive Funktionen

Prof. Dr. Nikolaus Wulff Programmieren in C 2

Rekursive Funktionen

• Jede C Funktion besitzt ihren eigenen lokalen Satz an Variablen.

• Dies bietet ganze neue Möglichkeiten Funktionen zu implementieren, die bis lang noch nicht betrachtet wurden.

• Ein Funktion kann sich selbst rekursiv aufrufen!

• Dies ist ein mächtiges Konzept der Sprache C, das nicht in jeder Programmiersprache möglich ist. Fortran oder Cobol kennen dies nicht...

Prof. Dr. Nikolaus Wulff Programmieren in C 3

Verkettung von Funktionen

• Rekursion möglicht eine ganz neue Klasse von Algorithmen, diese gehen über die bis lang betrachteten einfachen Schleifen hinaus.

• Aus der Mathematik ist uns ein der Rekursion ähnliches Verfahren, die Verkettung zweier Funktionen f und g zu einer Funktion h, bekannt:

• Der Spezialfall f ≡ g ergibt genau die Konstellation, dass sich die Funktion f selber aufruft.

• Allerdings ist dies keine Rekursion!

°h(x) := (f g)(x) = f(g(x))

Prof. Dr. Nikolaus Wulff Programmieren in C 4

Verkettung versus Rekursion

• Eine Gleichung der Form f(x) = h(x, f (g(x))) führt zu einer Rekursion.

• Meist verknüpft mit einer weiteren Funktion g, die das Argument x modifiziert und einer Funktion h.

• Rekursion liegt vor, wenn die Funktion f sowohl auf der linken als auch der rechten Seite vorkommt!

• Eine solche Funktion f kann sich unter Umständen beliebig oft aufrufen.

– Meist mit modifizierten Argument x → g(x)

• Damit ein solcher Algorithmus terminiert muss der Rekursion eine geeignete Grenze gesetzt werden.

Prof. Dr. Nikolaus Wulff Programmieren in C 5

Rekursive Algorithmen

• Wir wollen einen Algorithmus sum entwickeln, der alle Zahlen von 1 bis n aufsummiert:

• Die Definition σ(n) für den Algorithmus sum legt eher einen Algorithmus nahe, der eine Schleife verwendet.

• Es kostet einige Überlegungen hierfür einen rekursiven Algorithmus zu finden...

n=∑j=1

n

j

Prof. Dr. Nikolaus Wulff Programmieren in C 6

sum als Schleife

• Die folgende Implementierung von sum entspricht unserem bisherigen Programmierstil, wir verwenden eine Schleife:

• Es ist offensichtlich, dass diese Implementierung eine direkte Umsetzung der Definition der Formel σ(n) der letzten Folie ist.

int sum(unsigned int n){ int j, s = 0; for(j=1; j<=n; j++) { s += j; } return s;}

Prof. Dr. Nikolaus Wulff Programmieren in C 7

Aus Schleife wird Rekursion...

• Ein rekursiver Algorithmus lässt sich aus der Analyse der definierenden Formel gewinnen:

n =∑j=1

n

j

n = nn−121

n = n∑j=1

n−1

j

n = n n−1

Prof. Dr. Nikolaus Wulff Programmieren in C 8

sum per Rekursion

• Die folgende Implementierung berechnet die Summe per Rekursion:

• Um den Algorithmus besser zu verstehen, macht es Sinn ihn mit etwas Debug Output zu versehen...

int sum(unsigned int n) { if(n>1) { return n + sum(n-1); } return n;}

sum(n) = n + sum(n-1)Verankerung sum(0) = 0 sowie sum(1) = 1

Prof. Dr. Nikolaus Wulff Programmieren in C 9

sum per Rekursion

• Die Rekursionstiefe wird mit der statischen Variablen depth gezählt.

• Jeweils beim Eintritt und vor dem Verlassen der Methode werden depth, x und y ausgegeben.

static int depth = 0;

int sum(unsigned int x) { depth++; printf("BEG %d x: %d \n", depth, x); int y = x; if(x>1) { y += sum(x-1); } printf("END %d sum(%d)=%d \n", depth, x, y); depth--; return y;}

Prof. Dr. Nikolaus Wulff Programmieren in C 10

Rekursive Sum in Aktion

• Die folgende main Routine

• liefert als Ausgabe:

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: 4BEG 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

Result: sum(5)=15

Prof. Dr. Nikolaus Wulff Programmieren in C 11

Call Graph von sum

depth =1 sum(5)depth =1 sum(5) return 5 + 10 = 15

depth =2 sum(4) return 4 + 6 = 10

depth =3 sum(3) return 3 + 3 = 6

depth =4 sum(2) return 2 + 1 = 3

depth =5 sum(1) return 1

sum(1) = 1 sum(x) ≡ x + sum(x-1) für x > 1

Aufruf mit Argument 5 liefert nach 5 Rekursionen das Ergebnis 15

Prof. Dr. Nikolaus Wulff Programmieren in C 12

Die Fakultät

• Die Fakultät Funktion n! besitzt sowohl eine Definition per Produkt:

• als auch eine rekursive Definition:

n! :=

1! := 1n! := n*(n-1)!

∏j=1

n

j

Prof. Dr. Nikolaus Wulff Programmieren in C 13

Fakultät rekursiv

• Die rekursive faktorial Implementierung der Fakultät ist ähnlich zur sum Funktion strukturiert.

• Wichtig bei rekursiven Funktionen ist es, eine geeignete Abbruchbedingung vorzusehen, ansonsten terminiert der Algorithmus nie. => Stackoverflow

• Dies ist vollkommen analog zur Problematik bei falsch programmierten Schleifen...

long factorial(long n) { if (n>1) { return n*factorial(n-1); } return 1;}

Prof. Dr. Nikolaus Wulff Programmieren in C 14

• Die beiden Beispiele besitzen die Struktur:

• Mit der Funktion g(n)=n-1 und den Funktionen h

1(n,m) = n+m für die Summe und h

2(n,m)=n*m

für die Fakultät.

• Die Funktion g garantiert durch Verkleinerung von n, dass die Abbruchbedingung erreicht wird.

Gemeinsamkeiten

f n=hn , f g n

n=h1n , g n=n g n=n n−1

n!=h2n , g n!=n g n!=n n−1!

Prof. Dr. Nikolaus Wulff Programmieren in C 15

Binärdarstellung

• Ein Ganzzahl x soll binär dargestellt werden:

• Die Entwicklungskoeffizienten lassen sich mit dem Pseudo-Algorithmus

• ermitteln, allerdings in der falschen Reihenfolge!

x=∑j=0

n

b j 2j

b j∈{0,1 }

while(x) { b = x mod 2 x = x/2 print(b)}

Prof. Dr. Nikolaus Wulff Programmieren in C 16

Rekursive Binärdarstellung

• Ein rekursiver Algorithmus ermöglicht eine einfache Implementierung ohne revers Operation...

void printBinaery(unsigned int x) { if (x<2) { printf(“%d“,x); } else { printBinaery(x/2); printf(“%d“,x%2); }}

Prof. Dr. Nikolaus Wulff Programmieren in C 17

Rekursive Sortierung

• Quicksort ist ein rekursiver Algorithmus.

• Aus einem unsortierten Feld wird ein Element p ausgewählt und der Rest in zwei Untermengen aufgeteilt. Eine Menge mit Elementen größer als das ausgewählte Element p, die andere mit Elementen kleiner gleich dem ausgewählten Element.

• Diese Unterteilung wird so lange vorgenommen bis die Teilmengen weniger als zwei Elemente haben, dann terminiert die jeweilige Rekursion.

• Am Ende aller Rekursionen ist das Feld sortiert.

Prof. Dr. Nikolaus Wulff Programmieren in C 18

Rekursiver Quicksort

void qindex(int v[], int left, int right);

void qsort(int v[], int left, int right) { if (left>=right) return;/* Terminator */ int p = qindex(v, left, right); qsort(v, left, p-1); qsort(v, p+1, right);}

void sort(int v[], int length) { qsort(v, 0, length);}

• sort initialisiert den rekursiven qsort Algorithmus.

• Dieser verwendet die Hilfsfunktion qindex, um rekursiv das Feld in zwei Teilbereiche zu unterteilen und zu sortieren.

Prof. Dr. Nikolaus Wulff Programmieren in C 19

Pivot Element ermitteln

void qswap(int a[], int x, int y) { int tmp=a[x]; a[x]=a[y]; a[y]=tmp;}

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<=right; i++) { if (v[i] < v[left]) { /* compare to pivot */ qswap(v, ++p, i); } } qswap(v, left, p); /* restore pivot element */ return p; /* v[left,...,p]<= v[p] */}

Prof. Dr. Nikolaus Wulff Programmieren in C 20

Der Einfluss von qswap

• Was die Übersich bei der Rekursionsfolge erschwert, ist dass qindex mehrmals qswap aufruft.

• Nach dem Aufruf von qindex liegt also die Folge {431502}< 6 <{789} vor.

{5,3,9,1,6,7,0,2,8,4} {6,3,9,1,5,7,0,2,8,4} {6,3,9,1,5,7,0,2,8,4} {6,3,9,1,5,7,0,2,8,4} 3 ↔ 3 {6,3,9,1,5,7,0,2,8,4} 3 ↔ 3 {6,3,1,9,5,7,0,2,8,4} 9 ↔ 1 {6,3,1,9,5,7,0,2,8,4} 9 ↔ 1

{6,3,1,5,9,7,0,2,8,4} 9 ↔ 5 {6,3,1,5,9,7,0,2,8,4} 9 ↔ 5

{6,3,1,5,0,7,9,2,8,4} 9 ↔ 0 {6,3,1,5,0,7,9,2,8,4} 9 ↔ 0 {6,3,1,5,0,2,9,7,8,4} 7 ↔ 2 {6,3,1,5,0,2,9,7,8,4} 7 ↔ 2 {6,3,1,5,0,2,4,7,8,9} 9 ↔ 4 {6,3,1,5,0,2,4,7,8,9} 9 ↔ 4

{4,3,1,5,0,2,6,7,8,9}

AusgangssituationAusgangssituationPivotelement 6 sichern

Pivotelement 6 restaurieren

Prof. Dr. Nikolaus Wulff Programmieren in C 21

Rekursion kann kompliziert sein...

• Die Rekursion dieses Algorithmus ist nicht mehr so einfach nachzuvollziehen:

• Vorbelegung

• Es resultiert die folgende Folge von Rekursionen:

int v[]={5,3,9,1,6,7,0,2,8,4};

{5,3,9,1,6,7,0,2,8,4}

{4,3,1,5,0,2} {7,8,9}

{0} {4,5,3,2}

{2,4,3}

{3,2}

{2}

{7} {9}