Delkapittel 1.5 – Rekursjon

Oppgave 2

  public static int euklid(int a, int b)
  {
    System.out.println("euklid(" + a + "," + b + ") starter!");
    if (b == 0)
    {
      System.out.println("euklid(" + a + "," + b + ") er ferdig!");
      return a;
    }
    int r = a % b;            // r er resten
    int k = euklid(b,r);       // rekursivt kall
    System.out.println("euklid(" + a + "," + b + ") er ferdig!");
    return k;
  }

Oppgave 3

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610

Oppgave 4

Hvis flg. metode kjøres med en parameterverdi på 50, vil de ønskede Fibonacci-tallene bli skrevet ut:

  public static long fibonacci(int n)
  {
    System.out.println(0);  // Fibonacci-tall nr. 0

    long a = 0, b = 1, c = 0;

    for (int i = 0; i < n; i++)
    {
      a = b; b = c; c = a + b;

      System.out.println(c);
    }
    return c;
  }

Oppgave 5

Anta først at n er et oddetall, dvs. n = 2k + 1. Da vil

s_n = fib(0) + fib(1) + . . . . + fib(2k+1).

Legger vi sammen to og to tall (husk definisjonen av et Fibonacci-tall) får vi at

s_n = fib(2) + fib(4) + . . . . + fib(2k+2).

Men vi kan også legge sammen fib(1) og fib(2), fib(3) og fib(4), osv. Dermed

s_n = fib(0) + fib(3) + fib(5) . . . . + fib(2k+1) + fib(2k+1).

Hvis vi så adderere disse to rekkene får vi:

2s_n = s_n - fib(1) + fib(2k+1) + fib(2k+2).

Det gir at

s_n = fib(2k+3) - 1.

Vi kan argumentere på samme måte for tilfellet n er et partall. Konklusjonen blir dermed:

s_n = fib(n + 2) - 1.

Eksempel: s₁₀ = 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143. Videre er fib(10 + 2) - 1 = fib(12) - 1 = 144 - 1 = 143. Vi ser at formelen stemmer i dette eksempelet.

Oppgave 6

Rekursjonstreet for fib(5) har 15 noder. Rekursjonstreet for fib(6) vil få 25 noder.

Oppgave 7

Det kan vises at rekursjonstreet for fib(n) vil få 2*fib(n + 1) - 1 noder. Rekursjonstreet for fib(50) vil dermed inneholde 2*fib(51) - 1 noder. Vi vet at fib(51) = 20365011074. Dermed får treet 2*20365011074 - 1 = 40730022147 noder. Det betyr at hvis vi ønsker å finne Fibonacci-tall nr. 50, dvs. fib(50), ved hjelp av den rekursive fib-metoden, vil metoden bli kalt tilsammen 40730022147 ganger. Med andre ord er dette en helt håpløs og forferdelig metode for dette problemet. Den er vanvittig ineffektiv.

Oppgave 8

Det må opprettes en statisk int-variabel med navn antall i den klassen som flg. metode legges:

  public static int fib(int n)         // det n-te Fibonacci-tallet
  {
    antall++;     // antall må være en statisk variabel i klassen
    if (n <= 1) return n;              // fib(0) = 0, fib(1) = 1
    else return fib(n-1) + fib(n-2);   // summen av de to foregående
  }

Metoden kan kjøres slik:

  antall = 0;
  fib(10);
  System.out.println(antall);

  // Utskrift: 177