递归算法是编程时被经常应用的算法。本人并非编程专业人员，只是为了搞懂拜占庭将军问题查找资料时，偶然间得知这种算法的存在。因此，本文仅针对递归算法发表一些在数学层面和思维层面的粗浅个人理解。
目前，绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。虽然递归算法的常见应用场景是编程，但它来源于数学的归纳法，因此其应用场景不仅仅限于此。弄清递归算法或者具备递归思维，对我们平时解决和理解一些实际问题不无益处。
让我们先来了解什么是递归算法。百度百科上对递归算法是这样定义的：
递归算法是指一种通过重复将问题分解为同类的子问题而解决问题的方法。也可以说成是，把规模大的问题转化为规模小的相似的问题来解决。
上面这个定义过于抽象，为了便于理解，知乎答主李鹏用查词典来形容递归，他是这样比喻的：
当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查第二个词。可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是完全能懂的。此时，递归达到了临界点，走到了尽头。然后，开始倒退，逐个明白之前查过的每个词。最终，你弄明白了最开始的那个词的意思。
下面，结合上面这个例子我们把递归分解为以下三个步骤：
1、递过去：把一个大问题分解成若干个规模较小、与原问题形式相同的子问题，这些子问题可以用相同的思路来解决。问题递过去的过程实际上是问题由大到小演化的过程。就像上面例子中，可以用查字典这样一个相同的办法依次查找每一个词语的含义，来解决每一个小问题。
2、到达临界点：问题演化到一个明确的临界点，无法（或者不用）再往更小更远的地方走下去。就像上面这个例子，当每一个词都查明白了的时候就是到达临界点的时候，不必再去查找下一个词语。
3、归回来：从临界点开始，原路返回到原点，原问题解决。就像上面例子中，到达临界点后，向原点返回，逐个明白之前查过的每个词，最终弄明白了最开始的那个词的意思，问题解决。
现在，我们把递归算法用于对拜占庭将军问题口头版算法的理解：
我们所说的拜占庭将军问题一般是指广义的拜占庭将军问题，它等价于如何让一个将军（有可能是间谍）对所有接受者的命令保持一致，即狭义的拜占庭将军问题。
解决狭义的拜占庭将军问题的算法分为口头版和签名版。口头版算法对传令兵的要求有：命令的信道可靠；命令的来源可知，但上一来源未知；如有将军不发命令，可以被感知。
口头版算法描述如下：
一、OM(0)：0个叛徒的情况
1. 将军发送自己的观测结果给所有接受者
2. 每个接受者使用他们接收到的来自将军的结果进行一致行动。
二、OM(m)：m个叛徒的情况
1、将军发送自己的命令给所有接受者
2、递归开始，接受者收到来自将军的命令v后，并不直接接受， 而是让自身成为OM(m-1)的将军继续转发v
3、每个接受者收集除了自身的所有接受者在OM(m-1)作为将军时发给自身的结果，即（v1、v2、v3……）
4、某接受者在告诉别的接受者来自将军的命令的时候，别的将军会怀疑这个接受者是不是叛徒。判断这个接受者是否忠臣的唯一的办法是询问别的接受者，“这个接受者告诉你将军都发了啥?”
5、每次递归都做悲观预期，即将军是个叛徒， 那么就达成了OM(m)—>OM(m-1)—>OM(m-2)—>……OM(0)的递归效果。
6、将结果反向带入，最终获得的（v1、v2、v3……）的majority校验。
网友评论