Wozu dient die McCarthy-Funktion?

Hallo ihr Lieben!

Wir sollen im Informatik Unterricht ein Programm schreiben(JAVA), das die Funktionswerte der McCarthy-Funktion rekursiv berechnet. Mein Problem jedoch ist, dass ich nicht verstehe, was genau diese Funktion ,,tun soll"?! Beziehungsweise wo ich drüber stolpere ist das f(f(.. .

Hier noch einmal die Funktion:

f(n)={n-10 //falls n>100 sonst f(f(n+11))

Ich hoffe mir kann geholfen werden! Und danke schon einmal im Voraus.

Answer 1

[sic84]

Hallo,

rein mathematisch betrachtet ist die Funktion recht uninteressant. Ist allerdings ein sehr schönes Beispiel für Rekursion. Je kleiner der Wert 'n' ist, desto öfter muss mccarthy sich selbst aufrufen nur am ende herauszufinden, dass das Resultat immer "91" ist. Vielleicht mal ein Aufruf Schrittweise durchgegangen:

Wir rufen die Funktion mit dem Wert 88 für "n" auf:

mccarthy(88)

Wir springen in die Funktion.

1. Ist 88 > 100? = NEIN

   Also rufen wir die mccarthy Funktion erneut auf. Als Parameter bekommt die Funktion das Resultat eines weiteren mccarthy auffrufes mit dem Parameter + 11, also:

2. mccarthy(mccarthy(n+11))

   zuerst wird jetzt die fett markierte Funktion aufgerufen, also mccarthy(n+11) n hat hier noch immer noch den wert 88, darauf werden 11 addiert, also sieht es in der nächsten Funktion so aus:

3. Ist 99 (n+11) > 100? = NEIN

   Nun wird wieder die Funktion wie oben aufgerufen:

4. mccarthy(mccarthy(n+11))

   'n' hat nun den wert 99, wieder wird die Fett makierte funktion zuerst aufgerufen

5. Ist 110 (n+11) > 100? = JA

   Also 11 von n abziehen und funktion beenden

6. n - 11

   jetzt springen wir quasi zu punkt 4 zurück und es wird der äußere teil der funktion aufgerufen mit dem paramter 99 (aus punkt 6) also

7. mccarthy(mccarthy(n+11)) bzw mit dem ergebnis von mccarthy(n+11) wäre es dann mccarty(99)

Und so geht es dann immer weiter.. das ist ein schönes Beispiel für doppelte rekursion und anfangs bestimmt schwer zu verstehen. Ich denke der einzige Sinn darin ist, rekursion zu verstehen, es wird auch McCarthy 91 genannt, weil als ergebnis immer 91 herauskommt.

Ich hoffe, ich konnte es etwas verständlich rüber bringen. MfG

Comments

[Franz1957]

In der engl. Wikipedia... http://en.wikipedia.org/wiki/McCarthy_91_function ...heißt es, daß McCarthy die Funktion als Beispiel für formale Verifikation verwendete, d.h., um zu zeigen, wie man streng logisch beweisen kann, daß das Programm tatsächlich das tut, was man meint. Diese 91er-Funktion wurde dafür gewählt, weil sie sich so kompliziert verhält.

Answer 2

[MCGTV]

Hier ist eine Methode zum Thema Fakultät!

public class McCarthyFunktion { protected static int fac(int n) { if (n == 0) { return 1; }

    else
    {
        return n * McCarthyFunktion.fac(n-1);
    }
}
    
    public static void main(String[] args)
    {
        System.out.println(McCarthyFunktion.fac(5)); //120
    }

}

In Java benötigs Du in diesem Falle ein if-else Statement. Dies Ist mit einer McCarthy-Funktion gleichzusetzen!

Ich hoffe, ich konnte Dir helfen!