This Java program converts a natural number into a set-theoretic encoding using iteration. Request help/strategies for a recursive solution?

Question

I'm trying to get a better understanding of ZFC set theory, in particular how a computer program might model the axiom of infinity to "construct" natural numbers. The typical symbols I've seen used to construct the natural numbers are: "{", "}", and ",".

The code below works, but I'm hoping for a purely recursive solution. One that given a natural number (here using int), recursively builds up the corresponding string into its set-theoretic encoding and then returns it. Ideally, I hope for it to work without using any extra data structures like the String array currently being used.

It's ok if the runtime is slow (exponential). Using recursion sometimes makes the expression of the process simpler, more condensed/elegant and easier to understand, and I would very much like to see what such a solution for this might look like, regardless of performance. Ultimately, I'd like a better understanding of foundations of math/numbers. I have many questions but thought this might be a good way to begin. Thanks!

// Converts an natural number to its ZFC set notation: 
// 0 = {}, 1 = {0} = {{}}, 2 = {0,1} = {{},{{}}},  
// 3 = {0,1,2} = {{},{{}},{{},{{}}}} ...    

import java.util.Scanner;

public class IntToSetNotation {
    private static final String openBrace = "{";
    private static final String closeBrace = "}";
    private static final String seperator = ",";

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        System.out.println(getSetNotationFromInt(n));
    }

    private static String getSetNotationFromInt(int n) {
        String[] nums = new String[n+1];
        nums[0] = openBrace + closeBrace;
        for (int i = 1; i < nums.length; i++) {
            if(i == nums.length-1)
                nums[i] = openBrace + getPrevSets(i,nums) + closeBrace;
            else
                nums[i] = seperator + openBrace + getPrevSets(i,nums) + closeBrace;
        }
        return nums[n];
    }

    private static String getPrevSets(int n, String[] nums) {
        String s = "";
        for (int i = 0; i<n; i++)
            s += nums[i];
        return s;
    }
} 

Answer 1

The second helper method isn't necessary. Here is a shortened version.

public class IntToSetNotationRecursive {
    private static final String openBrace = "{";
    private static final String closeBrace = "}";
    private static final String separator = ",";

    public static void main(String[] args) {
        for (int i = 0; i < 6; i++) {
            System.out.println(i + " = " + getSetNotationFromInt(i));
        }
    }

    static String getSetNotationFromInt(int n){
        return helper1(n, n, "");
    }

    static String helper1(int n, int x, String s){
        if(x<=0)
            return openBrace + s + closeBrace;

        return helper1(n, x-1, helper1(x-1,x-1,"") + ((x != n ) ? separator : "") + s);
    }
}

Prints:
0 = {}
1 = {{}}
2 = {{},{{}}}
3 = {{},{{}},{{},{{}}}}
4 = {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
5 = {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}

Answer 2

So recursion sounds really difficult, but it's actually kind of simple once you get over the name.

Recursion needs to things: a base case to stop recursing, and an output to do what you want.

Say you want to write a recursive problem that takes in a number x, and returns a specific pattern of curly braces:

0 == (nothing)

1 == {}

2 == {{}}

3 == {{{}}}

...

So, your recursive method is going to take one integer.

Now, lets look at the method output. If we call the recursive method on 1, we want to return {}. Easy. In terms of java, we'll be returning a string.

Great, now we know the return type of the method.

If we call recursive method on 2, we want the method to first output {}, and then we want the method to execute AGAIN, but this time, we are putting a curly AT THE BEGINNING, and one curly AT THE END.

This is the part that is hard to explain. Imagine recursion as a loop. Eventually, we want the recursion to terminate. Say we call the method initially on 3. We want {{{}}} to be returned. First, our method will return {}, followed by {{}}, then {{{}}}. It runs a total of 3 times.

In the recursive call, you have to call it one less than the initial call.

Ok, now you say, if we are subtracting 1 each time and calling the method again, how do we get it to stop?

That's called the base case. If the method is called on 0, we don't want to return anything, thus we want to exit out of the method with a simple return statement.

Apply this to your own problem, and you should be good.

String exampleRecursiveMethod(int x){
 if(x==0)return "";
 else return exampleRecursiveMethod(x-1)
}

This is an example to get you started. The return statement after the else is called the recursive call, I talked about it above.

Answer 3

I came up with the below code as a recursive solution. It works, but I wonder if there is anyway to streamline it, perhaps to use less methods? Any thoughts or comments are welcome.

public class IntToSetNotationRecursive {
    private static final String openBrace = "{";
    private static final String closeBrace = "}";
    private static final String seperator = ",";

    public static void main(String[] args) {
        for (int i = 0; i < 6; i++) {
            System.out.println(i + " = " + getSetNotationFromInt(i));
        }
    }

    static String getSetNotationFromInt(int n){
        return helper1(n, n, "");
    }

    static String helper1(int n, int x, String s){
        if(x<=0)
            return openBrace + s + closeBrace;

        return helper1(n, x-1, helper2(x-1) + ((x != n ) ? seperator : "") + s);
    }

    static String helper2(int x){
        if(x<=0)return openBrace+closeBrace;
        else return helper1(x, x, "");
    }
}

Prints:
0 = {}
1 = {{}}
2 = {{},{{}}}
3 = {{},{{}},{{},{{}}}}
4 = {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
5 = {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}