Programmiergerüchte
-
_mngbd schrieb:
* rekursiv geht schief (in MISRA verboten?)
Ja:
Functions shall not call themselves, either directly or indirectly
Niemand kann ja garantieren, dass für die Rekursion genug Stack da ist... hm, ein Gerücht?
MISRA ist ein Fluch?
-
abc.w schrieb:
Niemand kann ja garantieren, dass für die Rekursion genug Stack da ist... hm, ein Gerücht?
Aber man sollte durchaus logarithmisch beschränkte Rekursion zulassen. Oder welche, die unabhängig von den Eingangsdaten nicht mehr als 1k benötigt. Bei Quicksort wird das zum Beispiel leicht erreicht, indem man immer die kleinere "Hälfte" rekursiv aufruft und die größere "Hälfte" die in eine Schleife umgewandelte Endrekursion machen läßt.
-
volkard schrieb:
Aber man sollte durchaus logarithmisch beschränkte Rekursion zulassen. Oder welche, die unabhängig von den Eingangsdaten nicht mehr als 1k benötigt. Bei Quicksort wird das zum Beispiel leicht erreicht, indem man immer die kleinere "Hälfte" rekursiv aufruft und die größere "Hälfte" die in eine Schleife umgewandelte Endrekursion machen läßt.
Ich kann mir gut vorstellen, es gibt dann jemanden, der sagt: "Herr volkard, alles schön und gut, aber stellen Sie sich vor, ein Auto muss bremsen und ABS fällt aus, weil es in der ABS Software eine schöne rekursive Funktion gibt, die aus unerklärlichen Gründen einen Stacküberlauf verursacht hat. Das Auto wird auf die Gegenfahrbahn geschleudert und es kommt zum Frontalzusammenstoß mit dem entgegenkommenden Auto..." usw.
-
Mit dem gleichen Argument kannst Du JEDEN Funktionsaufruf als gefährlich ansehen, denn vielleicht klappt er nicht, weil der Stackspeicher alle ist. Oder jede Funktion mit mehr als fünf lokalen Variablen. Oder jede Funktion mit mehr als 1k lokalen Variablen. Wo ist die Grenze?
Auf PCs sind 1k sicherlich null problemo. Auf Schwachrechnern mag man die Grenze auf 64 Bytes legen, wasauchimmer.
Aber Rekursion als solche zu verteufeln, ist nicht sehr gut.
-
außerdem könnte man jeder rekursiven Funktion ein zusätzliches Argument mitgeben, das die Rekursionstiefe mitzählt und bei Überschreitung weitere Selbstaufrufe verhindert.
-
volkard schrieb:
Aber Rekursion als solche zu verteufeln, ist nicht sehr gut.
MISRA-regeln sind zum grossen teil vorbeugende massnahmen. die gehen einfach davon aus, dass nicht jeder 100%ig weiss, wie tief seine funktionen rekursieren können, also verbieten sie's 'per default'. ist genau so bescheuert wie rote ampeln: auch wenn der nächste verkehrsteilnehmer 1km entfernt ist, losfahren darfste bei rot trotzdem nicht.
-
volkard schrieb:
Mit dem gleichen Argument kannst Du JEDEN Funktionsaufruf als gefährlich ansehen, denn vielleicht klappt er nicht, weil der Stackspeicher alle ist. Oder jede Funktion mit mehr als fünf lokalen Variablen. Oder jede Funktion mit mehr als 1k lokalen Variablen. Wo ist die Grenze?
Auf PCs sind 1k sicherlich null problemo. Auf Schwachrechnern mag man die Grenze auf 64 Bytes legen, wasauchimmer.
Aber Rekursion als solche zu verteufeln, ist nicht sehr gut.Ja, jeder Funktionsaufruf kann einen Stacküberlauf verursachen, aber es gibt z.B. Regeln oder Vorgaben in einem Projekt, wie viele Parameter eine Funktion maximal haben darf, wie viele maximal ausführbare Zeilen, wie viele maximal lokale Variablen... Ich bin nicht in diesem Bereich tätig (komme aus dem "car infotainment" Bereich, wo es mit MISRA und QAC++ Regeln lockerer ist) und weiss nicht genau, wie man es mit dem Stack genau garantieren kann. Ein Paar mal durfte ich mit den Green Hills Tools für V850 Mikrocontroller arbeiten und nach dem Kompilieren gab es eine Textdatei, in der Funktionen und alle Pfade und deren Stackverbrauch aufgelistet waren. Damit könnte man ja schon den Stackverbrauch eines Tasks recht genau abschätzen. Dann kann man das System laufen lassen, anhalten und sich mit dem Debugger die Stacks anschauen (so ungefähr mache ich das), Pi mal Daumen, 30% des Stacks müssen noch da sein (z.B).
Bei rekursiven Funktionen weiss man ja aber nicht, wie viel Stack vor dem rekursiven Funktionsaufruf noch frei sind. Es könnte ja sein, 30% sind frei, und dann wird die rekursive Funktion aufgerufen. Auch wenn diese Funktion einen Zähler zum Abruch o.ä. zur Absicherung hat, weiss man ja trotzdem nicht, ob die 30% ausreichen...
-
abc.w schrieb:
Bei rekursiven Funktionen weiss man ja aber nicht, wie viel Stack vor dem rekursiven Funktionsaufruf noch frei sind.
Ich gehe nur von rekursiven Funktionen aus, die ich beherrschen kann, zum Beispiel garantieren kann, daß die Tiefe nicht größer als 10 wird und pro Aufruf ausgemessen 20 Bytes draufgehen, macht nicht mehr als 200 Bytes.
Warum sollte man da weniger wissen, als bei normalen Funktionen?
-
volkard schrieb:
Ich gehe nur von rekursiven Funktionen aus, die ich beherrschen kann, zum Beispiel garantieren kann, daß die Tiefe nicht größer als 10 wird und pro Aufruf ausgemessen 20 Bytes draufgehen, macht nicht mehr als 200 Bytes.
Warum sollte man da weniger wissen, als bei normalen Funktionen?Es wird schwierig wenn die Rekursiontiefe von Funktionsargumenten abhängt was oft der Fall ist. Dann müßte die Funktieon alle Argumente ablehnen die eine bestimmte Tiefe verlangen
-
general bacardi schrieb:
Es wird schwierig wenn die Rekursiontiefe von Funktionsargumenten abhängt was oft der Fall ist. Dann müßte die Funktieon alle Argumente ablehnen die eine bestimmte Tiefe verlangen
Beispiel: Es gibt in der SetTopBox 1000 Programmplätze. Man will sie mit Quicksort sortieren (nur als Beispiel). Und man nimmt die von mir oben gesagte Modifikation und hat garantiert nicht mehr als Rekursionstiefe 10.
Oder auf PCs: Selbst bei 4GB Daten hat man nicht mehr als Rekursionstiefe 32.
-
Ok. Also ich denke, normalerweise wird es in einem Projekt so ablaufen, jemand stellt mit dem MISRA Checker fest, die Regel so und so "rekursive Funktionen nicht erlaubt" wurde verletzt. Diese Regel hat jemand explizit für dieses Projekt festgelegt. Dieser jemand ist dein Vorgesetzter oder der Kunde...
Dann heißt es entweder, weg mit der Rekursion, oder, Rekursion behalten und die Stelle besonders dokumentieren u.ä.
-
abc.w schrieb:
Ok. Also ich denke, normalerweise wird es in einem Projekt so ablaufen, jemand stellt mit dem MISRA Checker fest, die Regel so und so "rekursive Funktionen nicht erlaubt" wurde verletzt. Diese Regel hat jemand explizit für dieses Projekt festgelegt. Dieser jemand ist dein Vorgesetzter oder der Kunde...
Dann heißt es entweder, weg mit der Rekursion, oder, Rekursion behalten und die Stelle besonders dokumentieren u.ä.Ich widerspreche doch nur deiner Expertise "Niemand kann ja garantieren, dass für die Rekursion genug Stack da ist... hm, ein Gerücht?" und der Folgerung, Rekursion sei grundsätzlich gefährlich.
Und ich sage, daß es keine kluge Vorgehensweise ist, Rekursion generell zu verbieten. Projektweise oder Firmenweise oder MISRA-Branchenweise ist kein Problem. Jeder, wie er mag.
-
volkard schrieb:
...und der Folgerung, Rekursion sei grundsätzlich gefährlich.
rekursion hat auch keinen vorteil, ausser einer will zeigen, was für'n toller programmierer er ist. manche kommen auf die glorreiche idee, irgendwelchen mathematischen firlefanz wie 'ne fakultätsfunktion rekursiv zu proggen, und vergessen dabei, dass die rekursionstiefe linear in die höhe schnellt. in der realität bringt rekursion garnix und ist auch noch langsamer.
-
Falsch. Manchmal ist Rekursion schneller als der iterative Ersatz. Manchmal kriegt man's iterativ gar nicht hin (außer mit simulierter Rekursion durch einen künstlichen Stack, also keinerlei Zugewinn).
-
volkard schrieb:
Beispiel: Es gibt in der SetTopBox 1000 Programmplätze. Man will sie mit Quicksort sortieren (nur als Beispiel). Und man nimmt die von mir oben gesagte Modifikation und hat garantiert nicht mehr als Rekursionstiefe 10.
... im Mittel hast du recht. Im Worst-case kann der normale Quicksort aber Rekursionstiefe O(n) erreichen.
Da nimmt man besser abgewandelte Quicksorts mit besserem Worstcase-Verhalten, heapsort (der zwar im Mittel schlechter, aber im Worst-case besser ist) oder Introsort, der bei Überschreiten der Rekursionstiefe O(log n) auf heapsort "umschaltet".
-
u_ser-l schrieb:
volkard schrieb:
Beispiel: Es gibt in der SetTopBox 1000 Programmplätze. Man will sie mit Quicksort sortieren (nur als Beispiel). Und man nimmt die von mir oben gesagte Modifikation und hat garantiert nicht mehr als Rekursionstiefe 10.
... im Mittel hast du recht. Im Worst-case kann der normale Quicksort aber Rekursionstiefe O(n) erreichen.
Ich habe im worst case recht. Lies doch nochmal genau. Die Modifikation ist ein paar Postings vorher genau beschrieben.
-
ja, mit dem modifizierten Quicksort hast du recht.
-
volkard schrieb:
Ich widerspreche doch nur deiner Expertise "Niemand kann ja garantieren, dass für die Rekursion genug Stack da ist... hm, ein Gerücht?" und der Folgerung, Rekursion sei grundsätzlich gefährlich.
Und ich sage, daß es keine kluge Vorgehensweise ist, Rekursion generell zu verbieten. Projektweise oder Firmenweise oder MISRA-Branchenweise ist kein Problem. Jeder, wie er mag.Also irgendwelche Folgerungen habe ich nicht gezogen. Ist ja auch egal.
Eins muss man vielleicht dazu sagen: MISRA macht keine Verbote. Da haben sich "einfach" einige Spezialisten zusammengesetzt und haben "einfach mal so" die Regeln vorgeschlagen, die wenn man die befolgt, zu besserer Software führen sollen, so nach dem Motto "Software rostet nicht" .
Software rostet nicht - ein weiteres Gerücht?
-
volkard schrieb:
Falsch. Manchmal ist Rekursion schneller als der iterative Ersatz. Manchmal kriegt man's iterativ gar nicht hin (außer mit simulierter Rekursion durch einen künstlichen Stack, also keinerlei Zugewinn)
ok, algos wie den qsort z.b. dann sach ich mal: rekursion nur, wenn's nicht anders geht. zur not mit 'nem selbstgemachten stack, dessen füllstand die rekursive funktion selbst überprüfen kann. das entlastet den prozessor-stack und der aufrufer der funktion braucht sich keine gedanken zu machen, ob sein input zum absturz durch stack overflows führen kann. wer sowas wie fakultät, fibonacci-zahlen, permutationen, towers of hangeul. usw. braucht, der sollte trotzdem auf rekursion verzichten, auch wenn der code mit rekursion schicker und einfacher aussieht. schliesslich sind nicht alle compiler so schlau und machen aus rekursiven formulierungen schleifen.
-
* hier kann man auch nach 5 Seiten beim Thema bleiben
* Wer goto benutzt, bekommt Besuch von einem Velociraptor