Hej,

Skulle vilja veta lite mer om rekursion och vad det innebär.


1) Vad är en rekursiv metod/funktion?
2) Hur skriver man en metod som löser ett problem, t.ex. att skriva ut en textsträng baklänges med hjälp av en rekursiv metod. Förklara också gärna hur denna fungerar.
3) Exempel på när rekursiva metoder är lämpliga att använda.


Mvh
Teo

(1) En metod som anropar sig själv.

(2) Att skriva en text baklänges är inte ett typiskt exempel på när rekursion bör användas.
(se punkt 3 nedan)
Det är egentligen inte att beräkna fakulteten heller, eftersom den lätt kan beräknas utan rekursion, men av någon anledning brukar en fakultet ofta användas som exempel, kanske för att det brukar anses som ett litet pedagogiskt exempel som är enkelt att förstå.
Här har jag i alla fall ett sådant fakultets-exempel:

long fakulteten(int heltal) {

if(heltal < 0)
{
throw new IllegalArgumentException("Fakulteten är odefinierad för negativa tal");
}

/*
if(heltal > 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(heltal > 1)
{
// på raden nedan görs det rekursiva anropet
return heltal * fakulteten(heltal-1);
// för varje anrop kommer heltalet att minska med ett
}
else
{
// när heltalet i parametern har minskat till ett så avbryts rekursionen
// och en etta returneras istället
return 1;
}

}

För den som inte vet vad en fakultet är så är här är ett exempel:
fakulteten(6) = 6 * 5 * 4 * 3 * 2 * 1 = 720
(den kan förstås enkelt beräknas med en loop utan rekursion)


(3) Rekursiva metoder är oumbärliga när man hamnar i en situation där alternativet skulle vara ett oändligt antal nästlade loopar inuti varandra. Exempelvis om man på en webbsida för ett diskussionsforum vill visa alla svar på ett visst inlägg indenterat under det inlägget, och för varje nytt svar så vill man visa alla nya svar under detta o.s.v.

/ Tomas

<b>1) Vad är en rekursiv metod/funktion?</b>

Här finns en tråd med information om rekursion: [Rekursion]

Tack Per - det var jag som startade den. ;)

Kan man lösa ytterligare problem rekursivt? Exempelvis "floodfill". Hur gör man då?


Mvh
Teodor

<b>Tack Per - det var jag som startade den. ;)</b>

Låt mig omformulera mig...
Här är ett exempel på rekursion: [Rekursion]
Förstår du nu?

<b>Kan man lösa ytterligare problem rekursivt? Exempelvis "floodfill". Hur gör man då?</b>

<code>floodfill(x, y, color)
{
if(pixel(x, y).color == color)
return;

pixel (x, y).color = color;

floodfill(x+1, y, color);
floodfill(x-1, y, color);
floodfill(x, y+1, color);
floodfill(x, y-1, color);
}</code>

Man skall dock påpeka att rekursion kan påverka prestandan mycket negativt, speciellt om man rekurserar ner många nivåer.
En lösning som är iterativ istället för rekursiv är oftast MYCKET snabbare (t.ex. floodfill ovan).

Men ibland blir det mycket enklare och tydligare kod med rekursion (t.ex. traversering av träd), och då är det ett bra val.

/Andreas

Per - Nu förstår jag. :-)

Vågar man be om en förklaring på hur floodfill-koden fungerar?

Principen:
För att fylla utgår man från en punkt (x, y).
Man färgar denna.
Sedan gör man samma sak med utgång från i tur och ordning punkten till höger, punkten till vänster, punkten nedanför och punkten ovanför.

Men om man når en begränsning, en punkt som redan har den önskade färgen, sker inget rekursivt anrop.


Det kanske inte är riktigt så som floodfill brukar fungera. Mer korrekt är nog följande beteende:
<code>floodfill(x, y, color)
{
do_floodfill(x, y, color, pixel(x, y).color);
}

do_floodfill(x, y, color, old_color)
{
if(pixel(x, y).color != old_color)
return;

pixel (x, y).color = color;

floodfill(x+1, y, color);
floodfill(x-1, y, color);
floodfill(x, y+1, color);
floodfill(x, y-1, color);
}</code>

Jag brukar använda rekursion när jag tar mig igenom en hierarkisk struktur (t.ex. ett filträd).