Рекурсия в Java - Теория разделов

Question

Я пытался понять следующую рекурсию, код не мой, это код для вычисления теории разбиения n чисел, но рекурсия это меня запутывает. Кто-нибудь может объяснить мне, как это работает, чтобы я наконец смог понять это. Благодарю.

package practicingjava;

import java.util.Scanner;

/**
 * @author JVASQUEZ
 */
public class PracticingJava {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        partition(n, n, "");
    }

    public static void partition(int max, int n, String prefix) {
        if (n == 0) {
            System.out.println(prefix);
        }
        for (int i = Math.min(max, n); i >= 1; i--) {
            partition(i, n - i, prefix + " " + i);
        }
    }
}

Answer 1

Идея этой рекурсии состоит в том, что все возможные разбиения натурального числа N могут быть составлены из числа Ni, объединенного с каждым разбиением i с использованием натуральных чисел, меньших i, для каждого 1 ≤ i ≤ n ∈ ℕ и определяющих множество разделов, равное 0 быть пустым.

Если все разбиения n из чисел меньше j равны {n,j}, то все разбиения n

n,   {0, n)
n-1, {1, n-1}
n-2, {2, n-2}
n-3, {3, n-3}
...
1,   {n-1, 1}

где n-1, {1, n-1} все разделы образованы {1, n-1} с добавленным префиксом n-1 для каждого.

Например, партиции 5 (максимальное значение при разложении для ясности опущено)

{5} = 

i  n-i

5, {0} -> 5

4, {1} -> 4, (1, {0}) -> 4, 1

3, {2} -> 3, (2, {0}) -> 3, 2
          3, (1, {1}) -> 3, (1, 1, {0}) -> 3, 1, 1

2, {3} -> 
          2, (2, {1}) ->          
            2, 2, (1, {0}) -> 2, 2, 1
          2, (1, {2}) ->  
            2, 1, 1, (1, {0}) ->  2, 1, 1, 1

1, {4} ->  
        1, (1, {3}) ->
            1, 1, (1, {2}) ->
                1, 1, 1, (1, {1}) ->
                    1, 1, 1, 1, {0} -> 1, 1, 1, 1

Answer 2

Если вы вызываете его с помощью ввода 5, он напечатает

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

в основном это разбивка числа на меньшие при вводе 5, вызывает рекурсивную функцию с 4 и 1 1 не может быть разбита, но продолжается с 4

как только этот стек завершен, он делает... новые числа 3 и 2

и это продолжается

Answer 3

Для более основного учебника по рекурсии в Java: http://www.javatpoint.com/recursion-in-java

Но в этом случае раздел вызывается один раз, а затем продолжает вызывать себя, пока n не достигнет нуля. Это то, что делал предыдущий оператор if. Если бы этого не было, заявление продолжалось бы до бесконечности. Затем цикл извлекает переменные из аргументов и, следовательно, из ранее запущенного метода. Таким образом, проблема разбивается на более мелкие части.