C++ / Rekursion

C++ / Rekursion

Impressum | Werbung

Geizhals » Forum » Programmierung »

C++ / Rekursion (28 Beiträge, 213 Mal gelesen)

Top-100 | Fresh-100

Du bist nicht angemeldet. [ Login/Registrieren ]

bin grad in einem buch über folgenden text gestolpert:

verzichten sie auf rekursive funktionen ... rekursionen sind teuer - bei jedem aufruf wird für jede verwendete variable in dieser funktion ein eigener speicherplatz angelegt... stacküberlauf..

wie weit stimmt das? kann ich dieses problem (zb bei verketteten listen) irgendwie mit zeigern umgehen?

bin grad a bissl verwirrt

() ascii ribbon campaign - against html in mail and news
/\ - against microsoft attachments

kann ich dieses problem (zb bei verketteten listen) irgendwie mit zeigern
umgehen?

Würd ich schon sagen...dazu sind Pointer ja da.

aber wird dann nicht jedes mal eine neue variable angelegt mit der adresse des nächsten elements?

() ascii ribbon campaign - against html in mail and news
/\ - against microsoft attachments

Hmm.
Jetzt weiß ichs auch nimmer

Aber wenn scho, was würds machen?

stacküberlauf?

keine ahnung, drum frag ich ja

() ascii ribbon campaign - against html in mail and news
/\ - against microsoft attachments

So schnell lauft der scho net über

Kommt drauf an wie man's implementiert. Es stimmt wohl, daß lokale Variablen für jede Rekursion angelegt werden, man kann allerdings durchaus auch ohne auskommen, bzw. die Notwendigkeit derselben auf die "Ausnahmefälle" (sprich Abbruchbedingung oder "Gefunden" usw) beschränken. Oft genug, vor allem wenn man's mit Klassen realisiert, kommt man überhaupt ohne aus.

Lies Dich in die STL ein, damit sind viele der Probleme mit linked lists usw. leicht zu vermeiden.

________________________________________________________________________
Some people are like compilers. They take simple statements, add stuff from their memory, assume what you don't tell them explicitely and make some big production out of it.

also wenn ich die funktion rekursiv aufrufe ohne eine neue variable anzulegen braucht er kan neuen speicher anfordern? aber irgendwo muss er sich doch den zwischenschritt merken oder?

STL gut und schön.. hilft mir aber weder beim verständnis meines problems noch bei der aufgabenstellung..

() ascii ribbon campaign - against html in mail and news
/\ - against microsoft attachments

Du hast natürlich den Overhead, der dadurch entsteht daß hier der Aufruf auf'm Stack rumkugelt. Ob's jetzt allerdings sinnvoller ist, es iterativ zu lösen oder rekursiv hängt von einigen Faktoren ab. Von der Architektur die Du verwendest, vom System und nicht zuletzt von der Aufgabenstellung.

________________________________________________________________________
Some people are like compilers. They take simple statements, add stuff from their memory, assume what you don't tell them explicitely and make some big production out of it.

dass es für kleinere aufgaben komplett irrelevant ist ist mir klar... bei welchen fällen könnt sowas zu einem problem werden?

() ascii ribbon campaign - against html in mail and news
/\ - against microsoft attachments

Wahrscheinlich von irgendeinem Jolly, der gerade mal Windows programmiert, geschrieben.

Definitiv stimmt die Aussage, daß es Speicherplatz braucht. Allerdings ist die Frage, wieviel da realistisch zusammenkommt. Intel-CPU's verwenden die ENTER/LEAVE-Kombi auf Assemblerebene - das bedeutet, daß die Stackanforderung selbst mal mit wenigen CPU-Zyklen auskommt - also auf weniger als einer Milliardstel-Sekunden auf aktuellen Rechner... Und Speicher wird genausoviel angefordert wie lokale nicht-statische Variablen in der Funktion.

Wenn du also sagen wir 10 int32-werte in deiner lokalen Funktion hast - dann sind das 40 Bytes. Bei einer Rekursionstiefe von 25000 (was utopisch hoch ist) - hast gerade mal ein einziges Megabyte verschleudert - und auch nur zum "tiefsten" Zeitpunkt der Rekursion.

Als [seit >10 Jahren beruflicher] Programmierer sage ich Dir:
Meine Zeit, auch nur einen Gedanken an 1MB Storage [das eh nur millisekunden alloziert wird] zu verschwenden, ist weit teurer als der Speicher selbst

.

Wenn du nicht von gaaaanz extremen Rekursiven Funktionen sprichst - vergiß das Statement des Buchs.

Die Stunde eines [guten] Programmierers kostet insgesamt rd. 120-500 Euro. Selbst wenn er nur den Richtsatz der WKO kostet (und da geht's um durchschnittliche Programmierer) - und er sich beinhart einen Algo überlegt, wo er nur 512K Speicher braucht - und er dafür mit Doku, Test, ... 8 Stunden investierte - so kosteten im Endeffekt 512KB Ram mehr als 800 Euro... Wieviel RAM hättest dafür einkaufen können ?

Abschlußaussage:
Meide Bücher, wo endgültige, uneingeschränkte Statements auftreten

das is mal eine antwort wie ich sie mir erwarte.. und leider bleibts hier oft beim warten

ja hast recht.. is ein schrottiges buch.. hab eh noch stroustrub und 2 mal sedgewick da liegen.. hab darüber leider nix auf die schnelle gefunden außer einem hinweise dass " bei sehr großen problemen der stack eine rekursive lösung verhindern kann"... darum meine frage..

welche bücher kannst du sonst noch empfehlen?

() ascii ribbon campaign - against html in mail and news
/\ - against microsoft attachments

Die Stunde eines [guten] Programmierers kostet insgesamt rd. 120-500 Euro.

Kennst Du wirklich Programmierer die einen solchen Stundensatz haben? - ich nicht - die Leute die ich kenne - und das sind sehr gute Leute . bekommen knapp unter 100 Euro per Stunde.

Mini AquariumCam

Naja, zwischen kosten und bekommen ist halt ein kleiner Unterschied.

________________________________________________________________________
Some people are like compilers. They take simple statements, add stuff from their memory, assume what you don't tell them explicitely and make some big production out of it.

Yup - genau das ist der Punkt.

Denn der Programmierer kostet zusätzlich Arbeitgeberabgaben, Anteilig Büroplatz, Storage, Client-PC's, Putzfrau, Verwaltung, ...

Und dem Unternehmen ist ja mal wurscht, wieviel er verdient - dem ist nur wichtig, wieviel es zahlen muß

Die Kosten passen schon mit 120-500 Euro...

Dann bin ich ja direkt billig! Ich koste knapp 80€ intern.

Hmm... mal über mein Gehalt nachdenken...

________________________________________________________________________
Some people are like compilers. They take simple statements, add stuff from their memory, assume what you don't tell them explicitely and make some big production out of it.

Was meinst jetzt mit Brutto? Gesamtkosten.

________________________________________________________________________
Some people are like compilers. They take simple statements, add stuff from their memory, assume what you don't tell them explicitely and make some big production out of it.

also was du ein unternehmen kostest??

dann wärn es also gut 40€ brutto für dich

Schön wär's ja. Du unterschätzt die Bürokratie eines Konzerns gewaltig. Ich muss mit meiner Arbeitsleistung eine Menge Overhead mitfinanzieren.

________________________________________________________________________
Some people are like compilers. They take simple statements, add stuff from their memory, assume what you don't tell them explicitely and make some big production out of it.

hmm...tja is leider so...

geh zum orf

hab gestern gelesen das der roman raffreider (oder wie der da genau heißt) gut 15.000€ monatlich verdient als moderator etc

und ATV hat ihm sogar +16.000€ geboten wenn er zu denen wechselt

Mfg Marax

Vertrau mir, ich bin einer von den Guten

Kommt drauf an, was du machst (und wie du es machst). So allgemeine Aussagen sind nie 100% korrekt. Wennst viele grosse lokale Variablen und eine hohe Rekursionstiefe hast, dann stimmt das schon.

Suche im Forum
Suche im Internet (Google)
Was ist?
Forums-FAQ
Kino 2005

Auf den Stacküberlauf muss man aufpassen, ansonsten vernachlässigbar, wenn Du nicht wirklich große Datenstrukturen als lokale Variablen oder im Funktionsaufruf verwendest.

Wirklich nur in Ausnahmefällen, also
- Embedded Devices mit seeehr wenig RAM
- Strangen Devices ohne MMU und ohne HW-Stack
- Extrem aufwändigen Funktionen

Denn mit der gleichen Argumentation könntest auch sagen "meide Funktionsaufrufe, bau lieber lineare Programme"

Sorry, aber sobald man multithreading fährst, muss man aufpassen. Desgleichen bei DCE-RPC. Meldung: 'process killed due to trashed stack' auf einer HP-UX midrange Unix Kiste mit 4 CPU's und 4 Gig Ram habe ich schon gesehen.

Das kommt wohl daher, dass der Stack eines neuen pthreads etwas klein ist (64KB), ausser Du setzt ihn beim Erzeugen schon rauf.

Naja...

Erstens: Wenn du pthread_attr_setstacksize net verwendest, bist wissentlich ins Messer gerannt
Zweitens: sehe ich pthreads als ähnlichen "Exoten" wie embedded Devices... Beide gibt's sehr oft, aber beide haben ganz eigene Regeln
Drittens: Als Allgemeinplatz finde ich die Aussage "vermeide Rekursionen" definitiv falsch
Viertens: Sein Buch wirkt wie ein Einsteigerbuch... Da hat sowas überhaupt nichts zu suchen ,-).

Vieles läßt sich elegant und sauber einfach mit Rekursionen lösen. Klar kann man alles ohne Rekursion lösen, nur das Argument "Stacküberlauf" gilt für jede Rekursion gleich wie für jeden "normalen" Funktionsaufruf (eine Rekursion ist ja ein auch in Wirklichkeit ein ganz normaler Aufruf fürs System)...

So oder so, du hast absolut Recht, daß es [manchmal] Gründe gibt, auf Rekursionen zu verzichten - aber eben nur manchmal...
cu
gepeinigter.

Hab ich behauptet Rekursion ist schlecht? Sicher nicht. Ich hab nur drauf hingewiesen, dass man eben auf den Stack achten soll/muss, sonst nix.

Un mitm pthread_attr_setstacksize hast schon recht

Hehe...
Genau das meinte ich mit meinem Schlußabsatz

Dieses Forum ist eine frei zugängliche Diskussionsplattform.
Der Betreiber übernimmt keine Verantwortung für den Inhalt der Beiträge und behält sich das Recht vor, Beiträge mit rechtswidrigem oder anstößigem Inhalt zu löschen.
Datenschutzerklärung