基础-4：递归的三个例子

概述

前文中讲解了递归的运行机制，并讲解了简单的递归情况。从程序设计的角度来将，递归其实是现代程序设计不可或缺的一种方法，对于很多问题，用递归可能是一种较为合适的解决方法。但是如何设计递归需要设计或者求解出递推公式，才能转换为递归，其中的重点是设计递推公式。本文如下部分讲解三个例子，一个是人人皆知的汉诺塔，一个是求排列，一个是求整数划分，重点讲解如何设计递归公式。更详细的代码请见我的github

例1：汉诺塔

汉诺塔是学程序设计的童鞋必备的一环，其约束为：始终保持打圆盘不能在小圆盘之上，从一根柱子一到另一根柱子，中间可以借助一根柱子，示意图如图1所示：

图1:汉诺塔示意图，摘自维基百科

直觉上这应该是一个递归问题，但是如何设计递推公式是很多童鞋觉得比较头疼的问题。设计递推公式的本质就是形式化，寻找规模为n的问题和规模为n-1（或者小于n-1）的问题之间关系。

那如何对汉诺塔来设计递推公式呢？先对其中涉及的对象形式化描述，假设三根柱子分别编号为A, B, C，汉诺塔中的圆盘数为n，初始时n个圆盘在A中，求解的问题为：借助B，将A中的n个圆盘移动到C，且要适中保持小盘不能在大盘之下。形式化为：F(n, A, B, C)；接下来就要分析其中的过程，必然如下所述（肯定要先想办法把A中最底部的最大圆盘移到C盘上）：

• 将A中上面的n-1个圆盘借助C盘放在B盘上,其对应的问题形式化为F(n-1, A, C, B)
• 将A中最下面的圆盘放在C中；
• 将B中的n-1个圆盘借助A放置在C上,其对应的问题形式化为F(n-1, B, A, C)。

当然，这还没完，还必须定义终止条件，否则就是无限循环，这个问题中的终止条件为：当n=1时，直接移动，不用接住中间柱子。其对应的golang程序为：

func Hannoi(n int, first, second, third string){
    if n == 1{
        fmt.Println(first, "->", third)
    }else{
        Hannoi(n - 1, first, third, second)
        fmt.Println(first, "->", third)
        Hannoi(n - 1, second, first, third)
    }
}

例子2: 求排列

问题如下：

设计一个算法，实现{r₁,r₂,...,r_n}的全排列

这个问题相对例1来讲，困难一些（一般情况下，涉及纯数字游戏类的算法会困难一些）。先以例子来看，假设要求{1, 2, 3}的排列，我们一般情况下的思维逻辑是什么。通常情况下（天才不在此列），应该是：

123, 132 | 213, 231 | 312, 321，这样思考会比较规整

也就是说，假设数字集合为{r₁,r₂,...,r_n},要求这n个数字组成的集合S的排列F(S)，可以先取出其中的一个数r_m，然后将r_m放在剩下的n-1个数组成的排列F(S-{r_m})之前，则r_m在最前面的排列全部列玩了；如果取m = 1, 2, ...n，则列出了所有的排列。这个描述本身已经递归了，终止条件为：当S中的元素个数为1时，直接返回该数字（一个数字只有一个排列）。对应的golang程序如下所示：

func Permutation(input string) []string {
    ret := make([]string, 0)
    if len(input) == 1 {
        ret = append(ret, input)
        return ret
    }
    for idx, v := range input {
        var left string = ""
        if idx == 0 {
            left = input[1:]
        } else {
            pre := input[:idx]
            post := input[idx+1:]
            left = strings.Join([]string{pre, post}, "")
        }
        leftPermutaions := Permutation(left)
        for _, per := range leftPermutaions {
            oneUnit := strings.Join([]string{string(v), per}, "")
            ret = append(ret, oneUnit)
        }
    }
    return ret
}

例3：求整数的划分

数字划分的问题描述为：

将正整数n表示成一系列正整数之和:n=n₁+n₂+...+n_k， 其中n₁≥n₂≥...≥n_k≥1，k≥1。正整数n的这种表示称为正整数n的划分。 对于任意整数n，给出其划分的个数，如n=5，则其划分为：

• 5
• 4 + 1
• 3 + 2
• 3 + 1 + 1
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1
  即n=5时，有7种划分

相比例1和例2，这个问题更难一些，很难直接找出其中的递推关系，而且似乎也没有特别好的办法。如果定义F(n)为整数n的划分数，F(n-1)为n-1的划分数，很难直接找出二者之间的关系。

但是如果观察上述列出5的划分的过程，貌似有一些规律，每个划分中的最大的数从大往小在排，若设每个划分中最大的数为m，用P(n, m)表示整数n的划分中最大数不超过m的划分数，则有什么关系呢？

• a) 当n=m时，显然只有1个划分
• b) 当1 < m < n时，可以这样考虑两种情况：
  • 情况1: 先取出m作为划分中最大的数，则整数n-m的划分个数(划分中的最大数不能超过m，想想为什么)即为此种情况的个数，为P(n-m, m)
  • 情况2：再考虑划分中最大数为m - 1的情况，此种情况的划分个数为：P(n, m - 1).

因此, b）场景下P(n, m) = P(n, m - 1) + P(n - m, m)

• c) 当 m > n时，显然，这种情况出现在b)中情况1中继续执行时，根据语义：n的划分个数，且划分中最大数不能超过m（在这种情况下，这个条件显然是成立的），因此，这种情况的划分数为P(n, n)
• d) 当m = 1时，P(n, m) = 1， 显然成立。

对应的golang称为为：

// 求整数的不同划分数， 要求n > 0
// n: 待划分的整数，m: 划分中最大的整数
func DivideInteger(n, m int) int {
    if n <= 0 {
        return 0
    }
        // 当m为1时，必然是一个全为1的划分
    if m == 1 {
        return 1
    }
    if n < m {
        return DivideInteger(n, n)
    }
    if n == m {
        return 1 + DivideInteger(n, n - 1)
    }
    if n > m && n > 1 && m > 1{
        return DivideInteger(n, m - 1) + DivideInteger(n - m, m)
    }
    return 0
}

总结

虽然递归很常用，并且在一般的业务处理中，其逻辑也很简单，但是并不意味着寻找递归中的递推模式很简单。特别是在大数据当道的今天，数字求解已成为数据挖掘、机器学习很重要的一部分，如何快速寻找相应的递推公式公式需要一定的数学基础和经常的思维锻炼。总之，递推公式是递归的核心。