Wann ist eine Funktion primitiv rekursiv?
Eine Funktion f : Nk → N ist primitiv rekursiv, wenn sie der folgenden induktiven Definition genügt: Jede konstante Funktion f(x1,…,xk) = c ∈ N ist primitiv rekursiv. i (x1,…,xk) = xi sind primitiv rekursiv. Die Nachfolgerfunktion succ(x) = x + 1 ist primitiv rekursiv.
Wie funktioniert die Ackermann Funktion?
Die Ackermannfunktion definiert man üblicherweise rekursiv, d. h. man macht für einige Anfangswerte explizite Angaben und gibt eine Anleitung (das Rekursionsschema), wie man weitere Funktionswerte aus den bereits berechneten erhält.
Was ist bei der rekursiven Programmierung wichtig?
Wichtig bei der rekursiven Programmierung ist eine Abbruchbedingung in dieser Funktion, weil sich das rekursive Programm sonst theoretisch unendlich oft selbst aufrufen würde. Rekursive Programmierung kann unter anderem in prozeduralen und objektorientierten Programmiersprachen angewandt werden.
Wie wird eine Rekursion implementiert?
Rekursion wird in der Regel durch einen Stack implementiert, der die Rücksprungadressen, aber auch alle lokalen Variablen und eventuell Funktionsergebnisse aufnimmt. Würde man, wie im obenstehenden Beispiel, die Fakultät von 4 berechnen, so würde jeder Aufruf folgende Informationen auf den Stack legen:
Wie lassen sich rekursiven Algorithmen implementieren?
Alle rekursiven Algorithmen lassen sich jedoch auch durch iterative Programmierung implementieren und umgekehrt. Man hätte die Fakultät auch so implementieren können: Hierbei gilt die Regel, dass für einfache Probleme eine iterative Implementierung häufig effizienter ist.
Welche Programmiersprachen sind rekursiv?
Nicht alle höheren Programmiersprachen lassen rekursive Aufrufe zu. Ein Beispiel dazu ist Fortran. Andere Programmiersprachen sind dagegen grundsätzlich rekursiv (wie z. B. Prolog ). Solche rekursiven Programmiersprachen und auch andere Sprachen wie z. B. Scheme setzen die Rekursion meistens effizient um.