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


0:00

Is the following method recursive?

public static int mystery()
{
   int total = 0;
   for (int i=10; i>0; i--)
   {
      total = total + i;
   }
   return total;
}
mystery()没有调用它自己。
2

Is the following method recursive?

public static int mystery2(int x)
{
   if (x == 1) return 1;
   else return x + mystery2(x-1);
}
mystery()调用了它自己。
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);
}
if的条件n == 1满足时,return语句里返回常数,不再有递归。
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);
}
if的条件bunnies == 0bunnies == 1满足时,return语句里返回常数,不再有递归。
3

为什么使用递归?

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

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


陈 欣

AADPS创始人

发表评论