Rekursion - også en lille gennemgang

Rekursion er når en metode kalder sig selv.

Rekursion? at starte en funktion fra sig selv.

Bruges til visse komplicerede udregninger, men mest almindeligt i dag, til at søge i biblioteker på computeren.

Et eksempel nakket fra Microsoft:

// Function to calculate factorials. If an invalid
// number is passed in (ie, one less than zero), -1
// is returned to signify an error. Otherwise, the
// number is converted to the nearest integer, and its
// factorial is returned.
function factorial(aNumber)  {
aNumber = Math.floor(aNumber);  // If the number is not an integer, round it down.
if (aNumber < 0)  {  // If the number is less than zero, reject it.
    return -1;
    }
      if (aNumber == 0)  {  // If the number is 0, its factorial is 1.
      return 1;
      }
        else return (aNumber * factorial(aNumber - 1));  // Otherwise, recurse until done.
}

Det var godt nok JavaScript, det ved jeg, men koden er jo nogenlunde den samme

public class Fac {
    public static void main(String[] args) {
        System.out.println(fac(4));
    }
    public static long fac(int v) {
        if(v > 1) {
            return v * fac(v - 1);
        } else {
            return 1;
        }
    }
}

Og det er Java !

du kan tage og kigge på den nye javabog vp om Rekursion
http://javabog.dk/VPJ/bog4.html

Rekursion er f.eks. god til at travesere træer.

F.eks. med et binært træ.

public void preOrder(Node n)
{
  System.out.println(n.getValue());
  preOrder(n.getLeftNode());
  preOrder(n.getRightNode());
}

public void postOrder(Node n)
{
  postOrder(n.getLeftNode());
  postOrder(n.getRightNode());
  System.out.println(n.getValue());
}

public void inOrder(Node n)
{
  inOrder(n.getLeftNode());
  System.out.println(n.getValue());
  inOrder(n.getRightNode());
}

Jeg glemte at teste om n er null.

public void preOrder(Node n)
{
  if(n != null)
  {
    System.out.println(n.getValue());
    preOrder(n.getLeftNode());
    preOrder(n.getRightNode());
  }
}

Ellers så vil rekursionen ikke stoppe igen (før der ikke er mere stack til rådighed).

Vil den ikke dø med en null pointer exception før det ?

Det kan jeg ikke lige gennemskue - muligvis ?

Kan man kalde en metode med null som parameter ?

Jeg har desværre ikke tid lige nu til at strikke en test sammen.

Til Arne,

Det lille og udemærket eks. du har lavet her - kan du ikke lige forklare mig hvad det er der sker - kan ikke helt forstå hvordan den kommer frem til resultatet??

sorry - den kører ikke så hurtigt mere...

public static long fac(int v) {
        if(v > 1) {
            return v * fac(v - 1);
        } else {
            return 1;
        }
    }

vi kalder fac(4)

4 > 1 så fac(4) = 4 * fac(3)

3 > 1 så fac(3) = 3 * fac(2)

2 > 1 så fac(2) = 2 * fac(1)

1 er ikke større end 1 så fac(1) = 1

og derfor er fac(4) = 4 * 3 * 2 * 1 = 24

hvad vi selvfølgelig godt vidste !

Det er ikke særligt effektivt at udregne fac rekursivt men det er
et klassisk eksempel på det alligevel.

søren>

Du kan sagtens kalde en metode med null, men når du nede i metoden forsøger at
kalde en ikke-statiske metode på det objekt der er null, så sker der
noget grimt.

ok - nu tror jeg jeg har fattet humlen i rekursion - havde lige glemt at den kaldte sig selv...Havde bare kørt den i igenem engang...4 > 1 så fac(4) = 4 * fac(3)
Dum kan man jo altid være :-)

Stadig synes jeg det er fornuftigt at teste for null

:-)

søren>

Ja - selvfølgelig. null pointer exception eller out of memory er da et fedt.

der er sikkert mange om rekursion her på eksperten. Her er en stillet af en nybegynder.
http://www.eksperten.dk/spm/201986
Hvis du vil videre med lidt hæftigere rekursion så tjek det her spm (og EJ svar)
http://www.eksperten.dk/spm/53401

mindreklog>

Tid at lukke spørgsmålet ?

PS: Jeg håber at det gik godt til eksamen.

Ja, det må du undskylde....Og tak for hjælpen - det gik ikke vildt godt, men jeg brugte faktisk dit eks. på rekursion i en af opgaverne...