Rekursion

---

Motivation

Die Fibonacci-Folge $$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,144,\dots$$

• $$ F_0 = 0, F_1 = 1 $$

• $$ F_n = F_{n-1} + F_{n-2} $$

---

---

$$F_4?$$

$$ F_0 = 0, F_1 = 1 $$

$$ F_n = F_{n-1} + F_{n-2} $$

$$ F_4 \rightarrow F_3, F_2 \rightarrow F_2, F_1 \rightarrow F_1, F_0$$

$$ F_2 = F_1 + F_0 = 1 + 0 = 1 $$

$$ F_3 = F_2 + F_1 = 1 + 1 = 2 $$

$$ F_4 = F_3 + F_2 = 2 + 1 = 3 $$

---

Code

public static long fibonacci(int n) {
    if (n < 0)
        throw new IllegalArgumentException(
                "Can only compute for positive numbers. Given: " + n);
    if (n < 2)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

fibonacci(7);

---

Call Stack

Methoden sind am Stack bis sie verlassen werden

static void preparePancakes() {
    makeDough();
    heatPan();
    putDoughInPan();
}

static void makeDough() {
    addIngredients();
    stir();
}

static void stir() { ... }

---

public static long fibonacci(int n) {
    if (n < 0)
        throw new IllegalArgumentException(
                "Can only compute for positive numbers. Given: " + n);
    if (n < 2)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

fibonacci(7);

---

StackOverflow

static void recursive() {
    recursive();
}

Exception in thread "main" java.lang.StackOverflowError
	at recursion.StackDemo.recursive(StackDemo.java:10)
	at recursion.StackDemo.recursive(StackDemo.java:10)
	at recursion.StackDemo.recursive(StackDemo.java:10)
	at recursion.StackDemo.recursive(StackDemo.java:10)
	at recursion.StackDemo.recursive(StackDemo.java:10)

---

Faktorielle

$$ n! = n \cdot (n-1) \cdot (n-2) \cdot \dots 1$$

$$ 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24 $$

static long factorial(int n) {
    if (n < 0)
        throw new IllegalArgumentException(
                "Can only compute for positive numbers. Given: " + n);
    if (n < 2)
        return 1;
    return n * factorial(n-1);
}

long result = 1;
for (int i = n; i > 0; i--)
    result *= i;
return result;

---

Best practice

• anwenden, wenn natürliche Lösung
• Performance mies
• Umwandlung in nicht-rekursive Lösung?

---

Fibonacci iterativ

public static long fibonacci(int n) {
    if (n < 0)
        throw new IllegalArgumentException(
                "Can only compute for positive numbers. Given: " + n);
    if (n < 2)
        return n;
    long parent = 1;
    long grandparent = 0;
    long curr = -1;
    for (int i = 2; i <= n; i++) {
        curr = parent + grandparent;
        grandparent = parent;
        parent = curr;
    }
    return curr;
}

---

Fibonacci mathematisch

$$ F_n = F_{n-1} + F_{n-2} $$

$$ x^n = x^{n-1} + x^{n-2} | : x^{n-2} $$

$$ x^2 = x + 1 $$

$$ x_1 = \phi = \frac{1 + \sqrt{5}}{2}, x_2 = \psi = \frac{1 - \sqrt{5}}{2} $$

$$ \Rightarrow \phi^n = \phi^{n-1} + \phi^{n-2}, \psi^n = \psi^{n-1} + \psi^{n-2} $$

---

$$ F_n = a\phi^n + b\psi^n $$

$$ F_0 = 0 \implies 0 = a + b $$

$$ F_1 = 1 \implies 1 = a\phi + b\psi $$

$$ \Rightarrow a = \frac{1}{\sqrt{5}}, b= -\frac{1}{\sqrt{5}}$$

$$ F_n = \frac{\phi^n-\psi^n}{\sqrt{5}} $$