26 svar
107 visningar
destiny99 7842
Postad: 24 okt 21:09

Rekursiv kod

Hej!

 

jag har svårt att tolka vad denna kod ska skriva ut. Hur börjar man? Jag testkörde den men förstår ej vad som händer på vägen till svaret förutom att if villkoren inte uppfylls i början

Laguna Online 30305
Postad: 24 okt 21:15

Så då returneras alltså r(a-2, b) + r(a, b-3), dvs. r(2, 4) + r(4, 1).

Ta en av dem i taget. Vad returnerar r(2, 4)?

destiny99 7842
Postad: 24 okt 21:36
Laguna skrev:

Så då returneras alltså r(a-2, b) + r(a, b-3), dvs. r(2, 4) + r(4, 1).

Ta en av dem i taget. Vad returnerar r(2, 4)?

r(2,3)?

Laguna Online 30305
Postad: 25 okt 06:38

Nej, hur fick du det? Gör samma sak med r(2, 4) som jag gjorde ovan.

2 och 4 är positiva, så den gör r(a-2, b) + r(a, b-3) igen, vilket är r(0, 4) + r(2, 1) den här gången.

Vad blir r(0, 4)?

destiny99 7842
Postad: 25 okt 06:43 Redigerad: 25 okt 06:47
Laguna skrev:

Nej, hur fick du det? Gör samma sak med r(2, 4) som jag gjorde ovan.

2 och 4 är positiva, så den gör r(a-2, b) + r(a, b-3) igen, vilket är r(0, 4) + r(2, 1) den här gången.

Vad blir r(0, 4)?

Jag förstår inte hur detta ska gå till. Är ganska förvirrad.. vi börjar med parametrar 4 och 4 som inte uppfylls och sen kommer vi till sista raden return (a-2,b) +r(a,b-3) och det blir med insatta värden på a=b=4 , return r(2,4)+r(4,1). Sen nästa gång har vi r(0,4)+r(2,1). r(0,4) blir r(-2,4)+r(0,1)

thedifference Online 350
Postad: 25 okt 06:52
destiny99 skrev:
Laguna skrev:

Nej, hur fick du det? Gör samma sak med r(2, 4) som jag gjorde ovan.

2 och 4 är positiva, så den gör r(a-2, b) + r(a, b-3) igen, vilket är r(0, 4) + r(2, 1) den här gången.

Vad blir r(0, 4)?

r(0,4) blir r(-2,4)+r(0,1)

Blir det? Kommer funktionen nå sista raden om a är 0?

destiny99 7842
Postad: 25 okt 07:11 Redigerad: 25 okt 07:20
thedifference skrev:
destiny99 skrev:
Laguna skrev:

Nej, hur fick du det? Gör samma sak med r(2, 4) som jag gjorde ovan.

2 och 4 är positiva, så den gör r(a-2, b) + r(a, b-3) igen, vilket är r(0, 4) + r(2, 1) den här gången.

Vad blir r(0, 4)?

r(0,4) blir r(-2,4)+r(0,1)

Blir det? Kommer funktionen nå sista raden om a är 0?

Ingen aning jag följer bara det laguna skrev.  Nångång måste den uppfylla en av if satserna. 

thedifference Online 350
Postad: 25 okt 07:23

Ja, och nån gång måste den specifikt uppfylla den första if satsen, annars har du oändlig rekursion, det som leder till stack overflow. All rekursion måste ha ett "base case" där den inte anropar sig själv igen.

Fyll i det här trädet:

destiny99 7842
Postad: 25 okt 07:29 Redigerad: 25 okt 07:32
thedifference skrev:

Ja, och nån gång måste den specifikt uppfylla den första if satsen, annars har du oändlig rekursion, det som leder till stack overflow. All rekursion måste ha ett "base case" där den inte anropar sig själv igen.

Fyll i det här trädet:

Hur kommer jag till r(0,3) från r(0,4)+r(2,1)? Om jag använder a=0 och b=4 till r(a-2,b) får jag negativt uttryck dvs r(-2,4) medan r(a,b-3) ger mig positivt uttryck r(0,3).  Varför måste vi använda oss av r(a,b-3) för att komma till r(0,3) och inte r(-2,4)?

thedifference Online 350
Postad: 25 okt 07:31

För att r(0,4) kommer trigga andra if-satsen. Jag har inte skrivit ut stegen för r(2,1). De är upp till dig att lista ut. Likadant med r(4,1) högre upp i trädet.

destiny99 7842
Postad: 25 okt 07:32 Redigerad: 25 okt 07:36
thedifference skrev:

För att r(0,4) kommer trigga andra if-satsen. Jag har inte skrivit ut stegen för r(2,1). De är upp till dig att lista ut. Likadant med r(4,1) högre upp i trädet.

Jag kan inte riktigt lista ut det. Men är detta ett matematiskt uträkning vi ska göra med trädet? Hur vet jag vad som triggar andra if satser eller inte? Jag ser inte vad som händer framför mig

Laguna Online 30305
Postad: 25 okt 07:39

Vi kör bara koden, uppifrån och ner, precis som datorn gör.

När a = 0, som den är i r(0, 4), så blir andra if-testet sant.

destiny99 7842
Postad: 25 okt 07:41 Redigerad: 25 okt 07:44
Laguna skrev:

Vi kör bara koden, uppifrån och ner, precis som datorn gör.

När a = 0, som den är i r(0, 4), så blir andra if-testet sant.

Okej men i andra if testet har vi även return r(a,b-1) som körs om a är sant. Så r(0,4) , r(0,3), r(0,2) , r(0,1) och r(0,0) uppfyller andra if satsen ?

thedifference Online 350
Postad: 25 okt 07:51

Måste sticka men snabbt: Tolka alla streck som pilar uppifrån till ner. Trädet börjar överst. r(0, 4) leder till r(0, 3) baserat på vad funktionen gör när a är 0 och b är 4. Likadant leder r(0, 3) till r(0, 2).

Laguna Online 30305
Postad: 25 okt 08:14
destiny99 skrev:
Laguna skrev:

Vi kör bara koden, uppifrån och ner, precis som datorn gör.

När a = 0, som den är i r(0, 4), så blir andra if-testet sant.

Okej men i andra if testet har vi även return r(a,b-1) som körs om a är sant. Så r(0,4) , r(0,3), r(0,2) , r(0,1) och r(0,0) uppfyller andra if satsen ?

Det stämmer att r(0, 4), r(0, 3), r(0, 2) och r(0,1) skulle gå andra if-satsen att bli sann, men a och b har bara ett värde i taget. När vi anropar r(0, 4) så är a = 0 och b = 4.

destiny99 7842
Postad: 25 okt 08:23 Redigerad: 25 okt 08:25
Laguna skrev:
destiny99 skrev:
Laguna skrev:

Vi kör bara koden, uppifrån och ner, precis som datorn gör.

När a = 0, som den är i r(0, 4), så blir andra if-testet sant.

Okej men i andra if testet har vi även return r(a,b-1) som körs om a är sant. Så r(0,4) , r(0,3), r(0,2) , r(0,1) och r(0,0) uppfyller andra if satsen ?

Det stämmer att r(0, 4), r(0, 3), r(0, 2) och r(0,1) skulle gå andra if-satsen att bli sann, men a och b har bara ett värde i taget. När vi anropar r(0, 4) så är a = 0 och b = 4.

Ja exakt. Samma sak med r(0,3) osv. Nu måste vi jobba med r(4,1) och se till att den uppfyller första if satsen eller på samma sätt som vi gjorde med r(2,4)?

Laguna Online 30305
Postad: 25 okt 09:28

r(4, 1) uppfyller inte första if-satsen och vi kan inte se till att den gör det. Det som körs är det som står sist, så ta reda på vad det blir.

destiny99 7842
Postad: 25 okt 09:39 Redigerad: 25 okt 10:40
Laguna skrev:

r(4, 1) uppfyller inte första if-satsen och vi kan inte se till att den gör det. Det som körs är det som står sist, så ta reda på vad det blir.

Menar du r(0,0)? om vi använder r(4,1) får vi r(2,1)+r(4,-2). 

Laguna Online 30305
Postad: 25 okt 10:40

r blir anropad med a = 4 och b = 1. Vad händer då i funktionen? Berätta, rad för rad.

destiny99 7842
Postad: 25 okt 10:42 Redigerad: 25 okt 10:45
Laguna skrev:

r blir anropad med a = 4 och b = 1. Vad händer då i funktionen? Berätta, rad för rad.

då ser vi att 1 är inte mindre än eller lika med 0 vid första if satsen (villkoret uppfylls ej) så den går vidare till andra if satsen där den kontrollerar om 4<=0 vilket den inte är pga ej uppfylld villkor där heller,  så den räknar return(a-2,b)+r(a,b-3) med insatta värden på a=4 och b=1. Vi får return (2,1)+r(4,-2)

Laguna Online 30305
Postad: 25 okt 10:44

Det stämmer. Så vad blir det för nya anrop till r, med insatta värden?

destiny99 7842
Postad: 25 okt 10:47
Laguna skrev:

Det stämmer. Så vad blir det för nya anrop till r, med insatta värden?

r(2,1)+r(4,-2)

Laguna Online 30305
Postad: 25 okt 13:20

Så nu får du ta reda på vad r(2, 1) blir.

destiny99 7842
Postad: 25 okt 13:32
Laguna skrev:

Så nu får du ta reda på vad r(2, 1) blir.

Jo det blir ju bara r(0,1)+r(2,-2)

Laguna Online 30305
Postad: 25 okt 14:34

Ja, och vad blir det?

destiny99 7842
Postad: 25 okt 14:51
Laguna skrev:

Ja, och vad blir det?

Vi måste hitta r(0,1) ? Vi vet inte vad r(0,1) +r(-2,2) eftersom vi vet inte vad r(0,1) respektive r(-2,2) är .

destiny99 7842
Postad: 27 okt 12:35
Laguna skrev:

Ja, och vad blir det?

Är det möjligt att lösa detta på det sättet?

Svara
Close