Rekursion lösen, aber wie?

[Peter T. (Firma: schon lange insolvent) (wonderboy8051)]

Hi, ich tue mich mit Rekursion schwer. Wie würde man diese Gleichung in 
C oder irgendeiner Phantasie-Programmiersprache angehen?

[Udo S. (urschmitt)]

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

[Thilo L. (bc107)]

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?

[Mario M. (thelonging)]

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

[Oliver S. (oliverso)]

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

[Yalu X. (yalu) (Moderator)]

Peter T. schrieb:
> Wie würde man diese Gleichung in C oder irgendeiner
> Phantasie-Programmiersprache angehen?

In "phantastischem" Haskell:

m n | n ≤ 100   = m (m (n + 11))
    | 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:

m n | n ≤ 100     = m (m (n + 11))
    | 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

[Herbert B. (Gast)]

Yalu X. schrieb:
> https://www.spektrum.de/kolumne/mccarthy-91-funktion-die-sinn...

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

Spektrum = neues PM Magazin

[Udo S. (urschmitt)]

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.?"

[Herbert B. (Gast)]

Yalu X. schrieb:
> In "phantastischem" Haskell:
Was hat das mit der Frage zu tun? Willst du hier rumposen mit deinem 
akademisch-nutzlosen Sprachspielzeug?

[Gerald K. (geku)]

Mit welchem Wert soll M starten?

[Yalu X. (yalu) (Moderator)]

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.

[Yalu X. (yalu) (Moderator)]

Gerald K. schrieb:
> Mit welchem Wert soll M starten?

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

[Gerald K. (geku)]

Für M ist 1 :

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

int main(int argc, char* argv[])                                                                            {                                                                                                                   
  unsigned long long M=1;                                                                                                                                                                                                 
 
  for (int n=1;n<110;n++){                                                                                            
    if (n<=100)                                                                                                         
      M=M*(M*(n+11));                                                                                     
    else                                                                                                                
      M=(n-10);  
                                                                                         
   printf("%d: %ld\t\t",n,M);                                                                          }

[Peter T. (Firma: schon lange insolvent) (wonderboy8051)]

Herbert B. schrieb im Beitrag #7526476:
> 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!!!

function mc91(n : in integer) return integer is
begin
   if n > 100 then
      return (n - 10);
   else
      return mc91(mc91(n+11));
   end if;
end mc91;

[Yalu X. (yalu) (Moderator)]

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 :)

[Michael L. (nanu)]

Gerald K. schrieb:
> Für M ist 1 :

Irgendwie hast Du ganz viele Sachen nicht verstanden.

[Peter T. (Firma: schon lange insolvent) (wonderboy8051)]

Herbert B. schrieb im Beitrag #7526476:
> 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

[Hannes J. (pnuebergang)]

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:

-module(mcarthy91). 
-export([m/1]). 

m(N) when N =< 100 ->
   m(m(N + 11));
m(N) when N > 100 ->
   N - 10.

Eine Guard-Sequence eingespart:

-module(mcarthy91). 
-export([m/1]). 

m(N) when N =< 100 ->
   m(m(N + 11));
m(N) ->
   N - 10.

[Yalu X. (yalu) (Moderator)]

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.

[MaWin O. (mawin_original)]

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

[Rolf M. (rmagnus)]

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.

[Dieterich (einermehr)]

Hallo

Herbert B. schrieb im Beitrag #7526476:
> 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.

[Yalu X. (yalu) (Moderator)]

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:

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> < =

[M.A. S. (mse2)]

Herbert B. schrieb im Beitrag #7526476:
> 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!

[Rolf M. (rmagnus)]

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.

[Yalu X. (yalu) (Moderator)]

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 ;-)