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
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)?
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)?
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)?
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)
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?
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.
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:
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)?
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.
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
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.
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 ?
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).
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.
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)?
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.
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).
r blir anropad med a = 4 och b = 1. Vad händer då i funktionen? Berätta, rad för rad.
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)
Det stämmer. Så vad blir det för nya anrop till r, med insatta värden?
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)
Så nu får du ta reda på vad r(2, 1) blir.
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)
Ja, och vad blir det?
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 .
Laguna skrev:Ja, och vad blir det?
Är det möjligt att lösa detta på det sättet?
