如何仅使用递归来查找字符串的所有置换而没有循环和数组？

Question

对于一个类项目，我们被要求使用递归找到字符串的所有排列，建议我们也使用长度，子字符串和charAt。循环和数组是禁止的。我在这里搜索了答案，但是我只找到了使用循环，数组或两者兼有的解决方案。目前，我只能使用循环来完成此操作，我想不出任何其他方式。这就是我想出的。

function permutations(string,choice){

    if (choice.length == 0) {
        print(string);
    }

    for (var i = 0; i < choice.length; i++)
    {
        var newString = string + choice.charAt(i);

        var newChoice = choice.substring(0, i) +
                        choice.substring(i + 1);


        permutations(newString, newChoice);
    }
};

我想知道递归如何替代“排列”当前使用的for循环。

输入和输出示例：

permutations（“”，“ ABC）将返回：美国广播公司ACB商业咨询委员会BCA出租车CBA

permutations（“”，“ ABCD”）将返回：

ABCDABDCACBD交流数据库公元前ADCBBACDBADC计算机辅助设计BCDA数模转换器BDCA中央商务区计算机辅助设计中央银行哥伦比亚广播公司CDABCDBADABC数模转换器DBACDBCADCABDCBA

Answer 1

您可以将循环转换为“递归”函数，在该函数中，每次迭代都会增加索引。这会消耗更多的资源并且难以理解，因此应仅用于学习目的。

function recurse(i, string, choice) {
  if (i >= choice.length) return;
  var newString = string + choice.charAt(i);
  var newChoice = choice.substring(0, i) + choice.substring(i + 1);
  permutations(newString, newChoice);
  recurse(i + 1, string, choice);
}

function permutations(string, choice) {
  if (choice.length == 0) console.log(string);
  recurse(0, string, choice);
};

permutations("", "abc");