Summe der Zahlen mit Rekursion Java

Question

Sagen wir n = 4. Mit Rekursion möchte ich zurück:

1 1 1 1 
1 1 2 
1 3 
2 1 1 
2 2 
3 1 
4 

Grundsätzlich möchte ich Nummer nehmen n und mit durch Zahlen 1,2,3 kombiniert und 4 erzeugen alle möglichen Variationen, wenn die Anzahl der sum == n.

Dies war meine erste Idee, aber es gibt mir

Exception in thread "main" java.lang.StackOverflowError

public static void test_2(String path, int sum, int n){ 
    if(sum == n){ 
     System.out.println(path); 
    } else { 
     test_2(path+"1 ", sum + 1, n); 
     test_2(path+"2 ", sum + 2, n); 
     test_2(path+"3 ", sum + 1, n); 
     test_2(path+"4 ", sum + 2, n); 
    } 
} 

Answer 1

Das Hauptproblem ist, dass Sie immer Rekursion, wenn sum != n. Wenn die Summe größer als n wird, stoppen Sie nie, daher die StackOverflowError Das bedeutet, wir brauchen einen Scheck hinzuzufügen und zu beenden, wenn die Summe größer wird:

public static void test_2(String path, int sum, int n) { 
    if (sum == n) { 
     System.out.println(path); 
    } else if (sum < n) { // <-- only recurse if the sum is less than the target 
     test_2(path+"1 ", sum + 1, n); 
     test_2(path+"2 ", sum + 2, n); 
     test_2(path+"3 ", sum + 3, n); 
     test_2(path+"4 ", sum + 4, n); 
    } 
} 

Als Randnotiz, in der zwei letzten Anrufe, Du hast 1 und 2 statt 3 und 4 geschrieben, aber das war wahrscheinlich nur ein Tippfehler.

Ausgabe von Aufruf test_2("", 0, 4):

1 1 1 1 
1 1 2 
1 2 1 
1 3 
2 1 1 
2 2 
3 1 
4 

---

Aber beachten Sie, dass Ihr aktueller Code nicht sehr dynamisch: es würde nicht funktionieren, wenn Sie Werte zu geben, sind größer als 4 für n. Ich würde vorschlagen, es ein wenig zu refaktorisieren.