Van Pascal naar C++/Java

[Verwijderd]

Op dit moment ben ik me aan het verdiepen in data structuren en algoritmen en de talen die ik gebruik zijn C++ en Java. Echter het boek gebruikt Pascal als taal. In de meeste gevallen zijn de Pascal algoritmen 1 op 1 om te schrijven naar C++/Java, totdat er in het boek recursie gebruikt wordt.

Het probleem is dat als in een functie geheugen gereserveerd wordt, deze operatie wordt opgeheven als de functie wordt beeindigd. Voorbeeld

code:

void f(Tree *p)
{   p=new Tree();
}

Aanroep

code:

int main(void)
{    Tree p=null;
     f(p);
     f.value=10     //zal niet werken
}

Ik begrijp wel waarom het niet werkt, dus dat is de vraag niet.

Als in het boek recursie wordt gebruikt, wordt het wel op bovenstaande manier gedaan, 1 op 1 vertaalt ziet een functie uit het boek in C++ er dan zo uit:

code:

void insert(int a, Tree *p)
{   if (p==NULL)
    {   p=new Tree();
        p->w=a;
        p->l=NULL;
        p->r=NULL;
    }
    else if (a<p->w)
        insert(a,p->l);
    else if (a>p->w)
        insert(a, p->r);
}

De vraag is hoe kan ik dit op een zo mooi mogelijke manier dit soort functies van Pascal naar C++ vertalen?

[MSalters]

Functies hebben gewoon return waarden:

C++:

Tree* f()
{
  return new Tree;
}

[Verwijderd]

Verwijderd schreef op donderdag 20 juli 2006 @ 20:55:
Op dit moment ben ik me aan het verdiepen in data structuren en algoritmen en de talen die ik gebruik zijn C++ en Java. Echter het boek gebruikt Pascal als taal. In de meeste gevallen zijn de Pascal algoritmen 1 op 1 om te schrijven naar C++/Java, totdat er in het boek recursie gebruikt wordt.

Het probleem is dat als in een functie geheugen gereserveerd wordt, deze operatie wordt opgeheven als de functie wordt beeindigd. Voorbeeld

code:

void f(Tree *p)
{   p=new Tree();
}

Aanroep

code:

int main(void)
{    Tree p=null;
     f(p);
     f.value=10     //zal niet werken
}

Ik begrijp wel waarom het niet werkt, dus dat is de vraag niet.

Wat is het nut dan om het te vermelden?
Is het een typefout, of bedoel je p.value=10 want ik zie zo ff niet waarom het dan niet zou moeten werken.?

Verwijderd schreef op donderdag 20 juli 2006 @ 20:55:

Als in het boek recursie wordt gebruikt, wordt het wel op bovenstaande manier gedaan, 1 op 1 vertaalt ziet een functie uit het boek in C++ er dan zo uit:

code:

void insert(int a, Tree *p)
{   if (p==NULL)
    {   p=new Tree();
        p->w=a;
        p->l=NULL;
        p->r=NULL;
    }
    else if (a<p->w)
        insert(a,p->l);
    else if (a>p->w)
        insert(a, p->r);
}

De vraag is hoe kan ik dit op een zo mooi mogelijke manier dit soort functies van Pascal naar C++ vertalen?

Is toch niets mis mee?
Maar uh, is het dan niet verstandig om ook ff de pascal-code te vermelden?

[NMe]

Verwijderd schreef op donderdag 20 juli 2006 @ 21:08:
[...]

Wat is het nut dan om het te vermelden?
Is het een typefout, of bedoel je p.value=10 want ik zie zo ff niet waarom het dan niet zou moeten werken.?

Het werkt niet omdat hij een waarde by value doorgeeft aan een functie die een pointer wil hebben, nog los van die tikfout en het feit dat een nullpointer opslaan in een non-pointer nogal loos is.

Is toch niets mis mee?

Netjes is anders IMO, zie MSalters.

Maar uh, is het dan niet verstandig om ook ff de pascal-code te vermelden?

Dat sowieso. Wij kunnen moeilijk zeggen of iets goed is als we het origineel niet zien.

[Creepy]

Het probleem is dat als in een functie geheugen gereserveerd wordt, deze operatie wordt opgeheven als de functie wordt beeindigd. Voorbeeld

Als je ergens in een functie een aanroep naar new of malloc doet dan zal je dit ergens weer vrij moeten geven. Dit wordt niet zomeer opgeheven of automatsch voor je gedaan (net als in Pascal overigens).

[Verwijderd]

MSalters schreef op donderdag 20 juli 2006 @ 21:02:
Functies hebben gewoon return waarden:

C++:

Tree* f()
{
  return new Tree;
}

Dat begrijp ik, maar het gaat om het probleem te beschrijven dat ik tegenkom als ik een recursieve pascal functie wil vertalen in C++.

Verwijderd schreef op donderdag 20 juli 2006 @ 21:08:
[...]

Wat is het nut dan om het te vermelden?
Is het een typefout, of bedoel je p.value=10 want ik zie zo ff niet waarom het dan niet zou moeten werken.?

Dit is idd een type fout

De code moet dus zijn (p moet een pointer zijn):

code:

int main(void)
{    Tree *p=null;
     f(p);
     p->value=10     //zal niet werken
}

[...]

Is toch niets mis mee?
Maar uh, is het dan niet verstandig om ook ff de pascal-code te vermelden?

Goed idee
Die zal ik morgen ff overtikken uit het boek

-NMe- schreef op donderdag 20 juli 2006 @ 21:11:
[...]

Het werkt niet omdat hij een waarde by value doorgeeft aan een functie die een pointer wil hebben, nog los van die tikfout en het feit dat een nullpointer opslaan in een non-pointer nogal loos is.

p hoort dus een pointer te zijn

[...]

Netjes is anders IMO, zie MSalters.

Dat begrijp ik, maar ik wil duidelijk maken wat ik bedoel

Creepy schreef op donderdag 20 juli 2006 @ 21:31:
[...]

Als je ergens in een functie een aanroep naar new of malloc doet dan zal je dit ergens weer vrij moeten geven. Dit wordt niet zomeer opgeheven of automatsch voor je gedaan (net als in Pascal overigens).

Dat bedenk ik me ook net.
Dan is het probleem dat pointer p in functie f() een stuk geheugen krijgt toegewezen, maar p verliest na f() zijn waarde.

[ Voor 71% gewijzigd door NMe op 20-07-2006 22:02 ]

[NMe]

Wil je de volgende keer niet meer 4 posts achter elkaar plaatsen? Dat leest vrij vervelend en is nergens voor nodig, je kan je posts gewoon editen. In dit geval heb ik het even voor je gedaan.

[DroogKloot]

whosvegas schreef:
[...]

Dat bedenk ik me ook net.
Dan is het probleem dat pointer p in functie f() een stuk geheugen krijgt toegewezen, maar p verliest na f() zijn waarde.

Aangenomen dat we het over onderstaande stukje C++ hebben...

C++:

void f(Tree* p) {
  p=new Tree();
}

int main(void) {
  Tree* p=null;
  f(p);
  p->value=10;     //zal niet werken
}

... klopt je opmerking alsnog niet, want p in main() krijgt helemaal nix toegewezen en behoudt daarom gewoon zijn beginwaarde (null). Het echte probleem is namelijk dat de p in f() waar je wel geheugen aan toewijst een kopie is van de p in main(), dus je programmaatje dereferenced zowel een nullpointer EN bevat een geheugenlek, al met al geen slechte beginnersscore.

[ Voor 21% gewijzigd door DroogKloot op 20-07-2006 23:41 ]

[Verwijderd]

DroogKloot schreef op donderdag 20 juli 2006 @ 22:13:
[...]


Aangenomen dat we het over onderstaande stukje C++ hebben...

C++:

void f(Tree* p) {
  p=new Tree();
}

int main(void) {
  Tree* p=null;
  f(p);
  p->value=10;     //zal niet werken
}

Ik gok dat het de volgende code moet worden (ben geen held met C++)
16.7 @ Pointers and references

C++:

void f(Tree* &p) {
  p=new Tree();
}

int main(void) {
  Tree* p=null;
  f(&p);
  p->value=10;     //zal niet werken
}

voor deze pascal code?

Delphi:

procedure f(var p: Tree);
begin
  p := Tree.Create();
end;

procedure main
var
  p: Tree;
begin
  p := Null;
  f(p);
  p.value=10;
end;

[sirdupre]

Ik snap sowieso de recursie in je voorbeeld niet helemaal.

In elk geval, als je een volledig gevulde binaire boom met diepte n in java wilt waarin je ints kunt opslaan, zou ik iets doen als:

code:

class BinTree
{
    BinTree left;
    BinTree right;
    int value;
    public BinTree(int depth)
    {
         if (depth > 0)
         {
              left = new BinTree(depth-1);
              right = new BinTree(depth-1);
         }
    }

    public BinTree getLeft()
    {
           return left;
    }

    public BinTree getRight()
    {
           return right;
    }

    public void setValue(int v)
    {
           value = v;
    }

    public int getValue()
    {
           return value;
    }
}

Een analoog voorbeeld hiervan kan je vast wel in je boek vinden en dit is iig een goed voorbeeld van een recursieve datastructuur in java .

[DroogKloot]

sinaasappelsap schreef:
[...]

Ik gok dat het de volgende code moet worden (ben geen held met C++)
16.7 @ Pointers and references

C++:

void f(Tree* &p) {
  p=new Tree();
}

int main(void) {
  Tree* p=null;
  f(&p);
  p->value=10;     //zal niet werken
}

voor deze pascal code?

Delphi:

procedure f(var p: Tree);
begin
  p := Tree.Create();
end;

procedure main
var
  p: Tree;
begin
  p := Null;
  f(p);
  p.value=10;
end;

Niet f(&p) maar f(p), verder goed gegokt.

[Verwijderd]

Verwijderd schreef op donderdag 20 juli 2006 @ 23:25:
voor deze pascal code?

Delphi:

procedure f(var p: Tree);
begin
  p := Tree.Create();
end;

procedure main
var
  p: Tree;
begin
  p := Null;
  f(p);
  p.value=10;
end;

Volgens TS was die C++ code een letterlijke omzetting van de Pascal source uit 't boek, dus dat zal dan wel, want jouw terugvertaling is ook vrij letterlijk.
Maar ik heb nog niet vaak zulke ranzige Pascal code gezien...

[sirdupre]

Maar nog steeds is de recursie in het voorbeeld me niet duidelijk...

Een functie roept een andere functie aan, die een object aanmaakt. Daar is toch niets recursiefs aan?

[Robtimus]

SirDupre schreef op vrijdag 21 juli 2006 @ 00:32:
Maar nog steeds is de recursie in het voorbeeld me niet duidelijk...

Een functie roept een andere functie aan, die een object aanmaakt. Daar is toch niets recursiefs aan?

Ik denk dat ie op functie "insert" doelt.

[sirdupre]

Ah, ik snap het .

In C++ en Java lijkt het mij mooier om dat soort dingen te doen als een methode van een klasse. Je zou dan in java iets krijgen als

code:

class Tree
{
    Tree left;
    Tree right;
    int value;

    // Create a Tree with the given value in its root.
    public Tree(int r)
    {
        value = r;
    }

    void insert(int v)
    {
        if (v <= value)
        {
            if (left == null) left = new Tree(v);
            else left.insert(v);
        }
        else
        {
            if (right == null) right = new Tree(v);
            else right.insert(v);
        }   
    }
}

Als je nu ergens iets doet als

code:

Tree t = new Tree(8);
t.insert(4);
t.insert(12);
t.insert(9);
t.insert(5);
t.insert(2);
t.insert(15);

Dan heb je de volgende boom

code:

        8
     /     \
   4         12
 /   \      /   \
2     5    9    15

Het voornaamste verschil is in feite dat je bij jouw voorbeeld (en dus blijkbaar in Pascal?) een pointer meegeeft naar het object aan je insert functie, terwijl je in C++ of Java logischerwijs alleen een insert kunt aanroepen als je al een Tree object hebt. Als het ware vraag je dan aan de boom of hij zijn insert wil uitvoeren gegeven een getal dat je in wilt voegen, terwijl je in het oorspronkelijke voorbeeld aan een insert methode vraagt om gegeven een getal en een pointer naar een al dan niet bestaande boom te zorgen dat die pointer een boom zal bevatten waarin dat getal voorkomt.

Misschien gaat je hoofd nu duizelen, maar probeer je dan in te denken dat in het oorspronkelijke voorbeeld de boom en de insert-functie in feite niet direct met elkaar verbonden zijn. Die insert maakt gebruik van de Tree, maar staat wel op zichzelf.
In het java voorbeeld is de insert-functie eigenlijk echt van de Tree zelf. Als er geen boom is, kan je hem ook niet aanroepen.
Op het gebied van datastructuren neig ik toch te zeggen dat dat laatste mooier is, omdat een datastructuur eigenlijk meer is dan een manier van opslag. Een datastructuur is een manier van opslag met een aantal operaties (in dit geval dus insert) die op die opslag werken. En dat is wat een klasse precies doet: je koppelt de opslag aan de operaties.

[ Voor 45% gewijzigd door sirdupre op 21-07-2006 10:22 ]

[Verwijderd]

... klopt je opmerking alsnog niet, want p in main() krijgt helemaal nix toegewezen en behoudt daarom gewoon zijn beginwaarde (null). Het echte probleem is namelijk dat de p in f() waar je wel geheugen aan toewijst een kopie is van de p in main(), dus je programmaatje dereferenced zowel een nullpointer EN bevat een geheugenlek, al met al geen slechte beginnersscore.

Ik had al een tijdje (3 jaar ofzo) niet meer in C++ geprogrammeerd
Maar goed, ik was in de war met het feit dat de waarde van een pointer wel in de functie aangepast kan worden. Je opmerking heeft mij op het idee gebracht om een pointer naar een pointer te gaan gebruiken.

In elk geval, als je een volledig gevulde binaire boom met diepte n in java wilt waarin je ints kunt opslaan, zou ik iets doen als:

Als ik weer met Java aan de slag ga, zal ik je voorbeeld eens uitproberen, bedankt!

Ik denk dat ie op functie "insert" doelt.

Klopt, de andere code was om het probleem te schetsen.

In C++ en Java lijkt het mij mooier om dat soort dingen te doen als een methode van een klasse. Je zou dan in java iets krijgen als

Dat vind ik ook mooier, als ik opgaven aan het maken ben of ik ben voor mezelf bezig dan implementeer ik datastructuren altijd in classes. Maar ik het boek wordt dat niet gedaan.

Bedankt voor je verdere uitleg, ik zal het eens bestuderen.

Nu de Pascal code uit het boek:

code:

procedure insert(a: integer, var p: tree)
begin
   if p=nil then
   begin new(p); p^.w=a; p^.l=nil; p^.r=nil end
     else if a<p^.w then insert(a, p^.l)
     else if a>p^.w then insert(a, p^.r)
end

Maar zoals ik hier boven al heb aangegeven, zal ik het eens proberen daar aan insert een pointer naar een pointer mee te geven. In Java (ook in C++) kan ik het proberen om insert een nieuwe instance terug te laten geven.
Dus genoeg ideeen om me niet te hoeven vervelen, dit weekend
Bedankt voor jullie reacties tot nu toe!

Nog een klein vraagje.
Hoe ken ik een waarde toe aan een pointer naar een pointer van een struct?
Bij een int variabele is het:

code:

**p=120;

Als ik het volgende doe:

code:

*p->w=10;

Geeft de compiler de volgende foutmelding:
left of '->w' must point to class/struct/union/generic type

[ Voor 8% gewijzigd door Verwijderd op 21-07-2006 21:37 ]

[H!GHGuY]

(*p)->w = 10

[Verwijderd]

HIGHGuY schreef op zaterdag 22 juli 2006 @ 09:56:
(*p)->w = 10

Bedankt, heb gisteravond van alles zitten proberen (kon het met google ook niet vinden), behalve dt

[H!GHGuY]

als je echt het schoolvoorbeeld wil van recursie experimenteer dan wat met de rij van fibonacci of zo...

[Soultaker]

HIGHGuY schreef op zondag 23 juli 2006 @ 11:28:
als je echt het schoolvoorbeeld wil van recursie experimenteer dan wat met de rij van fibonacci of zo...

...om maar een algoritme te noemen dat je beter iteratief kunt implementeren.

De operaties op de binaire boom waar de TS mee bezig is lijkt me veel geschikter. Recursie in combinatie met recursieve datatypes komt veel voor. Verder kun je aan recursieve algoritmen als quicksort denken.

[ Voor 29% gewijzigd door Soultaker op 23-07-2006 14:44 ]

[H!GHGuY]

Soultaker schreef op zondag 23 juli 2006 @ 14:43:
[...]
...om maar een algoritme te noemen dat je beter iteratief kunt implementeren.

juist maar dat is dan de volgende stap

[Verwijderd]

Soultaker schreef op zondag 23 juli 2006 @ 14:43:
[...]

...om maar een algoritme te noemen dat je beter iteratief kunt implementeren.

De operaties op de binaire boom waar de TS mee bezig is lijkt me veel geschikter. Recursie in combinatie met recursieve datatypes komt veel voor. Verder kun je aan recursieve algoritmen als quicksort denken.

Rij van fibbonacci heb ik ook gehad, toen zitten spelen met recursie vs een oplossing met een loopje. Wat bleek, de oplossing met recursie was veel langzamer (dat had ik me ook wel van te voren kunnen beredeneren ). Dus ging ik er van uit dat recursie altijd langzamer is, totdat ik er met een vriend over had (die veel verder is op programmeer gebied is ik). In sommige gevallen blijkt recursie dus toch de betere oplossing. Maar de vraag is, in welke gevallen?

Bij het voorbeeld van een Tree, waarom zou je hier voor de oplossing mbv recursie kiezen?

Trouwens, het is me nog niet gelukt om de delete functie in C++ te vertalen, maar ik wil niet al te tlang stilstaan bij een onderwerp, dus ik kom hier zeker nog op terug

[Robtimus]

Verwijderd schreef op dinsdag 25 juli 2006 @ 21:32:
Bij het voorbeeld van een Tree, waarom zou je hier voor de oplossing mbv recursie kiezen?

Omdat lineair door de tree lopen orde N is, en de binaire versie (wat deze boom is) orde X log(N) (welke waarde X heeft weet ik niet). Anyway, in dit geval is de tree gewoon efficienter.

Waarom recursieve fibonacci dan zo traag is? Omdat je veel waarden dubbel zit uit te rekenen.
Voorbeelde: fib( 10 ) = fib( 9 ) + fib( 8 ) = (fib( 8 ) + fib( 7 )) + fib( 8 ). fib( 8 ) ga je nu twee keer recursief uitrekenen, het lijkt me duidelijk dat dat slecht voor performance is.

Naast de recursieve en lineaire versies bestaat er trouwens ook een versie met orde log(N), welke in theorie werkt met matrices maar in de praktijk met 4 variabelen (plus tijdelijke).

[.oisyn]

En er is natuurlijk ook gewoon een O(1) versie voor fibonacci getallen:

fib(n) = ((1 + √5)ⁿ - (1 - √5)ⁿ)) / (2ⁿ√5)

[ Voor 5% gewijzigd door .oisyn op 25-07-2006 22:13 ]

[JeRa]

.oisyn schreef op dinsdag 25 juli 2006 @ 22:12:
En er is natuurlijk ook gewoon een O(1) versie voor fibonacci getallen:

fib(n) = ((1 + √5)ⁿ - (1 - √5)ⁿ)) / (2ⁿ√5)

offtopic:
Nou ben ik geen held in het bepalen van de Big O-waarde, maar is dat niet O(n) vanwege die machtsverheffingen? (het lijkt me dat die, afhankelijk van de waarde n, niet altijd in O(1) kunnen worden berekend)

[.oisyn]

Ik snap niet helemaal in welke hoek je je opmerking bedoelt. Als het puur om het theoretische algoritme gaat is machtsverheffen gewoon een O(1) operatie. In de praktijk is de implementatie in de CPU natuurlijk niet geheel O(1), maar verhoudt het zich tevens ook niet tot n omdat er een minimum en een maximum aan zit (stel het hangt af van het aantal gezette bits in de mantissa, dan heb je met een float nog altijd maar maximaal 24 bits, hoe groot n ook is - hoe het daadwerkelijk zit weet ik niet precies, ze gebruiken daar meestal lookup tables voor).

[Soultaker]

Het idee van complexiteitsanalyse is dat alle basale operaties (alles wat O(1) is) binnen een vaste tijd uitgevoerd kunnen worden. Machtsverheffen met willekeurige getallen lukt niet in O(1). Als je je tot de MMU van een echte computer beperkt is dat wel O(1) maar dan is de uitkomst niet meer exact en dan is het algoritme vanuit theoretisch oogpunt dus waardeloos. Dan kun je net zo goed de eerste zoveel getallen in een array stoppen en die er in O(1) uitvissen.

Wat bij Fibonacci reeksen ook nog wel relevant is, is dat je computer helemaal niet in O(1) getallen kan optellen, vermenigvuldigen en delen, zodra die getallen niet meer in registers passen. Dat moet je eigenlijk meenemen in je berekeningen.

Tenslotte is er een slim truukje om Fibonacci reeksen in O(log N) uit te rekenen (uitgaande van rekenkundige operaties in O(1)), dat trouwens werkt voor alle lineaire recurrente betrekkingen: als je de 2x2 matrix [ 1 1 | 1 0 ] tot de n^de macht verheft, staat linksboven het n^de Fibonacci-getal. Machtsverheffen met geheeltallige machten kan eenvoudig in O(log N).

[ Voor 4% gewijzigd door Soultaker op 25-07-2006 23:05 ]

[DroogKloot]

whosvegas schreef:
[...]

In sommige gevallen blijkt recursie dus toch de betere oplossing. Maar de vraag is, in welke gevallen?

In alle gevallen waarbij je langer dan 5 minuten na moet denken over een iteratieve oplossing. Probeer bijvoorbeeld maar eens een pre-/in-/post-order tree traversal te implementeren zonder recursie, dat lukt je al niet zonder zelf een stack van nodes bij te houden (en dan ben je stiekem toch weer semi-recursief bezig), en het wordt nog veel erger als je de tree ook van vorm wilt veranderen. Maarja, voor het genereren van die knullige Fibonacci-getalletjes zijn zulke overwegingen niet echt relevant.

Bij het voorbeeld van een Tree, waarom zou je hier voor de oplossing mbv recursie kiezen?

Omdat een tree van nature een recursieve structuur heeft. Operaties op een tree kun je om die reden recursief in een paar regels uitdrukken, waar het je iteratief hele lappen code kost. Die iteratieve code kan dan wel sneller zijn (wat overigens lang niet altijd gezegd is, en bovendien zal het nooit meer dan een constante factor schelen), maar dat weegt bijna nooit op tegen de veel grotere lees- en onderhoudbaarheid van een recursieve versie.

[ Voor 4% gewijzigd door DroogKloot op 25-07-2006 23:00 ]

[Soultaker]

Verwijderd schreef op dinsdag 25 juli 2006 @ 21:32:
Rij van fibbonacci heb ik ook gehad, toen zitten spelen met recursie vs een oplossing met een loopje. Wat bleek, de oplossing met recursie was veel langzamer (dat had ik me ook wel van te voren kunnen beredeneren ).

Tja, als je 'm recursief geïmplementeerd had als f(n) = f(n-1) + f(n-2) dan is het gewoon een heel ander algoritme dan wanneer je iets doet als int a = 1, b = 1; while(--n) { int c = a + b; b = a; a = c }. Dat heeft weinig met recursie te maken.

Dus ging ik er van uit dat recursie altijd langzamer is, totdat ik er met een vriend over had (die veel verder is op programmeer gebied is ik). In sommige gevallen blijkt recursie dus toch de betere oplossing. Maar de vraag is, in welke gevallen?

Meestal bij divide-and-conquer algoritmen, zoals quicksort en mergesort, en bij depth-first search. Vaak kom je algoritmen tegen die je eigenlijk alleen recursief kunnen, of je moet expliciet een stack of een queue toevoegen. Vaak kun je dan net zo goed recursief programmeren.

Bij het voorbeeld van een Tree, waarom zou je hier voor de oplossing mbv recursie kiezen.

Stel dat je een boom hebt, en je wil alle waarden erin optellen. Hoe zou je dat niet recursief willen doen? (Het kan wel, maar je moet dan een stack of een queue gebruiken.) Recursief is het triviaal.

[sirdupre]

Over het gebruik van een stack of een queue:

In feite gebruik je bij een recursief algoritme impliciet een stack (wel te weten de call-stack). Dit kun je ook expliciet maken, door een gewone while lus te gebruiken, met iets als while (!stack.isEmpty()){...}.
In feite is bij een recursieve methode de aanroep van de eigen methode een push operatie en return een pop operatie. Wat mij betreft is dat juist een vrij belangrijk inzicht.

En ehm, fibonacci kan ook in O(n) recursief hoor.

code:

int fibo(int n)
{
if (n < 2) return n;
return fibohelper(0,1,n-2);
}

int fibohelper(int a, int b, int n)
{
if (n < 1) return a + b;
return fibohelper( b , a + b, n-1);
}

in tegenstelling tot het voor de hand liggende

code:

int fibo(int n)
{
if (n < 2) return n;
return fibo(n-1) + fibo(n-2);
}

wat dus inderdaad een hoop dubbel werk doet. (Volgens wikipedia zelfs O(2ⁿ) (wel met een c < 1 )).

[ Voor 17% gewijzigd door sirdupre op 25-07-2006 23:45 ]

[Verwijderd]

Bedankt voor de reacties!
Ik zal ze binnenkort bestuderen (op het moment is de warmte wat naar m'n hoofd gestegen )

[H!GHGuY]

iedereen post hier naast de kwestie: wanneer is recursie niet overbodig ?

zonder al te veel details:
elke functie oproep plaatst enkele gegevens op de call-stack (voornamelijk de inhoud van de registers, terugkeerpunt, etc). Elke return uit een functie oproep haalt die er terug af.

wanneer is recursie dus af te raden: als de hoeveelheid werk binnen de recursieve aanroep te klein is.
Als je recursief bergen verzet is die recursie geen probleem, maar als je louter de som van 2 getalletjes moet returnen kun je misschien beter eens langer nadenken over hoe het zonder kan.

wat met inlining dan?
inlining is een techniek waarbij de compiler functies die zeer klein zijn wegoptimaliseert door de functiebody telkens in te voegen op de plaats waar je de functie oproept. inlining kan je echter niet gebruiken bij recursie. je zou immers oneindig lang inlinen...

om het verhaal kort te houden:
recursie als: je genoeg werk hebt per oproep, als het algoritme dit niet toelaat (of te moeilijk wordt als je recursie wil verwijderen)
geen recursie als: je mini-functies schrijft (deze zijn meestal ook het eenvoudigst niet-recursief te maken)

het bijhouden van een eigen stack werd hier al vernoemd. Dit is bij goed gebruik sneller wanneer je toch weinig werk moet verzetten per oproep. Het lijkt misschien wel iets meer werk natuurlijk.

[.oisyn]

HIGHGuY schreef op donderdag 27 juli 2006 @ 11:45:
wat met inlining dan?
inlining is een techniek waarbij de compiler functies die zeer klein zijn wegoptimaliseert door de functiebody telkens in te voegen op de plaats waar je de functie oproept. inlining kan je echter niet gebruiken bij recursie. je zou immers oneindig lang inlinen...

Niet oneindig nee, maar er kan weldegelijk geinlined worden. VC++ kan dat tot 254 niveaus diep als ik me niet vergis. Overigens komt inlining de performance niet altijd ten goede (meer code cache misses, slechtere branch prediction), het is vooral nuttig bij kleine functies zodat het registergebruik door de compiler beter gebalanceerd kan worden en de opbouw van de stackframe kan worden vermeden.

[ Voor 4% gewijzigd door .oisyn op 27-07-2006 12:29 ]

[H!GHGuY]

.oisyn schreef op donderdag 27 juli 2006 @ 12:28:
[...]
Niet oneindig nee, maar er kan weldegelijk geinlined worden. VC++ kan dat tot 254 niveaus diep als ik me niet vergis. Overigens komt inlining de performance niet altijd ten goede (meer code cache misses, slechtere branch prediction), het is vooral nuttig bij kleine functies zodat het registergebruik door de compiler beter gebalanceerd kan worden en de opbouw van de stackframe kan worden vermeden.

je las even over

zonder al te veel details:

maar om er toch nog even op in te gaan: de compiler beslist (zonder specifieke opties) toch zelf of een functie al dan niet geinlined wordt.

"inline" en inline definitie van class members zijn niet meer dan de functie kandidaat stellen voor inlining.

[.oisyn]

Sterker nog, het inline keyword heeft maar weinig betekenis. Niet-inline functies kunnen ook geinlined worden, en inline functies kunnen ook niet geinlined worden. Inline is in principe alleen echt bruikbaar om de ODR niet te violaten, voor de rest mag de compiler het zelf beslissen.

[H!GHGuY]

dat is wat ik bedoelde