Aus ProgrammingWiki

Klasse der primitiv rekursiven Funktionen

Aufgabe

Entwickeln Sie einen "Werkzeugkasten" für primitiv rekursive Funktionen. Es wird erwartet, dass aus primitiv rekursiven (Basis-)Funktionen unter Verwendung der Kompositionstechniken (Substitution und primitive Rekursion) neue primitiv rekursive Funktionen generiert werden. Diese sollen verwendbar sein.

Lösung

Zur Lösung dieses Problems haben wir uns für die Verwendung der Programmiersprache Java entschieden. Da wir mit n-stelligen Funktionen arbeiten, erschien uns als einfachste Lösung, die Erstellung eines Interfaces für eine Klasse mit nur einer Funktion, die ein int-Array erwartet und einen int-Wert zurückgibt.

public interface RecFunc { public int calc(int[] l); }

Für die Basisfunktionen haben wir statische Methoden bereitgestellt, die die entsprechende Funktion zurückgeben. Im Falle der Nachfolgerfunktion S sieht das folgendermaßen aus:

public static RecFunc S(){ return new RecFunc(){ @Override public int calc(int[] l) { return l[0] + 1; } }; }

Die Methode besitzt natürlich nur einen Eingabeparameter, folglich wird auch nur das erste Element des Arrays benötigt. Bei der Nullfunktion haben wir uns entschieden, diese so zu erweitern, dass jede beliebige Konstantenfunktion C zurückgegeben werden kann. Dazu wurde der statische Aufruf einfach entsprechend parametrisiert.

public static RecFunc C(final int i){ return new RecFunc(){ @Override public int calc(int[] l) { return i; } }; }

Das war ebenso bei der Projektionsfunktion U nötig, da zusätzlich zur Liste von Eingabeparametern zusätzlich der entsprechende Index angegeben werden musste. Hierbei war darauf zu achten, dass der Index bei einem Array in Java 0-basiert ist und somit der Index entsprechend angepasst werden musste.

public static RecFunc U(final int i){ return new RecFunc(){ @Override public int calc(int[] l) { return l[i-1]; } }; }

Nun da die Basisfunktionen definiert waren, konnten auch Substitution und Rekursion implementiert werden. Zur Substitution gibt es dabei nicht viel zu beachten. Man spricht auch von einer Verkettung von Funktionen. Das wurde wie folgt realisiert:

public static RecFunc substituiere(final RecFunc f, final RecFunc[] gList){ return new RecFunc(){ @Override public int calc(int[] l) { int[] fValues = new int[gList.length]; for(int i = 0 ; i < gList.length ; i++){ fValues[i] = gList[i].calc(l); } return f.calc(fValues); } }; }

Die Ergebnisse der Operationen angewandt auf l dienen als Eingabeparameter für die Funktion f.

Die Umsetzung der Rekursion war hier schon etwas komplizierter. Durch strikte Umsetzung der mathematischen Notation, kamen wir schließlich auf folgende Lösung:

public static RecFunc primRec(final RecFunc f, final RecFunc g){ return new RecFunc(){ @Override public int calc(int[] l) { if(l[0]==0){ return f.calc(Arrays.copyOfRange(l, 1, l.length)); } int[] newHValues = Arrays.copyOf(l, l.length); newHValues[0] = newHValues[0]-1; int[] newGValues = new int[l.length + 1]; newGValues[0] = newHValues[0]; newGValues[1] = this.calc(newHValues); for(int i = 1 ; i < newHValues.length ; i++){ newGValues[i+1] = newHValues[i]; } return g.calc(newGValues); } }; }

Nun da wir den Werkzeugkasten mit allen Grundbausteinen gefüllt haben, können nun damit alle primitiv rekursiven Funktionen erzeugt werden. In folgendem Beispiel ist dazu die Erzeugung einer Additions- und einer Multiplikationsfunktion angegeben:

//Funktion die das zweite Element aus einer Liste inkrementiert: RecFunc addHelper = substituiere(S(), new RecFunc[]{U(2)}); //Funktion zur Addition zweier Zahlen: RecFunc add = primRec(U(1), addHelper); //Beispielaufruf: System.out.println(add.calc(new int[]{7,3})); //Funktion, die das zweite und dritte Element einer Liste addiert: RecFunc multHelper = substituiere(recTest,new RecFunc[]{U(2),U(3)}); //Funktion zur Multiplikation zweier Zahlen: RecFunc mult = primRec(C(0), multHelper); //Beispielaufruf: System.out.println(mult.calc(new int[]{5,4}));