AP计算机教程10-1：递归

AP计算机A的考试中通常有四五道递归问题。你只需要知道如何追踪递归method（推断出它们返回或输出什么），不需要自己写递归方法。

递归(recursion)的意思是某个method调用它自己，如这个例子所示。

public static void neverEnd()
{
  System.out.println("This is the method that never ends!");
  neverEnd();
}

method会先输出This is the method that never ends!然后再调用自己，导致无限递归(infinite recursion)。当然这一般是我们需要避免的状况。

如果能够正确使用递归，在某些情况下能够大大降低编程的复杂程度，这是一个计算阶乘(factorial)的method。\(n\)的阶乘被定义为\(n f(n-1)\)，当然\(f(0)=1\)，因此递归不会无限继续下去。

public static int factorial(int n)
{
  if (n == 0)
    return 1;
  else
    return n * factorial(n-1);
}

Is the following method recursive?

public static int mystery()
{
   int total = 0;
   for (int i=10; i>0; i--)
   {
      total = total + i;
   }
   return total;
}

Is the following method recursive?

public static int mystery2(int x)
{
   if (x == 1) return 1;
   else return x + mystery2(x-1);
}

What is the value of n when this method stops calling itself (when it reaches the base case)?

public static int product(int n)
{
   if(n == 1)
      return 1;
   else
      return n * product(n - 2);
}

What is/are the values of the variable bunnies when this method stops calling itself (when it reaches the base case)?

public static int bunnyEars(int bunnies)
{
   if (bunnies == 0) return 0;
   else if (bunnies == 1) return 2;
   else return 2 + bunnyEars(bunnies - 1);
}

为什么使用递归？

当所需要解决的问题有不断重复的结构时，递归可能会是一条捷径。例如，当你想知道电脑中的某个文件夹占用了多少硬盘空间，就可以使用递归来层层计算子目录的空间占用，再在最后求和。

递归还可以被用来创造分形(fractal)。一个简单的例子是谢尔宾斯基三角形(Sierpinski’s triangle)。你先将三角形分成四个小三角形，然后再对除中间三角形以外的三个小三角形重复这一步骤。