关于Nim游戏胜负判断的C++代码逻辑及return语句疑问

先看这段用于判断Nim游戏胜负的C++代码：

#include <iostream>
using std::cout;
using std::cin;
using std::endl;

bool winning(int x, int y, int z)
//x,y,z = number of stones in the 3 piles.
//returns true if this is a winning position.
{
    if (x==0 && y==0 && z==0) return false;    // base case

    for (int i=1; i<=x; ++i)                   // Pick i stones from pile 1
        if (!winning(x-i, y, z)) return true;  // if a losing next state is found

    for (int i=1; i<=y; ++i)                   // Pick i stones from pile 2
        if (!winning(x, y-i, z)) return true;  // if a losing next state is found

    for (int i=1; i<=z; ++i)                   // Pick i stones from pile 3
        if (!winning(x, y, z-i)) return true;  // if a losing next state is found

    return false;                              // if all next states are winning
}
int main() {
    int x,y,z;
    cout << "Give the number of stones in the 3 piles: ";
    cin >> x >> y >> z;
    if (winning(x,y,z)) cout << "Wins." << endl;
    else cout << "Loses." << endl;
}

代码实际执行逻辑 #

这段代码用递归实现了Nim游戏的胜负判断，核心是基于博弈论的状态推导：

• 基础状态：当三堆石头都为空（x==0 && y==0 && z==0），当前玩家没有任何石头可拿，直接输掉游戏，所以返回false。
• 必胜态判断：当前玩家尝试从任意一堆里拿1到全部数量的石头，生成新的游戏状态。如果存在某一种拿法，让对手进入必败态（也就是!winning(新状态)为真），那当前状态就是必胜态，立刻返回true——因为玩家可以选择这个走法确保自己赢。
• 必败态判断：如果遍历完所有可能的拿法，对手都会进入必胜态，那当前状态就是必败态，返回false。

程序如何区分不同状态值 #

虽然所有递归最终都会触碰到x=y=z=0的基础情况，但每个递归调用都是独立的函数执行实例：

• 每次调用winning函数时，都会在调用栈中创建一个新的栈帧，里面保存了当前调用的x、y、z参数副本，以及局部变量（比如循环里的i）和执行位置。
• 不同的状态对应不同的栈帧，它们的参数值完全独立，不会互相干扰。比如调用winning(3,2,1)时，会生成winning(2,2,1)、winning(1,2,1)等子调用，每个子调用的参数都是自己的，栈会记录这些上下文，直到触达基础情况后，再逐层向上返回结果。

return语句的通用用法 #

return是C++里控制函数执行流程和返回结果的核心语句，主要用法有：

• 返回结果给调用者：对于有返回值的函数（比如这里的bool类型函数），return后面跟着的表达式会被计算，然后把结果传递给调用这个函数的地方。比如return true就是告诉调用者当前状态是必胜态。
• 立即终止函数执行：只要执行到return语句，不管函数后面还有多少代码，都会立刻停止当前函数的执行，回到调用它的位置继续运行。比如递归里找到能让对手必败的走法时，直接return true，不会再遍历剩下的拿法。
• 无返回值函数的提前终止：对于void类型的函数，可以用return;（不带值）来提前结束函数，不需要返回任何内容。
• 递归的终止条件：在递归函数里，return常用来标记基础情况的结束，避免无限递归。比如代码里的return false就是终止空堆状态的递归分支，返回结果。

内容的提问来源于stack exchange，提问作者KeShAw