Teil 2

In 2. Teil der Rekursionen möchte ich Ihnen einige Beispiele demonstrieren die recht einfach zu verstehen sind. Diese Programme sollen nur das Kapitel der Rekursion deutlich machen. Es ist Einleuchtend das diese Programme Iterativ einfacher und meistens auch besser sind. Die Beispiele sind klassische Beispielen wie sie in fast allen guten Leerbüchern enthalten sind.

Als erstes Beispiel wollen wir eine Funktion schreiben zum Berechnen der Fakultät von der Zahl n. Die Fakultät der Zahl 6 ist zum Beispiel : 1*2*3*4*5*6 = 720 oder die Fakultät von 10 ist 1*2*3*4*5*6*7*8*9*10=3.628.800 .

Wie schreiben wir die Funktion am besten? Als erstes und wichtigstes benötigen wir eine Abbruchbedienung. Dafür müssen wir lediglich prüfen ob die Zahl von der wir die Fakultät haben wollen ungleich 0 ist. Hier nun das Programm....

/*Download:fakul.c*/ #include <stdio.h> long fakul(int n) { if(n) return n * fakul(n-1); return 1; } int main() { printf("Fakultät von 5 = %ld\n",fakul(5)); printf("Fakultät von 9 = %ld\n",fakul(9)); return 0; }

Unsere Funktion rechnet so lange n*n-1 bis n den Wert 0 hat den n*0 würde sonst das Ergebnis 0 ergeben. Bei fakul(5) wären dies dann 5*4*3*2*1=120 wobei wir uns n*1 eigentlich auch ersparen können denn mit n*1 wird sich der Wert nicht ändern. Natürlich will ich Ihnen die Iterative Lösung von diesem Beispiel nicht vorenthalten...

long fakul(long n)
{
 int x=n;
 while(--x)
    n*=x;
 return n;
}

Ein weiteres rekursives Beispiel wäre das Spiegeln eines Textes ...

/*Download:reverse.c*/ #include <stdio.h> void reverse(char *s) { if(*s) { reverse(s+1); putchar(*s); } } int main() { reverse("Some men interpret nine memos"); printf("\n"); reverse("HALLO"); printf("\n"); return 0; }

Bei dieser Rekursion wir jeder einzelne Buchstabe auf einem Stack gelegt. Z.B. bei HALLO zuerst das H dann das A usw. Jede einzelne Ablage auf dem Stack beinhaltet natürlich wie immer den Wert (Buchstabe) den Parameter und die Rücksprungadresse. An diesem Beispiel können sie erkennen das die Rücksprungadresse hinter der Rekursion putchar(*s) zum Ausgeben einzelner Zeichen lautet.

Als nächstes Beispiel wir Fibonacci-Zahlen rekursiv berechnen. Fibonacci-Zahlen sind z.B. 1,2,3,5,8,13,21....! Errechnen kann man diese mittels... 1+2=3, 2+3=5, 3+5=8, 5+8=13 nach Formel also...

F(n+2)=F(n+1)+F(n)

Hierzu nun der Code....

/*Download:fibo.c*/ #include <stdio.h> long fibo(long n) { if(n) return (n<=2) ?n :fibo(n-2)+fibo(n-1); } int main() { long f,i=0; printf("Wieviele Fibonacci-Zahlen wollen sie ausgeben : "); scanf("%ld",&f); while(i++<f) printf("F(%ld) = %ld\n",i,fibo(i)); return 0; }

Jetzt wollen wir ein Programm schreiben zum Ermitteln des größten gemeinsamen Teiler zweier Zahlen. Natürlich wollen wir den rekursiven Weg gehen. Als erstes benötigen wir auch hier die Abbruchbedienung. Wir haben 3 Möglichkeiten zum errechnen des ggT 's zweier Zahlen....

ist Zahl1 == Zahl2 dann Ergebnis = Zahl1
ist Zahl1 > Zahl2 dann Ergebnis = ggT(Zahl1-Zahl2, Zahl2)
ist Zahl1 < Zahl2 dann Ergebnis = ggT(Zahl1, Zahl2-Zahl1)

Das Programm sieht somit folgendermaßen aus...

/*Download:ggt.c*/ #include <stdio.h> #define ulong unsigned long ulong ggt(ulong a, ulong b) { if(a==b) return a; else if(a<b) return ggt(a,b-a); else return ggt(a-b,b); } int main() { ulong a,b; printf("ggt = grösster gemeinsamer Teiler\n"); printf("Zahl 1: "); scanf("%lu",&a); printf("Zahl 2: "); scanf("%lu",&b); printf("Der ggT von %lu und %lu ist %lu\n",a,b,ggt(a,b)); return 0; }

Nehmen wir zum Beispiel an sie geben für Zahl1=10 und Zahl2=3 ein. Folgende Werte werden auf dem Stack gelegt bis unser Programm den ggT von 1 zurückgibt......

1,2-1
1,3-1
4-3,3
7-3,3
10-3,3

Den Iterative Lösungsvorgang will ich Ihnen auch hier nicht vorenthalten....

/*Download:ggti.c*/ #include <stdio.h> #define ulong unsigned long #define SWAP(a,b) {ulong c; c=a; a=b; b=c;} ulong ggt(ulong a, ulong b) { ulong count; if(a==b) return a; else if((a%b)==0) return b; else for(count=b; count>0; count--) { if(((a%count) + (b%count)) == 0) return count; } } int main() { ulong a,b; printf("ggt = grösster gemeinsamer Teiler\n"); printf("Zahl 1: "); scanf("%lu",&a); printf("Zahl 2: "); scanf("%lu",&b); if(a<b) SWAP(a,b); printf("Der ggT von %lu und %lu ist %lu\n",a,b,ggt(a,b)); return 0; }

Nun das war wohl zu einfach was? Ok wollen wir mal Versuchen den größten gemeinsamen Teiler von X-beliebig vielen Zahlen zu ermitteln. Die Schwierigkeit liegt bei diesem Beispiel aber nicht an der rekursiven Funktion sondern an der main - Funktion. Sie könnten wenn sie wollen unsere Funktion ggT wie wir sie eben geschrieben ohne zu verändern benutzen. Ich möchte Ihnen aber noch eine 2. Möglichkeit demonstrieren wie sie den ggT ermitteln können. Hier die Funktion...

ulong ggt(ulong a, ulong b)
{
 if(b==0)
   return a;
 return ggt(b, a%b);
}

Jetzt können sie langsam die Vorteile einer Rekursion erkennen. Diese rekursive Funktion erfüllt den gleichen Zweck wie die beiden Funktion ggT zuvor. Mit return ggt(b, a%b) rufen wir die Funktion erneut auf. Wenn a%b Null ergibt haben wir ja den ggT durch b an a übergeben. Nun will ich Ihnen die main - Funktion zum Ermitteln des ggT 's mehrerer Zahlen zu ermitteln....

/*Download:ggt2.c*/ #include <stdio.h> #define ulong unsigned long ulong ggt(ulong a, ulong b) { if(b==0) return a; return ggt(b, a%b); } int main() { ulong a,b; printf("ggt = grösster gemeinsamer Teiler(mit 0 beenden)\n"); printf("Zahl> "); scanf("%lu",&a); printf("Zahl> "); scanf("%lu",&b); a=ggt(a,b); while(1) { printf("Zahl> "); scanf("%lu",&b); if(b==0) break; a=ggt(a,b); } printf("-------->ggt = %lu\n",a); return 1; }

An dem Programm wurde nicht viel verändert. Es kam lediglich die while - Schleife hinzu die wir mit der Eingabe 0 beenden können. Wichtig ist das wir immer bei jedem Schleifendurchlauf den größten gemeinsamen Teiler an a und die neue Zahl an b übergeben. Somit wird immer der ggT aller Zahlen aktuallisiert.

Als letztes Beispiel will ich Ihnen zeigen wie wir eine rekursive Funktion zum Umwandeln von Dezimalzahlen in Dualzahlen realisieren. Zuerst will ich Ihnen noch schnell erklären wie aus der Zahl 10 die Dualzahl 1010 machen...

Solange unser Zahl ungleich Null ->
Zahl%2 ist gleich kein Rest dann 0; ist gleich Rest dann 1;
Zahl=Zahl/2

Nehmen wir wieder unsere Zahl 10....

10/2 = 5 kein Rest also 0
5/2 = 2 Rest 1 also 1
2/2 = 1 Rest 0 also 0
1/2 = 0 Rest 1 also 1

Somit liegen auf unserem Stack.....

1
0
1
0

...die in der Reihenfolge 1010 ausgegeben werden. Hierzu jetzt unser rekursive Funktion...

/*Download:dez2bin.c*/ #include <stdio.h> #define ulong unsigned long void dez2bin(ulong dez) { if(dez) { dez2bin(dez/2); printf("%lu",dez%2); } } int main() { ulong dezimal; printf("Dezimalzahl in Dualzahl konvertieren\n"); printf("Welche Zahl : "); scanf("%lu",&dezimal); printf("Dezimal = %lu Dual = ",dezimal); dez2bin(dezimal); return 0; }

Ich möchte es jetzt mit den Programmbeispielen belassen. Ich denke mal sie haben das Prinzip der Rekursionen nun verstanden. Ich muss aber zu diesen Programmbeispielen sagen das man mit einer Iterativen Lösung besser fährt als mit einer Rekursiven. Aber das ist auch Geschmackssache. In den nächsten Kapiteln werden wir die Rekursion Sinnvoll einsetzen.