Dette er rekursjon, fordi som ikke vet det!

[Gjakmarrja]

Et problem kan ofte løses ved at vi deler det opp i mindre problemer. Av og til kan ett eller flere av disse mindre problemene være av samme type som det opprinnelige problemet.

 

et dagligdags eksempel har vi når vi slår opp i telefonkatalogen. La oss si at vi skal finne Ingvild Jensen. Først slår vi opp på en mer eller mindre tilfeldig side mellom A og Å, og finner f.eks at denne siden har navn som begynner på L. Da vet vi at vi må lete etter Ingvild fra begynnelsen av katalogen fram til denne siden(siden J kommer foran L). Men det er akkurat samme problemet som å lete i hele katalogen, bare at nå har vi færre sider å lete blant. Så vi slår opp på en tildfeldig side mellom A og L, og treffer kanskje på siden med navn på G. Da har vi redusert problemet enda et hakk, og trenger bare å lete mellom G og L. Slik kan vi fortsette å redusere antall sider å lete blant, helt til vi finner den siden hvor Ingvil må være. I hver runde prøver vi å løse problemet "finn Ingvil Jensen blant sidene mellom x og y", der x og y er bokstavene som stadig nærmer hverandre. Til slutt finner vi løsningen på problemet "finn Ingvild Jensen blant sidene mellom J og J", og da har vi også funnet løsningen på det opprinnelige problemet "finn Ingvild Jensen blant sidene mellom A og Å".

 

Når vi programmerer, lager vi gjerne en metode for å løse et problem. Hvis det viser seg at vi trenger løsningen på et tilsvarende problem, bruker vi den metoden vi har laget. Det kan vi også gjøre mens vi holder på å lage løsningen på det opprinnelige problemet. Da får vi det vil kaller reskursjon.

 

Kort:

 

En algoritme som kaller seg selv, kalles en rekursiv algoritme.

 

Noen ganger har vi indirekte rekursjon. Det betyr at en algoritme kaller en annen algoritme, og den andre kaller den første igjen. Eventuelt kan vi ha flere algoritmer mellom den første og den som kaller den!

 

Håper dette hjelper!

 

EDIT:

 

I bunn og grunn så er det mange "nybegynnere", som har brukt uten og vite hva det heter!

Endret 4. september 2005 av chills

[mar]

Du var veldig uheldig med eksemplet her (mulig det strengt tatt blir helt feil, men er ikke helt sikker). Det du beskriver er et enkelt binærsøk. Husker jeg ikke helt feil så er kjennetegnet på en rekursivalgoritme at den "løper" til bunnen av rekursjonstreet(til den treffer et basetilfelle) også setter den sammen delsvarene, mens den jobber seg oppover i treet igjen. Er lenge siden så jeg husker ikke helt.

 

Er litt bedre eksempel:

 

Fibonacci_number

 

Her er vært tall lik summen av de to foregående og basetilfellene er 0/1.

 

får da at "Fibonacci(10) = Fibonacci(9) + Fibonacci(8)" OSV

 

Helt til man kommer til "Fibonacci(1)" som er "1". Da kan man begynne å jobbe seg oppover i rekursjonstreet igjen.

Endret 4. september 2005 av mar

[Gjakmarrja]

Jeg håper innderlig ikke at det er feil... det er direkt avskrift fra en bok som heter Algoritmer og datastrukturer av Helge Hafting, Mildrid Ljosland.

 

Tenkte bare jeg skulle skrive det her... gadd faktisk og gå til byn for å låne boken på biblioteket... men for all del er du sikker på det er feil så kan jeg fjerne det?

Men i bunn og grunn kan vel en hver funksjon som kaller seg selv kalles rekursjon!

[mar]

Er mulig man kan kalle det en rekursiv metode. Selv vil jeg si at den er itterativ og ikke rekursiv, men nå er det en stund siden sist jeg grublet over sånt. Er mulig at jeg tenker litt mer på algoritmenivå, mens forfatteren utelukkende ser på selve programkoden. Hadde vært greit om noen flere hadde hatt noen meninger her. Sist jeg var borti dette var våren 2003. Drev til og med og rettet innleveringoppgaver med rekursjon det semseteret, så jeg burde jo husket dette her

 

Edit: Det er mulig med en rekursiv implementasjon av binærsøk. Så var det sagt. Måtte bare tenke litt Var nok jeg som var litt for teoretisk av meg. Blir fort sånn etter litt mange vekttall med algoritmeteori.

Endret 4. september 2005 av mar

[A_N_K]

Det her var ikke noe prakteksempel på rekursjon vil jeg mene, slik det er forklart kan det fint gjøres iterativt.

[GeirGrusom]

Det er veldig vanskelig å finne et dagligdags eksempel på rekusjon, men skal du løse et regnestykke med parantes, må du bruke rekursjon, ihvertfall hvis du gjør det på en datamaskin.... det er derfor det er vanskelig å lage et daglidags eksempel på rekursjon, fordi et menneske kan raskt skaffe seg oversikt over et problem, det kan ikke datamaskiner, den ser bare en liten del av problemet av gangen.

 

Men der ville jeg først gått fra Å / 2, altså midten, funnet ut om L er høyere eller lavere, og gått den veien som passer, helt til jeg fant J, og repetert dette til jeg fant Jensen, og deretter letet etter Ingvil blant de resterende mulighetene, iterativt.

Endret 7. september 2005 av GeirGrusom

[Iyon]

Dette er ihvertfall slik jeg lærte forskjellen en gang:

 

 

Utskrift av en liste med navn ordnet i en lenket liste

 

metode 1

 

Node betraktet = listehode;

while (betraktet != null)
       print(betraktet.getName();
       betraktet = betraktet.getNext();

 

 

metode 2: metoden under er deklarert i objektklassen Node

 

String printList()
       if (this.nesteNode != null) return this.navn + nesteNode.printList();
       else return this.navn;

Et kall til listeHode.printList() vil da skrive ut hele listen uten imperativ iterasjon.

 

 

Eksemplene er kanskje ikke så enkle å forstå for de som ikke er helt fortrolige med lenkede lister, men jeg regner med at de fleste som tråler dette forumet er det.

[GeirGrusom]

class familymember
 familymember[] children;
 familymember spouse;
 string name;

fn string write_tab(int tabs)
 string ret
 for int x = 0 to tabs
   ret += 0x08
 return ret

fn recurse_familytree(int tab, familymember member)
 print member.name

 if member.children.length == 0
   print "No children"
 else
   print member.children.length + " children"

 print member.spouse.name
 for each familymember child in member.children
   recurse_familytree tab + 1, write_tab(tab) + child