Recursion in Java - Partition theory

Question

I have been trying to understand the next recursion, the code ain't mine, it is a code to calculate the partition theory of n numbers, but the recursion of it, it's making me confused. Can anybody explain me how does it work in order I can finally understand it. Thanks.

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

For a more basic primer on recursion in java : http://www.javatpoint.com/recursion-in-java

But in thie case, partition is called once and then continues to call itself until n reaches zero. That is what the previous if statement was doing. If that if statement wasn't there it would continue on infinitum. The loop then pulls variables from the arguments and therefore the previously run method. It breaks the problem down into smaller pieces that way.

Answer 2

The idea behind this recursion is that all possible partitions of a natural number N can be composed from a number N-i combined with each partition of i using natural numbers less than i, for each 1 ≤ i ≤ n ∈ ℕ and defining partitions set of 0 to be empty.

If all partitions of n from numbers less than j are {n,j} then all partitions of n are

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

where n-1, {1, n-1} are all partitions formed by {1, n-1} with added prefix n-1 to each.

For example, paritions of 5 (max value in decomposition is omitted for clarity)

{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 3

if you call it with input 5 it will print

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

its basically breaking the number down in smaller ones when you input 5, it calls recursive function with 4 and 1 1 cannot be broken down but it continues with 4

once that stack is complete it does i-- so new numbers are 3 and 2

and it continues