# Dynamische Programmierung und Rekursion



## districon (26. Nov 2021)

Es geht um eine Golomb Folge (https://de.wikipedia.org/wiki/Golomb-Folge). Ich habe diese schon rekursiv und mittels Memoization implementiert. Nun soll ich die auch nocht mit DP implementieren. Nur dass der Code eben auch noch endrekursiv sein soll.

```
public static int DP(int n, int[] g) {
        g[1] = 1;
        for (int i = 2; i <= n; i++) {
            
        }
        return g[n];
    }
```
Die letzte Zahl der Folge wird zurückgegeben. Meine Frage ist nun, wie soll das genau mit der Rekursion ablaufen?


----------



## mrBrown (26. Nov 2021)

Woran scheitet es denn genau? Der Wikipedia-Link von dir liefert doch eine schöne rekursive Formel dafür, die müsstest du nur noch in deinem Code unterbringen


----------



## districon (26. Nov 2021)

mrBrown hat gesagt.:


> Woran scheitet es denn genau? Der Wikipedia-Link von dir liefert doch eine schöne rekursive Formel dafür, die müsstest du nur noch in deinem Code unterbringen


Also n ist immer 1 in der EIngabe. Ich will pro rekursivem Aufruf eine Stelle g[n] berechnen . Ich weiß nur nicht wie das gehen soll.

```
public static int DP(int n, int[] g) {
      
        g[1] = 1;
            if (n == g.length - 1) {
                return g[n];
            }
            
            g[n] = ; // soll nicht rekursiv sein

        return DP(n + 1, g);
    }
```


----------



## districon (27. Nov 2021)

Habe das Problem selbst gelöst


----------

