递归1-初识递归

I. 递归简论

• 递归的概念

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

• 递归的基本法则

  当编写递归程序时，关键是要牢记递归的四条基本法则:
  1.基准情形 (base case)。必须总要有某些基准情形，它无需递归就可以解出。
  2.不断推进 (making progress)。对于那些需要递归的求解的情形，每一次递归调用都必须要使情况朝向一种基准情形推进。
  3.设计法则 (design rule)。假设所有的递归调用都能运行。
  4.合成法则 (compound interest rule)。在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。
   使用递归计算诸如斐波那契数之类简单数学函数的值的想法一般来说不是一个好主 意，其道理正是根据第四条法则。

II. 递归与数学归纳法

• 数学归纳法的思想

   一般地，证明一个与自然数 n 有关的命题 P(n)，有如下步骤:
  (1) 证明当 n 取第一个值 n₀ 时命题成立;
  (2) 假设当n=k(k⩾n₀)时命题成立，证明当n=k+1时命题也成立。
  综合(1)(2)，对一切的自然数 n(n ⩾ n₀)，命题 P(n) 都成立。
  其实，数学归纳法利用的是递推的原理，可以形象地叫做多米诺原理。 数学归纳法的关键就是如何证明当 n = k + 1 时命题也成立。

• 递归的思想

    很明显，递归也是用了递推的思想。
  (1) 首先，我们需要一个递归的出口，即 base case;
  (2) 其次，是递归体的设计，即对于一个一般的情况如何向 base case 靠近，把它化解成为一个更小的，同样结构的问题。
  递归的关键就是将问题转化成一个更小规模的同样结构的问题。

III. 递归的经典例子

• n!的递归算法

    求解 n! 是最经典入门的递归算法。根据前面的知识我们知道用递归解决这个问题，需要两个要点。首先，如何将一个大的问题转化成一个小规模的问题?我们知道，n! = n(n − 1)!， 那么根据这个公式，我们就可以轻易地将求解 n! 转化为求解 (n − 1)!(将问题的规模变小了，并且是同样的问题)。其次，如何找到 base case，即递归的出口呢?在该问题里面也是很明显的，最后求 1! 时，就不需要在递归了。所以，该递归算法可以写为:

int factorial(int n){
   if (n == 1)
       return 1; // base case
   return n * factorial(n − 1); // making progress
}

• 汉诺塔的递归算法

    如下图所示，从左到右 A、B、C 三根柱子，其中 A 柱子上面有从小叠到大的 n 个圆盘。 现要求将 A 柱子上的圆盘移到 C 柱子上去，期间只有一个原则:一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数。
  汉诺塔示意图.png
  1. 算法分析:
    当 A 柱子上只有一个盘子时，可以直接把盘子移到 C 柱子上;当 A 柱子上有两个盘子时，需要借助 B 盘子，先将上面的小盘子移到 B 柱子上，再将大盘子移到 C 柱子上，再将小盘子移到 C 柱子上。那对于更一般的情况，当有 n 个盘子的时候怎么递归呢?当有 n 个盘子时，我们可以将盘子看成两个部分。第 n 个盘子和上面 n − 1 个盘子，如图中的颜色区分。就像是操作两个盘子(把前 n − 1 个盘子看成一个整体):先把前 n − 1 个盘子从 A 盘放到 B 盘，再把第 n 个盘子从 A 盘放到 C 盘，最后再把前 n − 1 个 盘子从 B 盘放到 C 盘。这样我们就把问题的规模缩小到 n − 1 了。
  2. 算法的Java实现:

/**
 * @Author: 落脚丶
 * @Date: 2017/10/14
 * @Time: 下午8:33
 * @ClassName: HanoiTower
 * @Description: 汉诺塔的递归算法
 */

import java.util.Scanner;

public class HanoiTower {
    private static int step = 0; // 记录步数

    public static void main(String[] argus){
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入盘子的个数:");
        int count = scanner.nextInt();
        hanoi(count, 'A', 'B', 'C');
    }
    /**
    * @Date: 2017/10/14
    * @Time: 下午9:27
    * @Method: hanoi
    * @Description:
     * 将n个盘子从a塔移动到c塔，需要借助中间塔b。
     * 最后一个塔只需要直接移动即可
     *
    */
    private static void hanoi(int n, char a, char b, char c){
        /**
         * n为需要移动的盘子数；
         * a是最开始放盘子的塔；
         * b是中间中转的塔；
         * c是最终需要放盘子的塔。
         */
        if (n == 1) {
            // 递归的base case 只有一个盘子的时候，直接把盘子从a塔移到c塔
            move(1, a, c);
        }else {
            /**
             * 对于递归的一般情况，把前n-1个塔看做是一个整体，整体移动，
             * 那么现在就相当于两个塔，
             * 注意：hanoi(n, a, b, c)方法的含义就是利用中间塔b，
             * 把n个盘子从a塔移到c塔！
             * 我们只需要下面三步：
             * 1. 把前n-1个盘子，从a塔移到b塔，需要借助中间塔c；
             * 2. 把第n个盘子从a塔移到c塔；
             * 3. 把前n-1个盘子从b塔移到c塔，需要借助中间塔a。
             */
            hanoi(n - 1, a, c, b);
            move(n, a, c);
            hanoi(n - 1, b, a, c);
        }
    }
   private static void move(int number,char origin, char target){
        System.out.println("第" + ++step + "次移动：" + number +
                "号盘子，" + origin + " ----> " + target);
    }
}
/**
 * 以3个盘子为例的输出：
 *
 * 请输入盘子的个数:
 * 3
 * 第1次移动：1号盘子，A ----> C
 * 第2次移动：2号盘子，A ----> B
 * 第3次移动：1号盘子，C ----> B
 * 第4次移动：3号盘子，A ----> C
 * 第5次移动：1号盘子，B ----> A
 * 第6次移动：2号盘子，B ----> C
 * 第7次移动：1号盘子，A ----> C
 */