Stakke og køer

Hvis der er en der osse kan komme med et pragt examplar af et exempel på en funktion hvor det ville være MEGET smartere at bruge rekursion frem for en almindelig løkke.. jeg kan ikke rigtigt komme frem til et selv :)

Det smarte ved en kø er bla., at man kan lave en producer/consumer. Dvs. et objekt der producerer data, og et objekt der forbruger data. Feks. en Printer-kø. En printer-kø bør altid være FIFO, og derfor er data-strukturen \"en kø\" velegnet til at implementere dette.

Hvor er det bedre end et array eller en alm. hægtet liste?????
Det er et godt spørgsmål, men det er nemmere at implementere en stak/kø end en liste, da der ikke er brug for traversering, dvs. det er hurtigere. Men du har ret->Det er en begrænsning af en liste.

Den helt store forskel mellem et array og en stak/kø, er jo at stakke/kø\'er (og også lister) er dynamiske hvor array er statiske.

Et eksempel på rekursion:

Et binært søgetræ:

class Knude
{
  friend class Bintrae;
private:
  String navn;
  Knude *venstre, *hoejre;
};

class Bintrae
{
public:
  UdskrivInorder();
  //...
private:
  Knude* rod;
  UdskrivIn(Knude* r);
  //...
};

void Bintrae::UdskrivInorder()
{
  cout << \"Traeet udskrives InOrder:\" << endl;
  UdskrivIn(rod);
}

void Bintrae::UdskrivIn(Knude* r)
{
  if (r != NULL)
  {
    UdskrivIn(r->venstre);  //rekursivt kald
    cout << r->navn << endl;
    UdskrivIn(r->hoejre);    //rekursivt kald
  }
]

Mht rekursion, så er QuickSort det bedste eksempel på en funktion der er nemmest at implementere rekursivt. Faktisk er den ret svær IKKE at implementere rekursivt.
Andre eksempler kunne være fibonacci\'s talrække eller Pascals trekant.

henrik_ffc >> Yes, godt eksempel...

Kamikaze> Ja, et binært søgetræ er da også er ret god eksempel....

Hanoi\'s tårne er også ret svær at implementere iterativt.

damon, du har ganske ret, man kan sagtens udtage værdier fra et array efter hvilken metode man ønsker! Det der er relevant, når man implementerer en datastruktur, er nogle overvejelser omkring brugen heraf...
Fordelen ved den arraybaserede implementation er fx hurtig tilgang (et array er jo i sin natur indexeret). Man KAN spare tid ved allokering, idét et array jo oftest allokeres for flere elementer ad gangen. Skal man dog ofte fjerne eller indsætte elementer, giver det en masse memory-management, idet alle elementer i arrayet skal reallokeres hver gang og det tager tid!
En liste derimod fungerer jo således, at der allokeres memory for hver element. Hver element har så en pointer til næste element (og forrige, hvis det er en dobbelthægtet liste) Det fylder altså lidt mere i RAM (pga. pointeren) og er langsommere at søge igennem, da man altid skal starte fra enden! Til gengæld er der den fordel, at man let kan fjerne eller indsætte et element, da man ikke skal reallokere noget af det eksisterende.

=>kamikaze, lige et par kommentarer

\"En printer-kø bør altid være FIFO\"
Hvorfor det?
Mange operativsystemer anvender en kø der er prioritetsbestemt, således at det job med højeste prioritet bliver udført først (en administrator bør fx have mulighed for at ændre udskriftsrækkefølgen). En anden metode kunne være SJF (Shortest Job First). Hvis der fx er et 500 siders job der ligger før 10 jobs på hver én side, så ville man helt sikkert få en større brugertilfredshed ved at udskrive de 10 små jobs først!

\"array er statiske\"
Nej, det passer ikke nødvendigvis. Et array kan sagtens være implementeret dynamisk...

Og så lige ang. rekursion:
Det er en smart måde at lave noget lækkert og simpelt kode på, men hastigheden er ikke altid lige god, sammenlignet med sekventiel kode...
En grund hertil er, at det ofte er svært for compileren at optimere rekursiv kode.

JPK>>
<CITAT>Det er en smart måde at lave noget lækkert og simpelt kode på, men hastigheden er ikke altid lige god, sammenlignet med sekventiel kode...
En grund hertil er, at det ofte er svært for compileren at optimere rekursiv kode.</CITAT>

En anden årsag til den dårligere hastighed er den overhead der opstår ved hver kald af funktionen.
Et funktionskald tager jo også tid, fx. fordi variable skal gemmes på stakken og returneres når funktionen er afsluttet.
Og i sagens natur har en rekursiv funktion [ofte mange] flere funktionskald end en iterativ funktion.
Så en iterativ funktion vil altid være hurtigst, men en rekursiv vil typisk være nemmere eller \"smukkere\" at implementere...

Ganske enig...

Luk venligst dette spørgsmål ;o)

pokemaster:> Du SKAL kun KOMMENTERE spørgsmål vedr. lukning, ikke svare på dem og derved få point på uærlig vis!