递归，一场数学与算法的永恒对话

有些规律，从未消失，只是换了一种方式重复出现。

计算机科学中，没有一个概念能像“递归”那样，既简洁深邃，又威力无穷。

它只有一条原则：

要理解当前这一步，

先去理解上一步。

而这条原则，恰好是打开组合数学众多经典问题的一把钥匙。

01

从“不允许连续出现a”的字符串说起

一个有趣的问题开启了递归的篇章：传输由字母a、b、c构成的字符串，但不允许两个a连续出现。问符合上述要求的长度为n的字符串有多少种？

直接计数非常困难，但递归提供了清晰的思路：

最左侧字母为b或c时，剩下部分依然是合法字符串，方案数为2f (n-1)

最左侧字母为a时，第二个字母必为b或c，剩下部分也是合法字符串，方案数为 2f (n-2)

由此得到递归关系：

配合边界条件f (1)=3, f (2)=8，整个数列就被唯一确定了。这就是递归的力量——

用有限的规则，

描述无限的可能。

02

斐波那契数：自然界的数学密码

这个著名的整数数列定义简单却内涵丰富：

更令人惊叹的是它的显式解可以表示为无理的黄金分割数的形式：

并且，每一个正整数都可以唯一地表示为一系列不连续的斐波那契数之和，比如：

50 = 34 + 13 + 3

100 = 89 + 8 + 3

这个性质在数据编码和压缩中有着奇妙的应用。

03

卡特兰数：无处不在的组合规律

这个神奇的数列出现在无数场景中：括号匹配、二叉树形态、网格路径...它的通项公式简洁优美：

从凸多边形三角剖分问题中，我们可以推导出它的递归起源：

这个关系看似复杂，却最终导向了那个简洁的显式解。

04

斯特林数：集合与排列的计数艺术

第二类斯特林数计算的是将n 个元素划分到k 个非空子集的方式数：

而第一类斯特林数则与圆排列密切相关：

特别地，n 个元素所有排列的总数与第一类斯特林数满足：

这个关系将排列数与圆排列美妙地连接起来。

05

快速排序：递归的算法典范

快速排序的效率分析完美展示了递归的实用性。其平均比较次数满足：

通过巧妙的数学变换，可以得到：

其中H(n) 是调和数。

由于

（欧拉常数），所以：

即快速排序的平均时间复杂度为O (n logn )。

递归是一种思想，也是一种美学。

它告诉我们：再复杂的问题，也可以分解成更简单的自己；再庞大的系统，也是由基本模块递归构建而成。

从数学定理到算法设计，从自然现象到人工系统，递归无处不在。掌握这种思维，就等于获得了一把解开复杂世界奥秘的钥匙。

关键词：#递归 #组合数学 #算法 #斐波那契 #卡特兰数 #斯特林数 #快速排序

关于《组合数学及应用》

本文整理自《组合数学及应用》一书。本书由刘关俊教授编写，科学出版社出版，是国家自然科学基金资助项目。本书不仅讲数学，更讲数学在计算机科学、人工智能、信息安全等领域的应用。通过上述专业领域的案例展现组合数学在解决复杂问题中的重要作用，适合希望将数学工具应用于实际场景的读者。

《组合数学及应用》

刘关俊 编著

北京 : 科学出版社 , 2025.1

ISBN978-7-03-080121-0

责任编辑：杨　凯

本书的创作初衷，是为了弥补现有组合数学书籍的不足：只聚焦数学原理，而忽略这些原理在其他领域的应用。虽然偶有书籍会提及一些应用，但通常只是浅尝辄止，覆盖面不够广泛。众所周知，组合数学是许多专业领域，尤其是计算机科学和电子信息技术的基础。在当前信息技术、计算机科学和人工智能迅猛发展的背景下，一本既深入讲解组合数学原理，又广泛展示其在这些领域应用的书籍，将为广大读者提供一个更广阔的视野。

如果你属于以下领域，这本书将为你提供坚实的数学基础：

本书共八章，系统介绍组合数学的基础知识与原理，每章配有一个精心挑选的应用案例，涉及计算机科学、软件工程、人工智能、大数据和通信技术等领域。即使读者在某些专业领域没有深入学习过，也能通过细致的讲解完全理解相应的应用案例，既拓宽了知识面，又激发了对组合数学的兴趣，并感受到数学之美。

（本文编辑：刘四旦）