像这样的游戏（河内塔是另一个经典例子）旨在说明归纳和递归的数学原理，递归与编程特别相关。
我们想确定一堆n块石头是赢堆还是输堆。直观地说，赢牌堆是这样的，无论对手做出什么样的选择，你总能拿走一定数量的棋子来保证你会赢。同样，失败的牌堆是这样一种牌堆，无论你做出什么选择，你总是给对手留下一个获胜的策略。
显然，n = 0是输桩；你已经输了。并且n = 1是一个胜利堆，因为你拿了一块石头并离开你的对手n=0。那么n=2呢？好吧，你只被允许拿一块石头，此时你已经给了你的对手一个获胜的堆（n=1），所以n=2是一个失败的数字。我们可以使这在数学上更精确。
定义：如果n=0 ，则整数n是失败者，或者对于1 和sqrt(n)之间的每个整数k，nk是胜利者。如果在 1 和sqrt(n)之间存在某个整数k使得nk是失败者，则整数n是获胜者。
在这个定义中，n是堆的大小，k是你选择拿的石头的数量。如果要移除的每一个有效数量的棋子都给你的对手一个获胜的堆，那么一个堆就是一个失败的堆，而一个获胜的堆是某个选择给你的对手一个失败的堆的堆。
当然，这个定义应该让你有点不安，因为我们实际上不知道它是否对我们已经检查过的n=0,1,2以外的任何东西有意义。也许某个数字既符合赢家也符合输家的定义，或者两者都不符合。这肯定会令人困惑。这就是归纳的用武之地。
定理：每个非负整数要么是赢家，要么是输家，但不是两者兼而有之。
证明：我们将使用强或完全归纳原理。我们知道n=0是失败者（根据定义），我们已经证明n=1是胜利者，而n=2直接是失败者。这些是我们的基本情况。
现在让我们考虑一些整数n_0 > 2，我们将假设（使用强归纳法）每个小于n_0的非负整数要么是赢家要么是输家，但不是两者兼而有之。让s = floor(sqrt(n_0))并考虑整数集P = {n_0-s, n_0-s+1, ..., n_0 - 1}。（因为{1, 2, ..., s}是要移除的可能选择的棋子的集合，所以P是我可以留给对手的棋子的集合。）通过强归纳，因为P中的每个值都是非负数小于n_0的整数，它们每个都是赢家或输家（但不是两者）。如果P中的任何值是失败者，那么根据定义，n_0是赢家（因为您移除了足够多的石头，让您的对手输掉了一堆）。如果不是，那么P中的每个值都是赢家，那么n_0就是输家（因为无论你拿了多少石头，你的对手仍然有一堆赢家）。因此，n_0要么是赢家，要么是输家，但不是两者兼而有之。
通过强归纳，我们得出结论，每个非负整数要么是赢家，要么是输家，但不是两者兼而有之。
量子点
好的，如果您对归纳感到满意，那将非常简单。但我们所展示的是，我们非常直观的定义实际上是有道理的，你得到的每一堆要么是赢家（如果你打得正确），要么是输家（如果你的对手打得好）。我们如何确定哪个是哪个？
好吧，归纳导致递归。让我们为我们的两个定义编写递归函数：n是赢家还是输家？这是一些没有错误检查的类 C 伪代码。
bool is_winner(int n) {
// check all valid numbers of stones to remove (k)
for (int k = 1; k <= sqrt(n); k++) {
if (is_loser(n-k)) {
// I can force the loser n-k on my opponent, so n is a winner
return true;
}
}
// I didn't find a way to force a loser on my opponent, so this must be a loser.
return false;
}
bool is_loser(int n) {
if (n == 0) { // this is our base case
return true;
}
for (int k = 1; k <= sqrt(n); k++) {
if (!is_winner(n-k)) {
// we found a way to give them a pile that ISN'T a winner, so this isn't a loser
return false;
}
}
// Nope: every pile we can give our opponent is a winner, so this pile is a loser
return true;
}
当然，上面的代码有些多余，因为我们已经证明每个数字要么是赢家，要么是输家。因此，将其实现is_loser为仅返回更有意义，!is_winner反之亦然。也许我们只是is_winner作为一个独立的实现来做。
bool is_winner(int n) {
if (n < 0) {
// raise error
} else if (n == 0) {
return false; // 0 is a loser
} else {
for (int k = 1; k <= sqrt(n); k++) {
if (!is_winner(n-k)) {
// we can give opponent a loser, this is a winner
return true;
}
}
// all choices give our opponent a winner, this is a loser
return false;
}
}
用这个函数来回答这个问题，如果游戏开始时有n颗棋子，玩家 A 先走，并且两个玩家都玩得最佳，那么玩家 A 获胜，如果is_winner(n)玩家 B 获胜!is_winner(n)。要弄清楚他们的游戏应该是什么，如果你有一个获胜的牌堆，你应该选择一些有效的k使得nk是失败者（哪个不重要，但最大的值将使游戏以最快的速度结束），如果给你一个失败的堆，你选择什么都没关系——这就是失败者的点，但同样，选择最大的k值会使游戏更快结束。
这些都没有真正考虑性能。由于n可能非常大，因此您可以考虑很多事情。例如，至少在单个递归调用中预先计算您要考虑的n的常见小值，或使用Memoization 。此外，正如我之前所建议的，移除k的最大值会以更少的回合结束游戏。同样，如果您反转循环并首先检查k的最大允许值，您应该能够减少递归调用的数量。
当然，真正快速的方法是做更多的数学运算并找出n的一些简单属性，您可以检查这些属性将确定它是赢家还是输家。