[MatLab (Python-lignene)] Hvordan fungerer denne koden? (rekursiv)

[Reeve]

Hei

 

Jeg har fått en relativt enkel oppgave der jeg skal skrive en rekursiv funksjon som skal regne ut summen av alle tall fra 1 til n, hvor n er gitt som et paramterer.

 

Til å begynne med, skrev jeg den vha. for-løkker, men fant senere ut at dette ikke var rekursive koder. Min kode fungerte, men vil gjøre den med rekursiv kode i stedet for løkker.

 

Derfor sjekket jeg løsningsforslaget, som er følgende:

 

function sum = recurSum(N)

if N == 1
sum = 1;
else
sum = N + recurSum(N-1);
end
end

 

Det jeg ikke forstår er hvordan denne koden fungerer. Jeg har testet den og den gir korrekte svar, men jeg forstår ikke helt hvorfor. Hvis jeg går gjennom koden med f.eks. N = 10; da vil den gå til else og sette sum = 10+recurSum(9), men neste gang vil den "erstatte" sum med sum = 9 + recurSum(8) helt til den år sum = 1.

 

Hvorfor blir ikke alltid svaret 1?

[Lycantrophe]

Fordi sum = 1 ikke er det første som gjøres, det er det siste.

[Reeve]

Nettopp, og når den er ferdig, så printer den sum, som skal være 1. Men det som kommer ut er ikke 1, det er totalsummen og det forstår ikke jeg.

[Lycantrophe]

Sum skal da ikke være 1, det skal være summen av 1,2...n.

 

Åh, det er sånn du lurer på.

 

Vel, tingen er at når du kaller metoden din med n som parameter er det DET kallet sin "sum" som gjelder, ikke det siste kallet sin variabel. Sum er bare et logisk navn for din del, maskinen holder styr på variabler selv. Videre "lukkes" ingen av funksjonene som kalles underveis før den som returnerer 1 er ferdig å kjøre.

 

Jeg kan gjøre et raskt illustret eksempel.

 

 

 

recurSum(3), sum = ?

 

 

recurSum(2), sum = ?

 

 

recurSum(1), sum = ?

 

 

return 1

 

 

sum = 1, return 1+1

 

 

sum = 2, return 2+2

 

 

sum = 4, return 4+3

 

 

sum = 7

Endret 25. november 2011 av Lycantrophe

[aschj]

Hver iterasjon har sin egen sum-variabel, så ingenting blir overskrevet noe sted.

 

sum for N=1 vil være 1 før den returneres.

sum for N=2 vil være 2 + sum for N=1 før den returneres.

 

Og så videre.

Endret 25. november 2011 av aschj

[Reeve]

Takk for hjelpen, var det jeg trodde etter å ha stirret litt på den.

[torbjørn marø]

Gratulerer! Dette er et av de mest minnerike øyeblikkene i din karriære; første gang du så og forstod rekursjon - en av de viktigste byggeklossene vi har. Kanskje ikke noe alle bruker hele tiden, men forståelsen utvider hjernen din, og gjør deg til en bedre utvikler.

 

[Reeve]

Har gjort noen enkle oppgaver med rekursjon nå, og føler jeg forstår det godt. Likevel er jeg ikke imponert. I hvertfall i Matlab virker det som om det er veldig dårlig optimalisert kode. Jeg har gjort en oppgave som finner det N-te leddet i fibonacci-rekken.

 

Jeg har tidligere gjort oppgaven med løkker, som jeg føler gjør en grei jobb. Jeg kan da finne tall med flere hundre siffer, uten at det lagger. Mens med rekursjon, begynner den å lagge allerede på det 20. fibonacci-tallet ca, altså rundt 40 000, 5 siffer og noe sånt som 40 regneoperasjoner.

 

Løkker:

clear
f(1) = 1;
f(2) = 1;
n = input('Hvor langt vi skal gå: ';
for i=3:n
   f(i) = f(i-1) + f(i-2);
end
fprintf('F(%d) er %d \n', n, f(n));

 

Rekursjon:

function ut = fibonacci(N)
if N == 1 || N == 2
   ut = 1;
else

   ut = fibonacci(N-1) + fibonacci(N-2);
end
end

Endret 28. november 2011 av ChrisReeve

[Lycantrophe]

Det er ikke så rart. Hver gang du ber om et fibonacci-tall regner den ut alle tallene opp dit.

 

La meg illustrere:

 

Si at du skal regne ut det fjerde. Da vil rekursonen kalle:

 

Hva er 4.? Det er 3.+ 2. Da må vi ha det.

 

Hva er 3.? Det er 2. + 1. da må vi ha det.

 

Hva er 2.? Det er 1 (definert).

 

Da er 3. 2. + 1. (=2)

 

Okay, da har vi 3.! Nå trenger vi 2.!

 

Hva er 2.?

 

2. er 1. + 1 (definert).

 

Okay!

 

4. er 3!

 

 

Tenk deg nå denne med 20.

 

tl;dr: Hvert kall nedover mot basetilfellet generer n-1 NYE kall. Dette baller fort på seg. Løkkene, derimot, husker hele tiden hva de forrige verdiene er (slår bare opp i tabellen over tidligere utregnede verdier). Derfor blir ikke de trege.

[Reeve]

Takk for svar. Vi har kun lært det på denne måten (er som sagt IT grunnkurs), men er det en måte å optimalisere det på, eller vil den bare fungere dårlig på oppgaver som fibonacci?

 

I så fall, hva er rekursjon godt for?

[Lycantrophe]

Åh, rekursjon er bra for mye rart, men ikke til å finne det N-te fibonacci-tallet. Det er rett og slett feil type problem for et verktøy som rekursjon.

 

Bruk løkker.

Endret 28. november 2011 av Lycantrophe

[Turbosauen]

I så fall, hva er rekursjon godt for?

 

Sortering for eksempel. To vanlige sorteringsalgoritmer, kalt Merge sort og Quick sort, er rekursive metoder (sikkert fler og, men disse jeg kom på i farta). Her er pseudokode for Merge sort:

 

function merge_sort(m)
   if length(m) ≤ 1
       return m
   var list left, right, result
   var integer middle = length(m) / 2
   for each x in m up to middle
        add x to left
   for each x in m after or equal middle
        add x to right
   left = merge_sort(left)
   right = merge_sort(right)
   result = merge(left, right)
   return result

 

Hvor merge(liste1, liste2) er kode som slår sammen to sorterte lister til én sortert liste.

 

Kjapt fortalt består sorteringen rett og slett å dele lista i to, og sortere de hver for seg. Hver av disse sorteres ved å deles i to, og sortere halvdelene hver for seg. Det er forholdsvis lett å slå sammen to sortere lister til én sortert liste; velg hele tiden det laveste verdien fra de to listene (dette er implementert i merge-funksjonen).

 

Hvorfor sortere på denne måten spør du kanskje? De er rett og slett mye raskere* enn for eksempel Bubble sort, som man vel lærer i ITGK, hvor man sorterer ett og ett element ved hjelp av to løkker.

*ved store datamengder

[Matsemann]

Løkker:

clear
f(1) = 1;
f(2) = 1;
n = input('Hvor langt vi skal gå: ';
for i=3:n
   f(i) = f(i-1) + f(i-2);
end
fprintf('F(%d) er %d \n', n, f(n));

 

Rekursjon:

function ut = fibonacci(N)
if N == 1 || N == 2
   ut = 1;
else

   ut = fibonacci(N-1) + fibonacci(N-2);
end
end

Som Lycan sier, så må denne regne ut mye av det samme om og om igjen, noe som er bortkastet. Så her kan en vanlig for-løkke være greit.

Men en ting som ofte brukes i dynamisk programmering og rekursjon er memoisering. Da lagrer du resultatene underveis, og sjekker om du har regnet ut noe allerede før du gjør det.

 

Jeg kan ikke matlab, men tror det ville blitt noe slikt:

 

function ut = fibonacci(N)
if N == 1 || N == 2
   ut = 1;
else if harRegnetOtFor(N) > 0
   ut harRegnetOtFor(N)
else
   harRegnetOtFor(N) = fibonacci(N-1) + fibonacci(N-2);
   ut harRegnetOtFor(N)
end
end

Da får du en tabell med harRegnetOtFor(N) der N er det n'te fibonacci-tallet. Den må vel opprettes og alle settes til 0 før man begynner.

Endret 28. november 2011 av Matsemann

[Lycantrophe]

Det er jo på sett og vis det løkken gjør.

[Matsemann]

Ja, men poenget var å vise en rekursiv tilnærming til problemet.

[Lycantrophe]

Sånn å forstå, da gir det mer mening.

[snippsat]

I så fall, hva er rekursjon godt for?

Rekursjon er noe man bruker ofte i problem løsning.

for each possibility at level 1:
   for each possibility at level 2:

 

Du kan bruke for lopp viss du vet antall level.

Vet du ikke antall level kan man bruke rekursjon.

 

Viss man tenker på situasjon som kan skje utenfor pcen.

Du skal i et møte,du vet hvilken etasje.

Når du kommer opp er ingen dører merket,du starter da og prøve dør for dør til du finner riktig rom.

Du har da bruk en Backtracking algoritme.

 

Stikkord:Rekursjon,Brute force,Backtracking

Er viktige verktøy i problem løsning.

 

En rekursiv løsning kan være mer effektiv enn en brute force løsning.

Et klassik eksempel er Eight queens puzzle

Et annet eksempel er Tree traversal hvor man ofte bruker rekursjon.

Endret 29. november 2011 av SNIPPSAT

[torbjørn marø]

Grunnleggende sett kan man si at programmering består av fire ting:

• Assignment - altså tilordne en verdi (til en variabel). Det finnes flere språk som ikke støtter dette..
  
• Decission - utføre ulike ting basert på resultatet av en test (if/else). Alle språk må ha dette.
  
• Iteration - gjøre ting mange ganger (løkker, rekursjon, goto). Noen språk har bare rekusjon, noen språk har bare løkker, noen språk har bare goto.
  
• Abstraction - å gruppere og "hjemme bort" funksjonalitet (prosedyrer/funksjoner/moduler/objekter).
  

 

Uansett hvilket språk du bruker, og hva det er du skal lage - og om du programmerte i 1960 eller gjør det i dag - så er det disse byggeklossene du bruker.

 

I noen språk og for noen problemer er det mer naturlig å bruke rekursjon enn løkker. I f.eks. Scheme, Clojure eller Haskell har man ingen løkker. I Clojure spesifikt har man noe som heter loop, men det er egentlig en rekursiv makro.

 

Ett av hovedproblemene med løkker er at det krever det man kaller bi-effekter, typisk i form av assignment (i denne konkrete oppgaven: f(i) = f(i-1) + f(i-2);

 

Assignment introduserer en rekke problemer, som gjør at enkelte språk (de funksjonelle) skyr dem som pesten. Kode med bi-effekter er f.eks. ikke lett å parallellisere, og ikke like enkel å optimalisere.

 

(For mer om hvordan disse løses ulikt i ulike språk anbefaler jeg at du følger med i julekalenderen min som starter på torsdag..)