Was ist so schwierig an Zeigern / Rekursionen? [geschlossen]

In den Gefahren von Java-Schulen diskutiert Joel seine Erfahrungen bei Penn und die Schwierigkeit von "Segmentierungsfehlern". Er sagt

[Segfaults sind schwierig, bis Sie] "Atmen Sie tief ein und versuchen Sie wirklich, Ihren Geist zu zwingen, gleichzeitig auf zwei verschiedenen Abstraktionsebenen zu arbeiten."

Angesichts einer Liste mit häufigen Ursachen für Störungen verstehe ich nicht, wie wir auf zwei Abstraktionsebenen arbeiten müssen.

Aus irgendeinem Grund hält Joel diese Konzepte für den Kern der Abstraktionsfähigkeit eines Programmierers. Ich möchte nicht zu viel annehmen. Was ist also so schwierig an Zeigern / Rekursionen? Beispiele wären nett.

Ich bemerkte zuerst, dass Zeiger und Rekursion im College schwierig waren. Ich hatte ein paar typische Kurse im ersten Jahr belegt (einer war C und Assembler, der andere war im Schema). Beide Kurse begannen mit Hunderten von Studenten, von denen viele über jahrelange Programmiererfahrung auf Highschool-Niveau verfügten (damals in der Regel BASIC und Pascal). Sobald jedoch im C-Kurs Hinweise und im Schema-Kurs eine Rekursion eingeführt wurden, war eine große Anzahl von Schülern - vielleicht sogar eine Mehrheit - völlig verblüfft. Dies waren Kinder, die zuvor eine Menge Code geschrieben hatten und überhaupt keine Probleme hatten, aber wenn sie Zeiger und Rekursionen trafen, stießen sie auch in Bezug auf ihre kognitiven Fähigkeiten an eine Wand.

Meine Hypothese ist, dass Zeiger und Rekursion insofern gleich sind, als Sie zwei Abstraktionsebenen gleichzeitig im Kopf behalten müssen. Es gibt etwas an der Abstraktion auf mehreren Ebenen, das eine Art geistige Begabung erfordert, die manche Menschen wahrscheinlich niemals haben werden.

• Bei Zeigern sind die "zwei Abstraktionsebenen" "Daten, Adresse von Daten, Adresse von Adresse von Daten usw." oder das, was wir traditionell "Wert vs. Referenz" nennen. Für den ungeübten Schüler ist es sehr schwer, den Unterschied zwischen der Adresse von x und x selbst zu erkennen .
• Mit der Rekursion verstehen die "zwei Abstraktionsebenen", wie es möglich ist, dass eine Funktion sich selbst aufruft. Ein rekursiver Algorithmus ist manchmal das, was die Leute "Programmieren durch Wunschdenken" nennen, und es ist sehr, sehr unnatürlich, sich einen Algorithmus als "Basisfall + induktiver Fall" anstelle der natürlicheren "Liste von Schritten vorzustellen, die Sie befolgen, um ein Problem zu lösen . " Für den ungeübten Schüler, der einen rekursiven Algorithmus betrachtet, scheint der Algorithmus die Frage zu stellen .

Ich wäre auch vollkommen bereit zu akzeptieren, dass es möglich ist, jedem Zeiger und / oder Rekursion beizubringen ... Ich habe keine Beweise auf die eine oder andere Weise. Ich weiß, dass die Fähigkeit, diese beiden Konzepte wirklich zu verstehen, empirisch gesehen ein sehr guter Prädiktor für die allgemeinen Programmierfähigkeiten ist und dass diese beiden Konzepte im normalen Verlauf der CS-Grundausbildung als eines der größten Hindernisse gelten.

Rekursion ist nicht nur "eine Funktion, die sich selbst aufruft". Sie werden nicht wirklich verstehen, warum Rekursion schwierig ist, bis Sie Stapelrahmen zeichnen, um herauszufinden, was mit Ihrem rekursiven Abstiegsparser schief gelaufen ist. Oft haben Sie gegenseitig rekursive Funktionen (Funktion A ruft Funktion B auf, die Funktion C aufruft, die möglicherweise Funktion A aufruft). Es kann sehr schwierig sein, herauszufinden, was schief gelaufen ist, wenn Sie N Stackframes tief in einer sich gegenseitig rekursiven Reihe von Funktionen befinden.

Auch bei den Zeigern ist das Konzept der Zeiger recht einfach: Eine Variable, die eine Speicheradresse speichert. Wenn jedoch etwas mit Ihrer komplizierten Datenstruktur von void**Zeigern, die auf verschiedene Knoten verweisen, nicht stimmt , werden Sie feststellen, warum es schwierig werden kann, herauszufinden, warum einer Ihrer Zeiger auf eine Speicherbereinigungsadresse verweist.

Java unterstützt Zeiger (sie werden als Referenzen bezeichnet) und unterstützt die Rekursion. Auf den ersten Blick erscheint sein Argument also sinnlos.

Worüber er wirklich spricht, ist die Fähigkeit zum Debuggen. Es ist garantiert, dass ein Java-Zeiger (err, reference) auf ein gültiges Objekt verweist. Wechselstromzeiger nicht. Und der Trick bei der C-Programmierung, vorausgesetzt, Sie verwenden keine Werkzeuge wie valgrind , besteht darin, genau herauszufinden, wo Sie einen Zeiger versaut haben (er befindet sich selten an der Stelle, an der er in einer Stapelspur gefunden wird).

Das Problem mit Zeigern und Rekursionen ist nicht, dass sie schwer zu verstehen sind, sondern dass sie schlecht unterrichtet werden, insbesondere in Bezug auf Sprachen wie C oder C ++ (hauptsächlich, weil die Sprachen selbst schlecht unterrichtet werden). Jedes Mal, wenn ich jemanden sagen höre (oder lese) "ein Array ist nur ein Zeiger", sterbe ich ein wenig im Inneren.

Ebenso möchte ich jedes Mal, wenn jemand die Fibonacci-Funktion verwendet, um die Rekursion zu veranschaulichen, schreien. Dies ist ein schlechtes Beispiel, da die iterative Version nicht schwerer zu schreiben ist und mindestens genauso gut oder besser als die rekursive ist. Außerdem erhalten Sie keinen wirklichen Einblick, warum eine rekursive Lösung nützlich oder wünschenswert wäre. Quicksort, Tree Traversal usw. sind weitaus bessere Beispiele für das Warum und Wie der Rekursion.

Das Müssen mit Zeigern ist ein Artefakt der Arbeit in einer Programmiersprache, die sie verfügbar macht. Generationen von Fortran-Programmierern erstellten Listen und Bäume sowie Stapel und Warteschlangen, ohne dass ein dedizierter Zeigertyp (oder eine dynamische Speicherzuweisung) erforderlich war, und ich habe noch nie gehört, dass jemand Fortran beschuldigte, eine Spielzeugsprache zu sein.

Es gibt verschiedene Schwierigkeiten mit Zeigern:

1. Aliasing Die Möglichkeit, den Wert eines Objekts mithilfe verschiedener Namen / Variablen zu ändern.
2. Nichtlokalität Die Möglichkeit, einen Objektwert in einem Kontext zu ändern, der sich von dem unterscheidet, in dem er deklariert ist (dies geschieht auch mit Argumenten, die als Referenz übergeben werden).
3. Lebensdauerkonflikt Die Lebensdauer eines Zeigers unterscheidet sich möglicherweise von der Lebensdauer des Objekts, auf das er verweist. Dies kann zu ungültigen Verweisen (SEGFAULTS) oder zu Datenmüll führen.
4. Zeiger Arithmetik . Einige Programmiersprachen erlauben die Manipulation von Zeigern als Ganzzahlen. Dies bedeutet, dass Zeiger auf beliebige Stellen verweisen können (einschließlich der unerwartetsten Stellen, an denen ein Fehler vorliegt). Um die Zeigerarithmetik korrekt zu verwenden, muss ein Programmierer die Speichergröße der Objekte kennen, auf die verwiesen wird, und darüber sollten Sie mehr nachdenken.
5. Typumwandlungen Die Fähigkeit, einen Zeiger von einem Typ auf einen anderen umzuwandeln, ermöglicht das Überschreiben des Speichers eines Objekts, das sich von dem beabsichtigten unterscheidet.

Aus diesem Grund muss ein Programmierer bei der Verwendung von Zeigern gründlicher nachdenken (ich kenne die beiden Abstraktionsebenen nicht ). Dies ist ein Beispiel für die typischen Fehler eines Anfängers:

Pair* make_pair(int a, int b)
{
    Pair p;
    p.a = a;
    p.b = b;
    return &p;
}

Beachten Sie, dass Code wie der obige in Sprachen, die kein Zeigerkonzept haben, sondern Namen (Referenzen), Objekte und Werte wie funktionale Programmiersprachen und Sprachen mit Garbage Collection (Java, Python) .

Die Schwierigkeit bei rekursiven Funktionen tritt auf, wenn Personen ohne ausreichenden mathematischen Hintergrund (bei denen die Rekursivität üblich ist und das erforderliche Wissen vorhanden ist) versuchen, sich ihnen zu nähern und glauben, dass sich die Funktion je nachdem, wie oft sie zuvor aufgerufen wurde, unterschiedlich verhält . Dieses Problem wird noch verschärft, weil rekursive Funktionen tatsächlich so erstellt werden können, dass Sie sie so denken müssen, um sie zu verstehen.

Denken Sie an rekursive Funktionen, bei denen Zeiger herumgereicht werden, wie bei einer prozeduralen Implementierung eines Rot-Schwarz-Baums, bei der die Datenstruktur direkt geändert wird. es ist etwas schwieriger zu überlegen als ein funktionales Gegenstück .

Es wird in der Frage nicht erwähnt, aber das andere wichtige Problem, mit dem Anfänger Schwierigkeiten haben, ist die Parallelität .

Wie andere bereits erwähnt haben, gibt es bei einigen Programmiersprachenkonstrukten ein zusätzliches, nicht konzeptionelles Problem: Selbst wenn wir verstehen, können einfache und ehrliche Fehler mit diesen Konstrukten äußerst schwierig zu debuggen sein.

Zeiger und Rekursion sind zwei getrennte Bestien und es gibt verschiedene Gründe, die jede als "schwierig" qualifizieren.

Im Allgemeinen erfordern Zeiger ein anderes mentales Modell als die reine variable Zuweisung. Wenn ich eine Zeigervariable habe, ist es nur das: ein Zeiger auf ein anderes Objekt, die einzigen Daten, die es enthält, sind die Speicheradressen, auf die es zeigt. Wenn ich zum Beispiel einen int32-Zeiger habe und ihm direkt einen Wert zuweisen möchte, ändere ich den Wert des int nicht. Ich zeige auf eine neue Speicheradresse (es gibt viele nette Tricks, die Sie damit machen können ). Noch interessanter ist es, einen Zeiger auf einen Zeiger zu haben (dies passiert, wenn Sie eine Ref-Variable als Funktion übergeben Ausgänge.

Die Rekursion macht beim ersten Lernen einen kleinen mentalen Sprung, weil Sie eine Funktion in sich selbst definieren. Es ist ein wildes Konzept, wenn Sie es zum ersten Mal finden, aber wenn Sie die Idee erst einmal begreifen, wird es zur zweiten Natur.

Aber zurück zum Thema. Bei Joels Argumentation geht es nicht um Hinweise oder Rekursionen an sich, sondern darum, dass die Schüler weiter von der tatsächlichen Funktionsweise der Computer entfernt werden. Dies ist die Wissenschaft in der Informatik. Es gibt einen deutlichen Unterschied zwischen dem Erlernen des Programmierens und dem Erlernen der Funktionsweise von Programmen. Ich denke, es geht nicht so sehr um "Ich habe es so gelernt, also sollte jeder es so lernen müssen", als er argumentierte, dass viele CS-Programme zu verherrlichten Handelsschulen werden.

Ich gebe P. Brian eine +1, weil ich das Gefühl habe, dass es so ist: Rekursion ist ein so grundlegendes Konzept, dass er, der die geringsten Schwierigkeiten damit hat, besser überlegen sollte, einen Job bei mac donalds zu suchen, aber dann gibt es sogar Rekursion:

make a burger:
   put a cold burger on the grill
   wait
   flip
   wait
   hand the fried burger over to the service personel
   unless its end of shift: make a burger

Der Mangel an Verständnis hat sicherlich auch mit unseren Schulen zu tun. Hier sollte man natürliche Zahlen wie Peano, Dedekind und Frege einführen, damit wir später nicht so viele Schwierigkeiten hätten.

Ich stimme Joel nicht zu, dass das Problem darin besteht, auf mehreren Abstraktionsebenen per se zu denken. Ich denke eher, dass Zeiger und Rekursion zwei gute Beispiele für Probleme sind, die eine Änderung des mentalen Modells erfordern, das die Leute in Bezug auf die Funktionsweise von Programmen haben.

Zeiger sind meiner Meinung nach der einfachere Fall, um sie zu veranschaulichen. Der Umgang mit Zeigern erfordert ein mentales Modell der Programmausführung, das berücksichtigt, wie Programme tatsächlich mit Speicheradressen und Daten arbeiten. Ich habe die Erfahrung gemacht, dass Programmierer oft nicht einmal darüber nachgedacht haben, bevor sie etwas über Zeiger erfahren. Auch wenn sie es abstrakt kennen, haben sie es nicht in ihr kognitives Modell der Funktionsweise eines Programms übernommen. Wenn Zeiger eingeführt werden, muss die Art und Weise, wie sie über die Funktionsweise des Codes nachdenken, grundlegend geändert werden.

Rekursion ist problematisch, weil es zwei konzeptionelle Blöcke zum Verstehen gibt. Die erste ist auf Maschinenebene und kann, ähnlich wie bei Zeigern, überwunden werden, indem ein gutes Verständnis dafür entwickelt wird, wie Programme tatsächlich gespeichert und ausgeführt werden. Das andere Problem bei der Rekursion ist meiner Meinung nach die natürliche Tendenz der Menschen, ein rekursives Problem in ein nicht rekursives zu zerlegen, was das Verständnis einer rekursiven Funktion als Gestalt trübt. Dies ist entweder ein Problem bei Menschen mit unzureichendem mathematischen Hintergrund oder ein mentales Modell, das die mathematische Theorie nicht an die Entwicklung von Programmen bindet.

Die Sache ist, ich denke nicht, dass Zeiger und Rekursion die einzigen zwei Bereiche sind, die für Menschen problematisch sind, die in einem unzureichenden mentalen Modell stecken. Parallelität scheint ein weiterer Bereich zu sein, in dem manche Menschen einfach stecken bleiben und Schwierigkeiten haben, ihr mentales Modell anzupassen, um zu berücksichtigen. Es ist nur so, dass Zeiger und Rekursionen in einem Interview oft einfach zu testen sind.

  DATA    |     CODE
          |
 pointer  |   recursion    SELF REFERENTIAL
----------+---------------------------------
 objects  |   macro        SELF MODIFYING
          |
          |

Das Konzept von selbstreferenzierenden Daten und Code liegt der Definition von Zeigern bzw. Rekursionen zugrunde. Unglücklicherweise haben Informatikstudenten aufgrund des weitverbreiteten Kontakts mit imperativen Programmiersprachen geglaubt, dass sie die Implementierung über das Betriebsverhalten ihrer Laufzeiten verstehen müssen, wenn sie diesem Geheimnis den funktionalen Aspekt der Sprache anvertrauen wollen. Das Summieren aller Zahlen auf hundert scheint eine einfache Sache zu sein, mit einer zu beginnen und mit Hilfe kreisförmiger selbstreferenzieller Funktionen zur nächsten in der Folge zu addieren und rückwärts zu machen reine Funktionen.

Das Konzept der Selbstmodifizierung von Daten und Code liegt der Definition von Objekten (dh intelligenten Daten) bzw. Makros zugrunde. Ich erwähne diese, da sie noch schwieriger zu verstehen sind, insbesondere wenn von einer Kombination aller vier Konzepte ein operatives Verständnis der Laufzeit erwartet wird - z. B. ein Makro, das eine Menge von Objekten generiert, die mithilfe eines Zeigerbaums einen rekursiven anständigen Parser implementiert . Anstatt die gesamte Operation des Programmzustands schrittweise auf einmal durch jede Abstraktionsebene zu verfolgen, müssen imperative Programmierer lernen, darauf zu vertrauen, dass ihre Variablen innerhalb von reinen Funktionen nur einmal zugewiesen werden und dass wiederholte Aufrufe derselben reinen Funktion mit Die gleichen Argumente liefern immer das gleiche Ergebnis (dh referenzielle Transparenz), auch in einer Sprache, die auch unreine Funktionen wie Java unterstützt. Nach der Laufzeit im Kreis herumzulaufen ist ein vergebliches Unterfangen. Abstraktion soll vereinfachen.

Sehr ähnlich zu Anons Antwort.
Abgesehen von kognitiven Schwierigkeiten für Neulinge sind sowohl Zeiger als auch Rekursion sehr leistungsfähig und können auf kryptische Weise verwendet werden.

Der Nachteil von großer Kraft ist, dass sie Ihnen große Kraft geben, um Ihr Programm auf subtile Weise zu vermasseln.
Das Speichern eines gefälschten Werts in einer normalen Variablen ist schon schlimm genug, aber das Speichern eines gefälschten Werts in einem Zeiger kann dazu führen, dass alle Arten von katastrophalen Verzögerungen eintreten.
Schlimmer noch, diese Effekte können sich ändern, wenn Sie versuchen, die Ursache für das bizarre Programmverhalten zu diagnostizieren / zu debuggen.

Ähnliches gilt für die Rekursion. Es kann eine sehr leistungsfähige Methode sein, um knifflige Dinge zu organisieren, indem die Kniffligkeit in die versteckte Datenstruktur (Stapel) eingefügt wird.
Aber wenn etwas auf subtile Weise falsch gemacht wird, kann es schwierig sein, herauszufinden, was los ist.