1. Foren
  2. Kommentare
  3. Wirtschaft-Forum
  4. Alle Kommentare zum Artikel
  5. › IT-Geschichte: Unix - ein…

GNU Not Unix :D

Neue Foren im Freiraum! Raumfahrt und freie Software haben jetzt einen Platz, die Games tummeln sich jetzt alle in einem Forum.
  1. Thema

Neues Thema


  1. GNU Not Unix :D

    Autor: derLaie 22.06.20 - 12:23

    Die Rekursion.. es macht meistens wenig Sinn und verschlingt unnötige Ressourcen. Rekursive Lösungswege zu finden macht aber trotzdem Spaß und ist gutes Gehirnjogging! Den Anfang macht die Fakultät!

  2. Re: GNU Not Unix :D

    Autor: George99 22.06.20 - 15:09

    Klar kann man jede Rekursion auch in Schleifen umwandeln und die benötigten lokalen Variablen in Arrays, deren Index dann der früheren Rekursiontiefe entspricht. Viele Resourcen spart man dadurch aber auch nicht. Gut, die Rücksprungadresse muss nicht mehr auf dem Stack gesichert werden...
    Ich hatte mal rekursiv programmierte Backtracking-Suchalgorithmen in Schleifenform umgewandelt, um eine höhere Geschwindigkeit zu erzielen, letztendlich aber keinen erreicht. (Hatte aber trotzdem Spaß gemacht!)

    Rekursive Algorithmen haben den Vorteil einfach zu programmieren und zu verstehen zu sein, was dann auch hilft, Fehler zu vermeiden. Türme von Hanoi rekursiv? Pillepalle, schafft jeder Zehnjährige. Ohne Rekursion und auch ohne bloß in Schleifen und Arrays umgebaute Rekursion? Gehirnschmelze!

  3. Re: GNU Not Unix :D

    Autor: Graveangel 22.06.20 - 15:56

    George99 schrieb:
    --------------------------------------------------------------------------------
    > Klar kann man jede Rekursion auch in Schleifen umwandeln und die benötigten
    > lokalen Variablen in Arrays, deren Index dann der früheren Rekursiontiefe
    > entspricht. Viele Resourcen spart man dadurch aber auch nicht. Gut, die
    > Rücksprungadresse muss nicht mehr auf dem Stack gesichert werden...
    > Ich hatte mal rekursiv programmierte Backtracking-Suchalgorithmen in
    > Schleifenform umgewandelt, um eine höhere Geschwindigkeit zu erzielen,
    > letztendlich aber keinen erreicht. (Hatte aber trotzdem Spaß gemacht!)
    >
    > Rekursive Algorithmen haben den Vorteil einfach zu programmieren und zu
    > verstehen zu sein, was dann auch hilft, Fehler zu vermeiden. Türme von
    > Hanoi rekursiv? Pillepalle, schafft jeder Zehnjährige. Ohne Rekursion und
    > auch ohne bloß in Schleifen und Arrays umgebaute Rekursion? Gehirnschmelze!


    Ist es nicht so, dass fast alles, was in rekursion geht, auch in iteration geht?
    Es gibt meines Wissens nach Ausnahmen.

    Viele meiner Kollegen finden rekursion jedoch komplexer als Iteration.
    Ich finde, dass das sehr drauf ankommt, was man bearbeiten will.
    Spätestens bei Bäumen finde ich iteration mehr als suboptimal.

  4. Re: GNU Not Unix :D

    Autor: lestard 22.06.20 - 16:25

    Graveangel schrieb:
    --------------------------------------------------------------------------------
    > Ist es nicht so, dass fast alles, was in rekursion geht, auch in iteration
    > geht?
    > Es gibt meines Wissens nach Ausnahmen.

    Da man Rekursion mit Iteration simulieren kann, lässt sich auch jedes rekursive Problem mit Iteration lösen. Unterschiedlich ist nur die kognitive Komplexität und eventuell die Ausführungsgeschwindigkeit, wenn man den Code auf einem Rechner ausführt.

    > Viele meiner Kollegen finden rekursion jedoch komplexer als Iteration.
    > Ich finde, dass das sehr drauf ankommt, was man bearbeiten will.
    > Spätestens bei Bäumen finde ich iteration mehr als suboptimal.

    Ich glaube es ist vor allem Gewohnheitssache und hängt auch von der Programmiersprache ab. In Java sind z.B. die Möglichkeiten für Rekursion stark begrenzt, weshalb es da selten genutzt wird und Java-Programmierer daher vermutlich eher Iteration gewöhnt sind.

  5. Re: GNU Not Unix :D

    Autor: wurstdings 22.06.20 - 16:26

    Graveangel schrieb:
    --------------------------------------------------------------------------------
    > Ist es nicht so, dass fast alles, was in rekursion geht, auch in iteration
    > geht?
    Alles geht auch als Iteration, ich entsinne mich grob, das wir dazu sogar mal nen Beweis im Infostudium gebastelt hatten.
    > Es gibt meines Wissens nach Ausnahmen.
    Die da wären?
    > Viele meiner Kollegen finden rekursion jedoch komplexer als Iteration.
    Ja Viele hatten das Rekursionskonzept nicht kapiert, aber so richtig verstehen konnt ich das nie, weil eigentlich ist es sehr einfach.
    > Ich finde, dass das sehr drauf ankommt, was man bearbeiten will.
    Logisch, richtiges Werkzeug fürs jeweilige Problem. Rekursion ist prima, wenn man ein und das Selbe mehrmals anwenden muss. Und man muss vorher wissen, das die Rekursionstiefe durch den Stack begrenzt ist.
    > Spätestens bei Bäumen finde ich iteration mehr als suboptimal.
    Das klingt sehr unscharf, was genau machst du mit den Bäumen und was sind das für Bäume?

  6. Re: GNU Not Unix :D

    Autor: George99 22.06.20 - 16:52

    Graveangel schrieb:
    --------------------------------------------------------------------------------

    > Ist es nicht so, dass fast alles, was in rekursion geht, auch in iteration
    > geht?

    Wie die anderen Foristen auch schon schrieben: Man kann jede rekursive Funktion praktisch automatisiert in eine iterative Funktion umwandeln, die letztendlich die Rekursion aber nur in Schleifen nachbaut und den Stack durch Array-Variablen ersetzt. Anders gesagt: Man gewinnt nichts, der Code wird nur unleserlicher.

    > Viele meiner Kollegen finden rekursion jedoch komplexer als Iteration.

    Tatsächlich ist es doch genau umgekehrt. Bspw. eine fill() Funktion in einer Bildverarbeitung.
    Rein rekursiv könnte ich die so in Pseudocode schreiben:

    fill(x, y){
    if(x and y in allowed range){
    if(Pixel[x][y] is blank){
    drawpixel(x,y)
    fill(x-1,y) fill(x+1,y) fill(x,y-1) fill(x,y+1)
    }
    }
    }

    Kurz und knapp, sofort verständlich und fehlerfrei, aber leider durch die ausuferne Rekursion extrem langsam und der Stack wird bei zu großer freier Fläche auch abkacken.

    Iterativ lässt sich das deutlich schneller lösen, indem man nicht einzelne Pixel zeichnet, sondern ganze Linien findet oder gar Rechtecke, aber den Code dann zu verstehen und zu debuggen ist, wie ich oben schon schrieb, Gehirnschmelze :)

  7. Re: GNU Not Unix :D

    Autor: Quantium40 22.06.20 - 16:53

    derLaie schrieb:
    > Die Rekursion.. es macht meistens wenig Sinn und verschlingt unnötige
    > Ressourcen.

    Das hängt doch erheblich von der gewünschten Funktionalität ab.
    Rekursive Sortiertverfahren sind z.B. sehr schnell und Ressourcensparend.
    Das rekursive Errechnen von Folgegliedern der Fibonacci-Folge hingegen, die gerne als Beispiel für Rekursion im Unterricht genutzt wird, ist hingegen ein gutes Beispiel dafür, wo Rekursion fehl am Platz ist.

  8. Re: GNU Not Unix :D

    Autor: tyraz 22.06.20 - 20:59

    wurstdings schrieb:
    --------------------------------------------------------------------------------
    > Graveangel schrieb:
    > ---------------------------------------------------------------------------
    > -----
    > > Ist es nicht so, dass fast alles, was in rekursion geht, auch in
    > iteration
    > > geht?
    > Alles geht auch als Iteration, ich entsinne mich grob, das wir dazu sogar
    > mal nen Beweis im Infostudium gebastelt hatten.
    > > Es gibt meines Wissens nach Ausnahmen.
    > Die da wären?

    Möge mich bitte jemand korrigieren, falls ich falsch liege, aber ich meine mich erinnern zu können, dass
    - jede Rekursion in eine Iteration umgewandelt werden kann,
    - jedoch nicht jede Iteration in eine Rekursion.

    Schlimm genug, den Beweis bekomme ich nach all den Jahren nicht mal so eben hin! :-(



    1 mal bearbeitet, zuletzt am 22.06.20 21:01 durch tyraz.

  9. Re: GNU Not Unix :D

    Autor: Oktavian 22.06.20 - 20:59

    > Ist es nicht so, dass fast alles, was in rekursion geht, auch in iteration
    > geht?

    Es geht alles rein iterativ. Die Beweisskizze ist relativ einfach:

    Die Turing-Maschine (Bandmaschine) kennt keine Rekursion.
    Die Turing-Maschine kann jedes berechenbare Problem lösen.

    Ergo kann man jedes berechenbare Problem ohne Rekursion lösen.


    Man kann es auch so lösen:
    Die Turing-Maschine (Bandmaschine) kennt keine Rekursion.
    Die uRekursion (Mü-Rekursion) kennt nur Rekursion und nichts anderes.
    Die Turing-Maschine und die uRekursion sind gleichmächtig, können also jedes berechenbare Problem lösen.

    Ergo kann man jedes berechenbare Problem sowohl rekursiv als auch nicht-rekursiv lösen.


    Im einfachsten Fall simuliert man sich halt selbt im Speicher einen Stack und bastelt die Rekursion in eine Schleife. Das war früher gelegentlich nötig, da der Stack eine recht begrenzte Größe hatte und bei zu tiefer Rekursion volllief (Stack Overflow). Im Heap war immer reichlich Speicher.

    > Es gibt meines Wissens nach Ausnahmen.

    Nein, viele Probleme sind rekursiv aber einfach eleganter zu lösen. Einen Quicksort iterativ auszuprogrammieren ist einfach unelegant, rekursiv sieht man schnell, was passiert.

    > Viele meiner Kollegen finden rekursion jedoch komplexer als Iteration.

    Ach, wenn Rekursion schon als komplex gilt...

    > Ich finde, dass das sehr drauf ankommt, was man bearbeiten will.
    > Spätestens bei Bäumen finde ich iteration mehr als suboptimal.

    Graphenalgorithmen sind eben das Musterbeispiel der Rekursion schlechthin.

  10. Re: GNU Not Unix :D

    Autor: Oktavian 22.06.20 - 21:02

    > - jedoch nicht jede Iteration in eine Rekursion.

    Doch, auch das geht. Im schlimmsten Fall entartet es halt zu einer Rekursion, die sich gar nicht selbst wieder aufruft.

    Da jedes berechenbare Problem sowohl durch eine Turing-Maschine (nicht rekursiv) als auch durch uRekursion (mü-Rekursion, partiell rekursive Funktionen) lösbar ist und beide Theoreme gleich mächtig sind, geht im Prinzip immer beides.

    In der Praxis hat du natürlich recht, manches schreit nach Rekursion, bei anderem verbietet es sich. Aber man kann jedes Problem auch auf die andere Art lösen.

  11. Re: GNU Not Unix :D

    Autor: tyraz 22.06.20 - 21:12

    Oktavian schrieb:
    --------------------------------------------------------------------------------

    > In der Praxis hat du natürlich recht, manches schreit nach Rekursion, bei
    > anderem verbietet es sich. Aber man kann jedes Problem auch auf die andere
    > Art lösen.

    Sehr gut, Danke für die Beweisskizzen und Auffrischung!



    1 mal bearbeitet, zuletzt am 22.06.20 21:17 durch tyraz.

  1. Thema

Neues Thema


Um zu kommentieren, loggen Sie sich bitte ein oder registrieren Sie sich. Sie müssen ausserdem in Ihrem Account-Profil unter Forum einen Nutzernamen vergeben haben. Zum Login

Stellenmarkt
  1. Java Software Developer (w/m/d) Customer Service
    SSI SCHÄFER Automation GmbH, Giebelstadt, Dortmund, Münster, Oberviechtach
  2. Softwareentwickler Healthcare IT (gn*)
    medavis GmbH, Karlsruhe
  3. Informatiker*in (m/w/d) Schwerpunkt Gesundheitstelematik
    KBV Kassenärztliche Bundesvereinigung, Berlin
  4. Datenschutzkoordinator (m/w/d) - IT
    HSBC, Düsseldorf

Detailsuche


Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Hardware-Angebote
  1. 499,99€
  2. 399,99€


Haben wir etwas übersehen?

E-Mail an news@golem.de


Hyperschallwaffen: China testet Flugzeugträger-Killer in der Wüste
Hyperschallwaffen
China testet Flugzeugträger-Killer in der Wüste

Die Volksbefreiungsarmee schießt im Uiguren-Gebiet auf Attrappen von Kriegsschiffen. Erprobt wird die Fähigkeit, gegnerischen Flotten einen empfindlichen Erstschlag zu versetzen.
Ein Bericht von Matthias Monroy

  1. Stormcaster-DX Lasergerät für Drohnen-Montage kommt mit Zielverfolgung
  2. Hensoldt Deutsche Jammer sollen russische Luftabwehr stören können
  3. Cybersicherheit Rechenzentren-Projekt der Schweizer Armee "ungenügend"

Astronomie: Bilder vom schwarzen Loch im Zentrum der Milchstraße
Astronomie
Bilder vom schwarzen Loch im Zentrum der Milchstraße

Das Event Horizon Telescope hat keine Beobachtungen in fernen Galaxien gemacht, sondern in unserer Nachbarschaft. Trotzdem ist es kompliziert.
Von Frank Wunderlich-Pfeiffer

  1. Automatik-Teleskop Stellina im Test Ist es wirklich so einfach?
  2. Astronomie Möglicher Planet Neun entdeckt
  3. Seti Doch kein Signal von Proxima Centauri

Open Source: Interaktives Rechnen mit Jupyter-Notebooks
Open Source
Interaktives Rechnen mit Jupyter-Notebooks

Ob der Test einer Signalverarbeitungs-Bibliothek oder die Hardware-Synthese für einen FPGA: Im Jupyterhub klappt das via Cloud.
Eine Anleitung von Martin Strubel

  1. Software 20 Dinge, die ich in 20 Jahren als Entwickler gelernt habe
  2. Programmierung Githubs Copilot produziert Bugs und Sicherheitslücken