1

这个函数有什么作用？你如何评价它？

如何追踪它？如何理解递归方法？

我就是看不懂递归，考试的日子快到了，而且我知道要想理解递归，就必须先理解递归。

但我就是不能写一个稍微复杂的递归方法，谁能帮我用最简单的英文单词。

public class BalancedStrings {

    public static void printBalanced(String prefix, int a, int b) {
        if (a > 0)
            printBalanced(prefix + "a", a - 1, b);
        if (b > 0)
            printBalanced(prefix + "b", a, b - 1);
        if (a == 0 && b == 0)
            System.out.println(prefix);
    }

    public static void printBalanced(int n) {
        if (n % 2 == 0) {
            printBalanced("", n / 2, n / 2);
        }
    }

    public static void main(String[] args) {
        printBalanced(4);
    }
}
4

4 回答 4

6

调用printBalanced()是递归调用。识别递归的方法是函数调用自身。使用树绘制时最好理解递归：

在此处输入图像描述

树的分支将继续创建更多函数，直到满足结束条件，在本例中为a == 0 && b == 0. 您提供的函数看起来像是以递归方式打印字符串“前缀”与指定数量的“a”和“b”字符连接。当变量a和b到达0时，递归停止并使用打印结果System.out.println(prefix);

在主函数中，您将整数 4 传递给printBalanced(int n)调用printBalanced(String prefix, int a, int b)参数，如下所示：printBalanced("",2,2);

总体结果是前缀与平衡数量的 a 和 b 连接

于 2012-06-29T15:16:27.650 回答
0

你的停止条件是

a == 0 & b == 0

在满足此条件之前，您递归地调用函数并降低 a 和 b 直到它们都为 0。

尝试在 printBalanced() 中设置一些断点，以便了解它是如何工作的。

于 2012-06-29T15:20:55.507 回答
0

在最基本的计算机科学意义上，递归是一个调用自身的函数。递归的实际用法很少。

树遍历
图
Lexing/Parsing
排序

递归的基本思想是你把原始问题分成更小的（更容易解决的）实例，解决那些更小的实例（通常再次使用相同的算法），然后将它们重新组合成最终的解决方案。

例如，考虑以下计算一个数的阶乘的 C 代码

function factorial(int n)
{
  int fact = 1;
  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }
  return fact;
}
于 2012-06-29T15:21:43.717 回答
0

通过在每次调用 printBalanced 之前放置 print 语句以及将 print 语句作为每个 printBalanced 方法定义的第一行，它可以帮助您查看递归。见下文：

public class BalancedStrings {

    public static void printBalanced(String prefix, int a, int b) {
        System.out.println( "printBalanced called prefix = " + prefix + " a = " + a + " b = " + b );
        if (a > 0) {
            System.out.println( "printBalanced calling printBalanced with prefix = " + prefix + " a-1 = " + (a-1) + " b = " + b );
            printBalanced(prefix + "a", a - 1, b);
        }
        if (b > 0) {
            System.out.println( "printBalanced calling printBalanced with prefix = " + prefix + " a = " + a + " b-1 = " + (b-1) );
            printBalanced(prefix + "b", a, b - 1);
        }
        if (a == 0 && b == 0)
            System.out.println(prefix);
    }

    public static void printBalanced(int n) {
        System.out.println( "printBalanced called n = " + n );
        if (n % 2 == 0) {
            printBalanced("", n / 2, n / 2);
        }
    }

    public static void main(String[] args) {
        printBalanced(4);
    }
}

此外，printBalanced 也被称为重载方法，因为它有两个“方法签名”，这基本上意味着它被定义了不止一次，并且每个方法定义都有一组不同的变量传递给方法。

基本上，printBalanced 会一直调用自己，直到变量 a 和 b 减为零。然后它将打印出它不断累积的结果前缀。

此外，所有这些魔法都可能发生，因为每个方法调用都会将前缀、a 和 b 的当前状态推送到调用堆栈上。当方法最终返回而不进行递归调用时，堆栈就会展开。

我希望这个对你有用！递归可能很难理解。您还可以通过自己玩计算机并通过在纸上写下将被压入调用堆栈的前缀、a 和 b 的值来跟踪方法的执行来手动跟踪调用。

这是包含跟踪打印的程序的输出：

C:\Users\>java BalancedStrings
printBalanced called n = 4
printBalanced called prefix =  a = 2 b = 2
printBalanced calling printBalanced with prefix =  a-1 = 1 b = 2
printBalanced called prefix = a a = 1 b = 2
printBalanced calling printBalanced with prefix = a a-1 = 0 b = 2
printBalanced called prefix = aa a = 0 b = 2
printBalanced calling printBalanced with prefix = aa a = 0 b-1 = 1
printBalanced called prefix = aab a = 0 b = 1
printBalanced calling printBalanced with prefix = aab a = 0 b-1 = 0
printBalanced called prefix = aabb a = 0 b = 0
aabb
printBalanced calling printBalanced with prefix = a a = 1 b-1 = 1
printBalanced called prefix = ab a = 1 b = 1
printBalanced calling printBalanced with prefix = ab a-1 = 0 b = 1
printBalanced called prefix = aba a = 0 b = 1
printBalanced calling printBalanced with prefix = aba a = 0 b-1 = 0
printBalanced called prefix = abab a = 0 b = 0
abab
printBalanced calling printBalanced with prefix = ab a = 1 b-1 = 0
printBalanced called prefix = abb a = 1 b = 0
printBalanced calling printBalanced with prefix = abb a-1 = 0 b = 0
printBalanced called prefix = abba a = 0 b = 0
abba
printBalanced calling printBalanced with prefix =  a = 2 b-1 = 1
printBalanced called prefix = b a = 2 b = 1
printBalanced calling printBalanced with prefix = b a-1 = 1 b = 1
printBalanced called prefix = ba a = 1 b = 1
printBalanced calling printBalanced with prefix = ba a-1 = 0 b = 1
printBalanced called prefix = baa a = 0 b = 1
printBalanced calling printBalanced with prefix = baa a = 0 b-1 = 0
printBalanced called prefix = baab a = 0 b = 0
baab
printBalanced calling printBalanced with prefix = ba a = 1 b-1 = 0
printBalanced called prefix = bab a = 1 b = 0
printBalanced calling printBalanced with prefix = bab a-1 = 0 b = 0
printBalanced called prefix = baba a = 0 b = 0
baba
printBalanced calling printBalanced with prefix = b a = 2 b-1 = 0
printBalanced called prefix = bb a = 2 b = 0
printBalanced calling printBalanced with prefix = bb a-1 = 1 b = 0
printBalanced called prefix = bba a = 1 b = 0
printBalanced calling printBalanced with prefix = bba a-1 = 0 b = 0
printBalanced called prefix = bbaa a = 0 b = 0
bbaa
于 2012-06-29T15:30:22.593 回答