8 svar · 1 259 visningar · startad av pulse
Jag har lite problem med att förstå det här med rekursion. Vad händer tex i returnen i följande kodsnutt:
public class Test{
public static void main(String[] args){
int sum = 4;
System.out.println(fak(sum));
}
static int fak(int a){
if(a != 1)
return a * fak(a-1);
else
return a;
}
}
Om någon sitter på en bra länk som förklarar rekursion på ett lätt och bra sätt så får ni gärna skriva den här.
Det som händer vid returen i funktionen fak är att om variabeln a inte är 1 så anropar den sig själv med a - 1.
Med fyra i ditt exempel så kommer fak(4) att anropas. fak(4) kontrollerar om 4 är 1. Det är det inte, så den anropar fak(4-1), dvs fak(3). fak(3) kollar om 3 är 1, vilket det inte är och anropar fak(3-1). fak(2) kollar om 2 är 1, och anropar fak(2-1) som kollar om 1 är 1 vilket det är och den returnerar därför 1 tillbaka till fak(2) som tar returvärdet och multiplicerar med sitt värde (2) och returnar alltså 2*1 till fak(3) som tar det och multiplicerar med sitt värde och returnerar hela härligheten (3*2*1) till fak(4) som returnerar 4*3*2*1 till den ursprunlige anroparen, et voilà, du har ditt svar!
Grundprincipen för rekursion kan man säga är:
En funktion som anropar sig själv och som (helst) har någon form av villkor så den vid något tillfälle slutar att anropa sig själv.
En rekursiv funktion är egentligen en form av loop.
Samma funktion kan ju skrivas:
static int fak(int a)
{
int sum = 1;
for (; a; a--)
{
sum *= a;
}
return sum;
}
Jag tror inte att du har testat den koden... Java kräver att andra argumentet i for ska vara av typen boolean, tills killnad från t ex C. Därför måste man sätta ett villkor på a, snarare än att bara stoppa dit a.
static int fak(int a)
{
int sum = 1;
for (; [b]a>0[/b]; a--)
{
sum *= a;
}
return sum;
}
Re: Rekursion
pulse skrev:
Jag har lite problem med att förstå det här med rekursion. Vad händer tex i returnen i följande kodsnutt:
public class Test{ public static void main(String[] args){ int sum = 4; System.out.println(fak(sum)); } static int fak(int a){ if(a != 1) return a * fak(a-1); else return a; } }Om någon sitter på en bra länk som förklarar rekursion på ett lätt och bra sätt så får ni gärna skriva den här.
Någon har sagt "In order to understand recursion, one must first understand recursion" vilket är ganska talande ;).
Ett rekursivt anrop är när en funktions resultat är baserat på ytterligare ett anrop till samma funktion, genom att ha ett stoppvilkor när denna rekursion skall avbrytas så förhindrar man en evighetsloop (fak() returnerar resultat baserat på fak() som returnerar resultat baserat på fak() som returnerar resultat baserat på fak() ... i all evighet ...)
Rent tekniskt så fungerar det (oftast) så att delresultaten från varje anrop läggs på stacken, innan exekveringen går in i nästa funktionsanrop, när stoppvilkoret nås så hämtas de tidigare delresultaten upp från stacken.
Jag brukar tänka mig typ ett torn byggt av klossar, varje nytt rekursivt anrop är en ny kloss och när stoppvilkoret nåtts så rasar alla klossar ned till det första anropet.
I ditt fall så kommer det ju bli så här:
fak(4) =
4 * fak(3) =
4 * (3 * fak(2)) =
4 * (3 * (2 * fak(1))) =
[i]< stoppvilkor a = 1 uppnått >[/i] =
4 * (3 * (2 * 1)) =
4 * 6 =
[b]24[/b].
Jag får inte till någon vettigare förklaring över rekursion än det, så det är bättre att hänvisa dig till ett par bra länkar där de är mer pedagogiska än vad jag klarar av :):
På den här sajten hittar du massor med information om rekursion: http://encyclopedia.lockergnome.com/s/b/Recursion
Här hittar du en förklaring baserad just på ditt fakultetsexempel ovan: http://www.freenetpages.co.uk/hp/alan.gauld/tutrecur.htm
nitro2k01 skrev:
Jag tror inte att du har testat den koden...
Du har alldeles rätt. Jag kan inte Java, bara C. Det enda program jag skrivit i Java är ett som skriver ut talen 4-12, faktiskt huvudsakligen med just rekursion :-)
Det programmet testade jag så det fungerade eftersom det var nån person som ville ha hjälp med sin skoluppgift, och då vore det ju trist om det inte funkade, eller hur?
"Skriv ett program som skriver ut talen 4 till 12 genom att använda en for-loop"
http://www.webforum.nu/showthread.php?s=&postid=773778#post773778
Re: Rekursion
pulse skrev:
Jag har lite problem med att förstå det här med rekursion. Vad händer tex i returnen i följande kodsnutt:
public class Test{ public static void main(String[] args){ int sum = 4; System.out.println(fak(sum)); } static int fak(int a){ if(a != 1) return a * fak(a-1); else return a; } }
När man implementerar en rekursiv funktion/metod bör man akta sig för att inte få en oändlig anropskedja till minnet tar slut.
I detta exempel så kommer det att inträffa om du anropar med ett tal som är mindre än 1.
När det gäller beräkning av fakulteten så ska fak(0) ge resultatet 1, medan fak(x) är odefinierat om x<0.
Din metod enligt ovan kommer däremot att förbruka minnet i datorn om man anropar den med sådana parametrar.
För att undvika oändliga anrop så kan man titta på dels det rekursiva anropet och dels på avbrottsvillkoret (d.v.s. vad är det som gör att rekursionen kommer att avrbytas) och försöka se till att villkoret förr eller senare kommer att uppfyllas så att rekursionen avbryts.
I det här exemplet ser man tydligt att värdet kommer att minska med ett för varje anrop d.v.s. det blir hela tiden mindre och mindre.... alltså borde villkoret för att avbryta rekursionen ha något att göra med att man kollar att det minskade värdet är en låg siffra. Dock är det vanskligt att, som implementationen ovan gör, ange en exakt siffra eftersom man i det första anropet kan ange en siffra som är lägre än det exakta villkoret. (t.ex. "if(a != 1)" är ett exakt villkor till skillnad från exempelvis "if(a <= 1)" )
För att åtgärda problemen som jag har försökt beskriva ovan, så kan du implementera fakulteten så här istället:
static long fak(int a) {
if(a < 0)
{
throw new IllegalArgumentException("Fakulteten är odefinierad för negativa tal");
}
/*
if(a > MAX) // prova med olika inparamtrar för att fastställa maxvärdet som metoden kommer att klara
{
throw new IllegalArgumentException("Datorn klarar inte att korrekt beräkna fakulteten för ett så stort tal");
}
*/
if(a > 1)
{
return a * fak(a-1);
}
else
{
return 1;
}
}
pulse skrev:
Om någon sitter på en bra länk som förklarar rekursion på ett lätt och bra sätt så får ni gärna skriva den här.
Jag har i och för sig inte läst denna sajt om rekursion:
http://personal.vsnl.com/erwin/recursion.htm
men den verkar ganska ambitiös och är kanske bra...
/ Tomas
Detta står i ordlistan på Delphi7:
recursion
A programming technique in which a subroutine calls itself. Use care to ensure that a recursion eventually exits. Otherwise, an infinite recursion will cause a stack fault.