Der 8. Teil der unendlichen Geschichte

 
Diesmal werden wir uns mit dem Thema Rekursion beschäftigen.
Und wir werden uns einen Taschenrechner programmieren, der sogar mit Variablen umgehen kann.
Er ist im Softwarearchiv unter "C-Kurs TR" mit dem dokumentierten Listing zu finden.
Da der Taschenrechner etwas umfangreicher ist, werde ich nur auf die Aspekte eingehen, die neu sind
Für diesen Teil ist es die...

 

 
Rekursion

 

Rekursionen sind Zahlenfolgen, bei denen ein Zahlenelement durch einen Vorgänger oder Nachfolger bestimmt wird.


Wenn man eine Vorschrift zu der Bildung einer Zahlenfolge hat, die wie folgt aussieht
 

A 1 = 1 

A n+1 = A n + 1

erhält man die Zahlenfolge
 

1 , 2 , 3 , ...

Das Ganze kann man nun auch anders herum durchführen:
 

A n = A n+1 - 1

Abbruchbedingung:
 

A 1 = 1
Die Zahlenfolge bleibt die selbe, nur fangen wir bei einer Anfangszahl, z.B. 3 , an und bilden die Vorgänger.
Damit das nicht ewig weitergeht, müssen wir eine Abbruchbedingung angeben, wo wir aufhören können.
Die ist in unserem Fall A 1 , da dies unser Startwert in der zu bildenden Zahlenfolge ist.
Rekursionen haben den Vorteil, das sie durch ihre einfachen Zuweisungsvorschrift, jedem folgendem Element einen Wert zuweisen können und relativ klein sind.
Das wird am Besten an einem kleinen Beispiel klar.

 

 
 
 
Fakultätsberechnung 

In der Mathematik bedeutet die Fakultät folgendes:
 

n! = 1 * 2 * 3 * .. * n

n! spricht man n-Fakultät.

Es werden also alle ganzen Zahlen bis n miteinander multipliziert.


Wenn wir nun ein rekursives Programm in C schreiben, könnte es z.B. so aussehen
 

#include <stdio.h> 
double fakultaet ( int );
 
double fakultaet ( int n ) 
    if (n) return n * fakultaet ( n - 1 ); 
    return 1; 
}
 
void main ( void ) 
    int zahl; 
    printf("\nBitte geben sie eine Zahl ein : "); 
    scanf ("%d",&zahl); 
    printf ("\n\n%d Fakultät = %l",zahl,fakultaet(zahl)); 
}
Wir fangen hier bei der Zahl n an.


Um zu verdeutlichen, wie das Programm arbeitet, wieder einen mathematischen Abstecher.
 

4! 
    = 3! * 4

    = 2! * 3 * 4

    = 1! * 2 * 3 * 4

    = 0! * 1 * 2 * 3 * 4

Bei Null setzen wir unsere Abbruchbedingung. Es ist mathematisch definiert: 0! = 1.

Und genau nach dem oberen Arbeitsschema arbeitet auch unser Programm. Es bekommt als Übergabewert die Zahl n, deren Fakultät berechnet werden soll und multipliziert diese mit dem Wert der Fakultät von n-1 .
das geschieht solange, bis n=0 ist.
Wie wir schon aus den vergangenen Kursen wissen, wird in einer if - Bedingung geprüft, ob der Wert wahr ist.
C hat die tolle Angewohnheit alle Werte ungleich 0 als Wahr anzusehen.
Daher reicht also die verwendete if - Bedingung.

 

 

Dieses ist zwar ein sehr kurzes aber immens wichtiges Kapitel in C !
Es ist nicht leicht zu verstehen, aber man kann sich sehr viel Arbeit ersparen.
 


Diesmal gibt es keine Übungsaufgaben, da der nächste Teil schon in den Startlöchern steht ;-)
 
 
 
 
 
...das Obligatorische

Autor: Sebastian Cyris PCDBascht@aol.com

Dieser C-Kurs dient nur zu Lehrzwecken! Eine Vervielfältigung ist ohne vorherige Absprache mit dem Autor verboten! Die verwendete Software unterliegt der GPL und unterliegt der Software beiliegenden Bestimmungen zu deren Nutzung! Jede weitere Lizenzbestimmung die der benutzten Software beiliegt, ist zu beachten!