public class SilniaDZ
{
  public static void main(String[] args)
  {
    final int N = 3;
    System.out.println(N + "! = " + silnia(N));
  }
  
  static long silnia(int n)
  {
    if (n == 0)
    {
      return 1;
    }
    else
    {
      return n*silnia(n-1); 
    }
  }
}

Ad. a

Analizujemy wywołanie silnia(3)

1. Przebieg z góry do dołu

• silnia₁(3) =
  return 3*silnia₂(2) =
• silnia₂(2) =
  return 2*silnia₃(1) =
• silnia₃(1) =
  return 1*silnia₄(0) =
• silnia₄(0) =
  return 1

2. Przebieg z dołu do góry

• silnia₁(3) = 6
  return 3*silnia₂(2) = 3*2 = 6
• silnia₂(2) = 2
  return 2*silnia₃(1) = 2*1 = 2
• silnia₃(1) = 1
  return 1*silnia₄(0) = 1*1 = 1
• silnia₄(0) = 1
  return 1

Uwaga: Kolejne wywołania metody silnia zostały ponumerowane przy pomocy indeksów dolnych.

Graf wywołań rekurencyjnych

silnia1(3) --> silnia2(2) --> silnia3(1) --> silnia4(0)

Odp:

Program wypisze: 3! = 6

Ad. b

f(n) - złożoność obliczeniowa wywołania silnia(n), gdzie n ∈ N ∪ {0}

Złożoność obliczeniową mierzymy zazwyczaj liczbą instrukcji przypisań i porównań wykonanych w trakcie działania programu.

Wyznaczamy równanie rekurencyjne na podstawie analizy wywołań:

• silnia(0)

  f(0) = 1 + 1 = 2

• silnia(1)

  f(1) = 1 + 1 + f(0) = 2 + f(0)

• silnia(2)

  f(2) = 1 + 1 + f(1) = 2 + f(1)

...

• silnia(n)

  f(n) = 1 + 1 + f(n-1) = 2 + f(n-1)

Uzasadnienie wyprowadzenia

Uzasadnienie podamy na przykładzie wywołania silnia(0) i silnia(1)

• silnia(0)    - wywołujemy metodę silnia z parametrem aktualnym 0

  f(0) =       - wyznaczamy złożoność obliczeniową wywołania silnia(0)

       1       - w momencie wywołania metody silnia parametr formalny n przyjmuje wartość
                 parametru aktualnego, czyli 0, a zatem mamy niejawne podstawienie, które
       +         liczymy za 1

       1       - wchodzimy do ciała metody silnia, napotykamy instrukcję if..else, sprawdzamy
                 warunek logiczny z nagłówka instrukcji, co liczymy za 1, warunek jest prawdziwy,
                 bo 0 = 0, a zatem wchodzimy do pierwszego ciała instrukcji i zwracamy wartość 1

• silnia(1)    - wywołujemy metodę silnia z parametrem aktualnym 1

  f(1) =       - wyznaczamy złożoność obliczeniową wywołania silnia(1)

       1       - w momencie wywołania metody silnia parametr formalny n przyjmuje wartość
                 parametru aktualnego, czyli 1, a zatem mamy niejawne podstawienie, które
       +         liczymy za 1

       1       - wchodzimy do ciała metody silnia, napotykamy instrukcję if..else, sprawdzamy
                 warunek logiczny z nagłówka instrukcji, co liczymy za 1, warunek jest fałszywy,
       +         bo 1 ≠ 0, a zatem pomijamy pierwsze ciało i wchodzimy do drugiego ciała instrukcji

       f(0)    - w drugim ciele instrukcji if..else zwracamy wartość wyrażenie 1*silnia(0) w którym
                 pojawia się wywołanie rekurencyjne silnia(0) o złożoności obliczeniowej równej f(0)

Równanie rekurencyjne

       2          ; n = 0
f(n) =
       2 + f(n-1) ; n > 0

Rozwiązanie równania

Sposób I

f(n) = 2 + f(n-1) = 2 + 2 + f(n-2) = 2 + 2 + 2 + f(n-3) = *

Z: n - k = 0 => k = n

* = 2 + 2 + 2 + ... + 2 + f(n-k) = 2k + f(n-k) = 2n + f(0) = 2n + 2

Sposób II

f(0) = 2
f(1) = 2 + f(0) = 2 + 2
f(2) = 2 + f(1) = 2 + 2 + 2
f(3) = 2 + f(2) = 2 + 2 + 2 + 2
...
f(n) = 2 + f(n-1) = 2n + 2

Dowód indukcyjny

1. f(0) = 2
   f(0) = 2*0 + 2 = 2

2. Z: f(n) = 2n + 2
   T: f(n+1) = 2(n+1) + 2

Dowód 1

   f(n+1) = 2 + f(n) = 2 + 2n + 2 = 2n + 2 + 2 = 2(n+1) + 2

Dowód 2

   f(n+1) = 2(n+1) + 2 = 2n + 2 + 2 = 2 + 2n + 2 = 2 + f(n) prawda

Dowód funkcyjny

1. f(0) = 2
   f(0) = 2*0 + 2 = 2
   
2. Wykażemy, że rozwiązanie f(n) = 2n + 2 spełnia równanie funkcyjne f(n) = 2 + f(n-1)

   2 + f(n-1) = 2 + 2(n-1) + 2 = 2 + 2n - 2 + 2 = 2n + 2 = f(n)

Odp:

f(n) = 2n + 2 ∈ Θ(n) "f jest dokładnie rzędu n"

Ad. c

g(n) - złożoność pamięciowa wywołania silnia(n), gdzie n ∈ N ∪ {0}

Złożoność pamięciową mierzymy zazwyczaj liczbą deklaracji komórek pamięci wykonanych w trakcie działania programu.

Wyznaczamy równanie rekurencyjne na podstawie analizy wywołań:

• silnia(0)

  g(0) = 1

• silnia(1)

  g(1) = 1 + g(0) = 1 + g(0)

• silnia(2)

  g(2) = 1 + g(1) = 1 + g(1)

...

• silnia(n)

  g(n) = 1 + g(n-1) = 1 + g(n-1)

Uzasadnienie wyprowadzenia

Uzasadnienie podamy na przykładzie wywołania silnia(0) i silnia(1)

• silnia(0)    - wywołujemy metodę silnia z parametrem aktualnym 0

  g(0) =       - wyznaczamy złożoność pamięciową wywołania silnia(0)

       1       - w momencie wywołania metody silnia parametr formalny n przyjmuje wartość
                 parametru aktualnego, czyli 0, a zatem mamy deklarację zmiennej n, którą
                 liczymy za 1

                 wchodzimy do ciała metody silnia, napotykamy instrukcję if..else, sprawdzamy
                 warunek logiczny z nagłówka instrukcji, warunek jest prawdziwy, bo 0 = 0, 
                 a zatem wchodzimy do pierwszego ciała instrukcji i zwracamy wartość 1

• silnia(1)    - wywołujemy metodę silnia z parametrem aktualnym 1

  g(1) =       - wyznaczamy złożoność pamięciową wywołania silnia(1)

       1       - w momencie wywołania metody silnia parametr formalny n przyjmuje wartość
                 parametru aktualnego, czyli 1, a zatem mamy deklarację zmiennej n, którą
       +         liczymy za 1

       g(0)    - wchodzimy do ciała metody silnia, napotykamy instrukcję if..else, sprawdzamy
                 warunek logiczny z nagłówka instrukcji, warunek jest fałszywy, bo 1 ≠ 0,
                 a zatem pomijamy pierwsze ciało i wchodzimy do drugiego ciała instrukcji

                 w drugim ciele instrukcji if..else zwracamy wartość wyrażenie 1*silnia(0) w którym
                 pojawia się wywołanie rekurencyjne silnia(0) o złożoności pamięciowej równej g(0)

Równanie rekurencyjne

       1          ; n = 0
g(n) =
       1 + g(n-1) ; n > 0

Rozwiązanie równania

Sposób I

g(n) = 1 + g(n-1) = 1 + 1 + g(n-2) = 1 + 1 + 1 + g(n-3) = *

Z: n - k = 0 => k = n

* = 1 + 1 + 1 + ... + 1 + g(n-k) = k + g(n-k) = n + g(0) = n + 1

Sposób II

g(0) = 1
g(1) = 1 + g(0) = 1 + 1
g(2) = 1 + g(1) = 1 + 1 + 1
g(3) = 1 + g(2) = 1 + 1 + 1 + 1
...
g(n) = 1 + g(n-1) = n + 1

Odp:

g(n) = n + 1 ∈ Θ(n) "g jest dokładnie rzędu n"