Rekursion lösen, aber wie?

Suchst du einen Dummen, der dir deine Hausaufgaben macht? Schreibe deine Lösung hin, dann findet sich jemand der dich auf Fehler aufmerksam macht.

Das ist keine Hausaufgabe, sondern entstammt einem kürzlich online bei Spektrum der Wissenschaft erschienenen Artikel. Ich nehme an, der TO möchte einfach nur (aus Neugierde?) etwas den Artikel vertiefen und etwas mit der Formel praktisch herumspielen.

Also kein Grund, gleich im ersten Antwort-Post gleich so agressiv zu werden. Leute, würdet Ihr Jemandem bei einem Bier auch so rotzig daherkommen?

https://craftofcoding.wordpress.com/2021/06/02/recursion-mccarthys-91-function/

Peter T. schrieb:

Wie würde man diese Gleichung in C oder irgendeiner Phantasie-Programmiersprache angehen?

So, wie es da steht. Allerdings musst du selber herausfinden, ob die Rekursion auch mal abbricht, oder n so groß wird, daß es den Zahlenbereich deiner Variablen überschreitet, oder was da sonst noch so passieren kann.

Oliver

Peter T. schrieb:

Wie würde man diese Gleichung in C oder irgendeiner Phantasie-Programmiersprache angehen?

In "phantastischem" Haskell:

1

m n | n ≤ 100   = m (m (n + 11))

2

    | n > 100   = n - 10

Das ist die Originalformel mit etwas anders angeordneten Elementen. Da die zweite Bedingung (n > 100) alle verbleibenden Fälle abdeckt, kann man sie auch durch "otherwise" ersetzen:

1

m n | n ≤ 100     = m (m (n + 11))

2

    | otherwise   = n - 10

Thilo L. schrieb:

Das ist keine Hausaufgabe, sondern entstammt einem kürzlich online bei Spektrum der Wissenschaft erschienenen Artikel.

Die Formel ist eigentlich ziemlich unspektakulär. Wer sich dennoch dafür interessiert:

https://www.spektrum.de/kolumne/mccarthy-91-funktion-die-sinnlose-funktion-erfuellt-einen-zweck/2192409

Thilo L. schrieb:

gleich so agressiv zu werden.

Ich war zu keiner Zeit aggressiv. Es gehört zum guten Ton sich selbst erst mal etwas Mühe zu geben und nicht einfach eine Aufgabe hier rein zu posten die nach einer Hausaufgabe / Übung aussieht.

Siehe: Beitrag "Einheitlicher Umgang mit faulen Schülern etc.?"

Mit welchem Wert soll M starten?

Herbert B. schrieb:

Spektrum wird auch immer schlechter. Solchen trivialen Mist bauschen die zum Artikel auf, naja von nem Astronomen kann man auch nicht mehr erwarten.

Ich habe mich gefragt, warum überhaupt McCarthy, von dem die Formel stammt, solchen "trivialen Mist" veröffentlicht hat. Der Autor des Spektrum-Artikels hat es leider versäumt, mehr zu den Hintergründen zu erzählen.

Gerade entdeckt:

https://en.wikipedia.org/wiki/McCarthy_91_function

Da gibt es auch Code-Beispiele in verschiedenen Programmiersprachen.

Gerald K. schrieb:

Mit welchem Wert soll M starten?

Wie meinst du das? Das Argument der Funkton M kann ein beliebiges Element aus ℤ sein.

Für M ist 1 :

1

                                                                        #include <stdio.h>                                                                                          #include <stdlib.h>                                                                                         #include <string.h>                                                                                         #include <math.h>                                                                                           #include <inttypes.h>                                                                                                                                                                                                                                                                                                                                                                                                                           

2

3

int main(int argc, char* argv[])                                                                            {                                                                                                                   

4

  unsigned long long M=1;                                                                                                                                                                                                 

5

6

  for (int n=1;n<110;n++){                                                                                            

7

    if (n<=100)                                                                                                         

8

      M=M*(M*(n+11));                                                                                     

9

    else                                                                                                                

10

      M=(n-10);  

11

12

   printf("%d: %ld\t\t",n,M);                                                                          }

Herbert B. schrieb:

Wenn dich so ein Kinderkram schon geistig überfordert, lass die Finger vom Programmieren.

Oh, die Formel mag trivial erscheinen, aber die Lösung zwingt den "Mikrocontroller" dazu, zur Laufzeit emsig die Register auszutauschen!!! Wenn da mal nicht der Stackpointer überläuft!!! 😄 Ich bin das Problem gänzlich falsch angegangen, ich dachte, ich müsste ein Array aufmachen und jedes Element markieren als undefiniert oder berechnet. Die fertige Lösung ist da fast trivial, man (ich) sollte sie um Ausgaben ergänzen, so dass man sieht, was der uC macht!!!

1

function mc91(n : in integer) return integer is

2

begin

3

   if n > 100 then

4

      return (n - 10);

5

   else

6

      return mc91(mc91(n+11));

7

   end if;

8

end mc91;

Herbert B. schrieb:

Yalu X. schrieb:

In "phantastischem" Haskell:

Was hat das mit der Frage zu tun?

Es ist die (bzw. eine) Antwort darauf.

Willst du hier rumposen mit deinem akademisch-nutzlosen Sprachspielzeug?

Der Titel des Spektrum-Artikels lautet "Auch sinnlose Formeln haben ihren Wert". Für "sinnlose" Formeln ist doch ein "akademisch-nutzloses Sprachspielzeug", wie du es nennst, geradezu prädestiniert :)

Gerald K. schrieb:

Für M ist 1 :

Irgendwie hast Du ganz viele Sachen nicht verstanden.

Herbert B. schrieb:

Wenn dich so ein Kinderkram schon geistig überfordert, lass die Finger vom Programmieren.

https://www.brigitte.de/liebe/persoenlichkeit/psychologie--deshalb-halten-viele-menschen-sich-fuer-intelligenter--als-sie-sind-13536828.html

Herbert B. schrieb:

Yalu X. schrieb:

In "phantastischem" Haskell:

Was hat das mit der Frage zu tun? Willst du hier rumposen mit deinem akademisch-nutzlosen Sprachspielzeug?

So, damit du dich noch mehr ärgerst und dein Blutdruck steigt, mal sehen ob ich das noch in Erlang hin bekomme.

Jeweils mit einer Guard-Sequence:

1

-module(mcarthy91). 

2

-export([m/1]). 

3

4

m(N) when N =< 100 ->

5

   m(m(N + 11));

6

m(N) when N > 100 ->

7

   N - 10.

Eine Guard-Sequence eingespart:

1

-module(mcarthy91). 

2

-export([m/1]). 

3

4

m(N) when N =< 100 ->

5

   m(m(N + 11));

6

m(N) ->

7

   N - 10.

Peter T. schrieb:

Oh, die Formel mag trivial erscheinen, aber die Lösung zwingt den "Mikrocontroller" dazu, zur Laufzeit emsig die Register auszutauschen!!! Wenn da mal nicht der Stackpointer überläuft!!! 😄

Im oben verlinkten Wikipedia-Artikel wird auch eine endrekursive Variante der Funktion vorgestellt, die die meisten C-Compiler in eine einfache Schleife (ohne Rekursion) übersetzen.

Um die Rekursion zu lösen, muss man erst einmal die Rekursion lösen. Sonst wird das nichts.

Yalu X. schrieb:

≤

Ist das tatsächlich ein Operator in Haskell? Wie tippe ich den ein?

Peter T. schrieb:

https://www.brigitte.de/liebe/persoenlichkeit/psychologie--deshalb-halten-viele-menschen-sich-fuer-intelligenter--als-sie-sind-13536828.html

Dazu haben die Herren Dunning und Kruger sicher auch noch was zu sagen.

Hallo

Herbert B. schrieb:

Wenn dich so ein Kinderkram schon geistig überfordert, lass die Finger vom Programmieren.

Eine ziemlich arrogante und weltfremde Aussage. Geh mal in eine Fußgängerzone, einen Discounter, eine Werkstatt,... und frage was Rekursion ist....

Unter 100 Leuten werden dir vielleicht 2 Leute das beantworten können. (Und nein, der Campus einer technischen Hochschule oder die Halle, in der eine Matheolympiade stattfindet, sind nicht "zugelassen")

Besuche mal eine Schulklasse, die aus Kindern -ist ja Kinderkram (und nicht Jugendliche aus der Oberstufe eines Gymnasiums) besteht und zeige ihnen gerne zusammen mit der Lehrerin die Kinderkramformel...

Du wirst erstaunt sein festzustellen, dass diese Formel kein Kinderkram ist.

Ich würde dir raten, mal im normalen Leben anzukommen und ein wenig über deine Wortwahl und Bewertung deiner Mitmenschen nachzudenken.

Wer überhaupt nur andeutungsweise etwas mit solchen Formeln und Begriffen anfangen kann, wird ganz bestimmt nicht so leicht geistig überfordert und besitzt mehr mathematische Fähigkeiten als wohl 90% der Weltbevölkerung.

Rolf M. schrieb:

Yalu X. schrieb:

≤

Ist das tatsächlich ein Operator in Haskell?

Der Operator ist in Prelude.Unicode aus dem Package base-unicode-symbols definiert:

1

import Prelude.Unicode

Neben ≤ und ≥ kommt man damit u.a. in den Genuss der Operatoren ≠, ∧, ∨ ∈ und ∉ sowie der Variable π und der Datentypen ℤ und ℚ. In anderen Modulen sind noch weitere Unicode-Symbole definiert.

Wie tippe ich den ein?

In Vim:

Strg+K = <

In X (mit Compose-Key, bei mir ist das die rechte Strg-Taste):

<compose> < =

Herbert B. schrieb:

Wenn dich so ein Kinderkram schon geistig überfordert, lass die Finger vom Programmieren.

Wenn Dich der Umgang mit Dich nicht interessierenden Fragen überfordert, lass die Finger von diesem Forum!

Yalu X. schrieb:

Neben ≤ und ≥ kommt man damit u.a. in den Genuss der Operatoren ≠, ∧, ∨ ∈ und ∉ sowie der Variable π und der Datentypen ℤ und ℚ. In anderen Modulen sind noch weitere Unicode-Symbole definiert.

Das ist zwar irgendwie nett, wäre mir aber zu umständlich einzugeben.

Rolf M. schrieb:

Yalu X. schrieb:

Neben ≤ und ≥ kommt man damit u.a. in den Genuss der Operatoren ≠, ∧, ∨ ∈ und ∉ sowie der Variable π und der Datentypen ℤ und ℚ. In anderen Modulen sind noch weitere Unicode-Symbole definiert.

Das ist zwar irgendwie nett, wäre mir aber zu umständlich einzugeben.

Man muss diese Unicode-Zeichen nicht benutzen, und die wenigsten Leute tun dies. Auch ich bin grundsätzlich der Meinung, dass im Quelltext von Programmen außerhalb von String-Literalen ausschließlich ASCII-Zeichen verwendet werden sollten, also bspw. auch keine Umlaute in Identifiern.

Mir ging es bei der obigen Verwendung von ≤ hauptsächlich darum, eine möglichst große Ähnlichkeit zur Originalformel zu erreichen. Das war mir einen zusätzlichen Tastendruck (Strg-Taste vor dem <=) wert ;-)