-1 
import java.io.*;
class combination
{
    static int cntr =  0;
    public static void main(String args[]) throws IOException
    {
        combination call = new combination();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Enter a String : ");
        String n = br.readLine();
        call.comb("",n);
        System.out.println("Number of combinations are : "+cntr);
    }
    public void comb(String beg, String end) throws IOException
    {
        if (end.length()<=1)
        {
            cntr++;
            System.out.println(beg+end);
        }
        else
        {
            for (int i=0;i<end.length();i++)
            {
                String n = end.substring(0,i)+end.substring(i+1);
                comb(beg + end.charAt(i),n);
            }
        }
    }
}

上面的程序给出了特定字符串的组合。

我无法理解递归的调用流程。我想知道上面递归程序的调用流程。

任何人都可以解释这一点吗？

4

2 回答 2

1

您的程序执行所有排列，而不是所有组合。有n！（其中的 n 个阶乘）以及程序使 n! 来电。递归表示一堆方法调用。请记住，每个递归步骤对应于每个堆栈条目。每个堆栈条目都保留其局部变量。现在让我们逐步了解流程。例如，让 n="abc"。length=3 --> !n=1*2*3=6 递归调用。当 var end.length <= 1 时递归结束。这是一个基本情况（System.out.println）。在每个基本情况下，我们在递归树中返回 1 级。

所以流程是（通常称为递归树）：

步骤 1. 递归
  步骤 2 递归
    步骤 3 基本情况 --> 打印 abc
  在递归树上返回 1 级
  第4步
    第 5 步基本案例 --> 打印 acb
  在递归树上返回 1 级
在递归树上返回 1 级
步骤 6. 递归
  第 7 步递归
    步骤 8 基本案例 --> 打印 bac
  在递归树上返回 1 级
  步骤 9 递归
    第 10 步基本案例 --> 打印 bca
  在递归树上返回 1 级
在递归树上返回 1 级
步骤 11. 递归
  步骤 12 递归
    步骤 13 基础案例 --> 打印驾驶室
  在递归树上返回 1 级
  步骤 14 递归
    步骤 15 基本案例 --> 打印 cba
  在递归树上返回 1 级
在递归树上返回 1 级
结尾。

从这个流程中，您可以将“递归步骤”想象为推送操作，将“Go 1 level back”想象为堆栈上的弹出操作并通过流程/代码。

下面是对调用的详细分析，大家可以通过调试来理解或上一块parer。

        第 1 步：递归级别 1
          乞求 = ""
          结束=“ABC”
          cntr = 0
          我 = 0
          n="bc"

          第 2 步：递归级别 2
            乞求=“一个”
            结束=“公元前”
            cntr = 0
            我 = 0
            n = "c"

            第 3 步：递归级别 3
            乞求=“ab”
            end = "c", 这是一个基本情况 --> 打印 beg+end = abc
            cntr = 0
            我 = 0
          返回递归级别 2

          第 4 步：递归级别 2
          乞求=“一个”
          结束=“公元前”
          cntr = 1
          i = 1 打印 beg+end = acb
            cntr = 1
          返回递归级别 2
        返回递归级别 1

        第 6 步：递归级别 1
        乞求 = ""
        结束=“ABC”
        cntr = 1
        我 = 1
        n = "交流"

          第 7 步：递归级别 2
          乞求 = "b"
          结束=“交流”
          cntr = 2
          我 = 0
          n = "c"

            第 8 步：递归级别 3
            乞求=“巴”
            end = "c", 这是一个基本情况 --> 打印 beg+end = bac
            cntr = 2
            我 = 0
            n = "c"
          返回递归级别 2

          第 9 步：递归级别 2
          乞求 = "b"
          结束=“交流”
          cntr = 3
          我 = 1
          n = "一个"

            第 10 步：递归级别 3
            乞求=“公元前”
            end = "a", 这是一个基本情况 --> 打印 beg+end = bca
            cntr = 3
            我 = 1
            n = "c"
          返回递归级别 2
        返回递归级别 1

        第 11 步：递归级别 1
          乞求 = ""
          结束=“ABC”
          cntr = 4
          我 = 2
          n="ab"

          第 12 步：递归级别 2
            乞求 = "c"
            结束 = “ab”
            cntr = 4
            我 = 0
            n = "b"

            第 13 步：递归级别 3
            乞求 =“ca”
            end = "b", 这是一个基本情况 --> 打印 beg+end = cab
            cntr = 0
            我 = 0
          返回递归级别 2

          第 14 步：递归级别 2
            乞求 = "c"
            结束 = “ab”
            cntr = 5
            我 = 1
            n = "一个"

            第 15 步：递归级别 3
            乞求=“cb”
            end = "a", 这是一个基本情况 --> 打印 beg+end = cba
            cntr = 6
            我 = 1
          返回递归级别 2
        返回递归级别 1
      结尾。
于 2013-09-14T15:20:57.400 回答
0

如果我理解正确，comb请获取一个字符串并显示该字符串中的字符可以重新排列的所有方式。例如，如果您输入"abc"，程序将给出以下输出：

abc
acb
bac
bca
cab
cba
Number of combinations are : 6

这里的部分问题是comb's 的名称对正在发生的事情不是很清楚。如果我要维护这段代码，我会重命名beg为combinedChars和（或者可能是 ），因为该函数通过在每个递归级别将单个字符从to移动来工作。该算法基本上是：enduncombinedCharsremainingCharsendbeg

  • 是否只剩下一个字符可以组合？
    • 如果是这样，只有一种方法可以将它与已经洗牌的字符结合起来，所以结合它，打印结果，并更新计数。
    • 如果没有，请查看尚未合并的字符列表。依次将每个字符作为组合中的下一个字符，然后对剩余的未组合字符重复该过程，直到只剩下一个。
于 2013-09-14T13:26:46.667 回答