Suma liczb za pomocą rekurencji java

Question

Powiedzmy, że n = 4. Z rekursji chcę wrócić:

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

Zasadniczo chcę wziąć numer n i łącząc numery 1,2,3 i 4 stworzyć wszystkie możliwe wariacje, gdy liczba sum == n.

To był mój pierwszy pomysł, ale daje mi

Wyjątek w wątku "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

Głównym problemem jest to, że zawsze, gdy recursing sum != n. Gdy suma dostaje większe niż n, nigdy nie przestać, stąd StackOverflowError Oznacza to musimy dodać czek i zakończyć, gdy suma robi się coraz większy:

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); 
    } 
} 

Jako marginesie, w Twoich 2 ostatnich połączeń, napisałeś 1 i 2 zamiast 3 i 4, ale to był prawdopodobnie tylko literówka.

Wyjście z wywołaniem test_2("", 0, 4):

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

---

Ale należy pamiętać, że aktualny kod nie jest bardzo dynamiczny: to nie będzie działać, jeśli były, aby dać wartości większe niż 4 dla n. Sugerowałbym trochę refaktoryzacji.