这个 Java 程序使用迭代将自然数转换为集合论编码。请求 help/strategies 递归解决方案？

Question

我试图更好地理解 ZFC 集合论，特别是计算机程序如何将无穷大公理建模为 "construct" 自然数。我见过的用于构造自然数的典型符号是：“{”、“}”和“,”。

下面的代码有效，但我希望有一个纯递归的解决方案。给定一个自然数（这里使用 int）的一个，递归地将相应的字符串构建到它的集合论编码中，然后 returns 它。理想情况下，我希望它能够在不使用任何额外数据结构的情况下工作，例如当前正在使用的 String 数组。

如果运行时间很慢（指数级）也没关系。使用递归有时会使过程的表达更简单，更 condensed/elegant 并且更容易理解，我非常想看看这样的解决方案可能是什么样子，而不管性能如何。最后，我想更好地了解 math/numbers 的基础。我有很多问题，但认为这可能是一个很好的开始方式。谢谢！

// 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

所以递归听起来真的很难，但是一旦你记住了这个名字，它实际上有点简单。

递归需要做的事情：停止递归的基本情况，以及做你想做的事情的输出。

假设您想编写一个递归问题，它接受一个数字 x，并且 return 是一个特定的花括号模式：

0 ==（无）

1 == {}

2 == {{}}

3 == {{{}}}

...

因此，您的递归方法将采用一个整数。

现在，让我们看看方法输出。如果我们在 1 上调用递归方法，我们想要 return {}。简单。根据 java，我们将 returning 一个字符串。

太好了，现在我们知道了方法的 return 类型。

如果我们在2上调用递归方法，我们希望该方法首先输出{}，然后我们希望该方法再次执行，但是这次，我们在开始时放了一个卷曲，在开头放了一个卷曲AT结束。

这是很难解释的部分。将递归想象成一个循环。最终，我们希望递归终止。假设我们最初在 3 上调用该方法。我们希望 {{{}}} 被 returned。首先，我们的方法将 return {}，然后是 {{}}，然后是 {{{}}}。它总共运行了 3 次。

在递归调用中，必须比初始调用少调用一次。

好吧，现在你说，如果我们每次都减1，然后再次调用该方法，我们如何让它停止？

这就是所谓的基本情况。如果在 0 上调用该方法，我们不想 return 任何东西，因此我们想使用简单的 return 语句退出该方法。

把这个应用到你自己的问题上，你应该会很好。

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

这是一个让您入门的示例。 else后面的return语句叫做递归调用，上面讲过

Answer 2

我想出了下面的代码作为递归解决方案。它有效，但我想知道是否有简化它的方法，也许使用更少的方法？欢迎任何想法或评论。

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

打印：
0 = {}
1 = {{}}
2 = {{},{{}}}
3 = {{},{{}},{{},{{}}}}
4 = {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
5 = {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}}, {{},{{}}},{{},{{}},{{},{{}}}}}}

Answer 3

第二种辅助方法不是必需的。这是一个简化版本。

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

打印：
0 = {}
1 = {{}}
2 = {{},{{}}}
3 = {{},{{}},{{},{{}}}}
4 = {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
5 = {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}}, {{},{{}}},{{},{{}},{{},{{}}}}}}

这个 Java 程序使用迭代将自然数转换为集合论编码。请求 help/strategies 递归解决方案？

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

java

recursion

set-theory

number-theory

peano-numbers