第1章引论

当一个函数用它自己来定义时就被称为是递归的。

递归的四个基本法则

1.基准情形。必须总要有某些基准的情形，它们不用递归就能求解

2.不段推进。对于那些要递归求解的情形，递归调用必须总能够朝着一个基准情形推进。

3.设计法则。假设所有的递归调用都能运行。

4.合成效益法则。在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作

类型限界在尖括号内指定，它指定参数类型必须具有的性质。

 1     public static <AnyType extends Comparable<? super AnyType>>
 2     AnyType findMax(AnyType[] arr)
 3     {
 4         int maxIndex = 0;
 5 
 6         for (int i = 1; i < arr.length; i++)
 7             if (arr[i].compareTo(arr[maxIndex]) > 0)
 8                 maxIndex = i;
 9 
10         return arr[maxIndex];
11     }

函数对象，重写findMax

 1     public static <AnyType>
 2     AnyType findMax(AnyType[] arr, Comparetor<? super AnyType>cmp)
 3     {
 4         int maxIndex = 0;
 5 
 6         for (int i = 1; i < arr.length; i++)
 7             if (cmp.compare(arr[i], arr[maxIndex]) > 0)
 8                 maxIndex = i;
 9 
10         return arr[maxIndex];
11     }

1 class CaseInsensitive implements Comparetor<String>
2 {
3     @Override
4     public int compare(String lhs, String rhs)
5     {
6         return lhs.compareToIgnoreCase(rhs);
7     }
8 }

1 public interface Comparetor <AnyType>
2 {
3     int compare(AnyType lhs, AnyType rhs);
4 }

1.5 编写一种递归方法，它返回数N的二进制表示中1的个数。利用这种事实：如果N是奇数，那么其1的个数等于N/2的二进制表示中1的个数加1。

1    public static int ones(int n)
2    {
3        if (n < 2)
4            return n;
5 
6        return n % 2 + ones(n / 2);
7    }

第1章 引论

第1章引论