javascript - 如何提出适当的递归解决方案

这是一个场景，我在一次面试中被问到了下面的问题，我设法解决了其中的一部分，但是我在第二部分的问题上遇到了一些麻烦（我甚至不知道我是否正确地解决了第一部分，我只是想出了在这种情况下我可以编写的最好的代码）。所以让我来介绍一下问题：
考虑一下下面的两人游戏，在一连串的破折号和加号上进行。如果在回合开始时，字符串不包含一对相邻的破折号，则获胜！否则，请选择字符串中任意一对相邻的短划线“--”，并将其替换为“++”。我们轮流直到有人赢。
游戏示例：-+-----+-->-+-++--+-+-+++++（游戏结束）。
编写一个函数listMoves()，该函数接受一个位置字符串作为参数，并返回所有有效移动的列表。
示例：

listMoves("") == []
listMoves("--+---+") == ["+++---+", "--+++-+", "--+-+++"]

我的解决方案（用javascript）是：

var listMoves = function(arg) {
    if (arg === null) return;

    if (arg === "") {
        return [];
    }

    var result = [];
    var temp = '';
    var string = [];
    for (var i=0; i<arg.length; i++) {
        if (temp == '-' && arg[i] == '-') {
            string = arg.split('');
            string[i-1] = '+';
            string[i] = '+';
            console.log(string);
            result.push(string);
        } else if (arg[i] == '-') {
            temp = arg[i];
        } else if (arg[i] == '+' && temp == '-') {
            temp = '';
        }
     }

     return result;
}

问题的第二部分是：
在最佳状态下，每一个位置都是球员移动的输赢。编写一个函数isWin(position)，当位置是玩家移动的胜利时返回true。
示例：

isWin("") == true
isWin("---+") == false
isWin("----") == true
isWin("--+----+--+---++--") == ???

我设法弄明白我需要一个递归算法来解决这个问题，并且我可以使用我为问题1创建的函数（因此我将其包括在内）。
然而，我不能把我的想法编成代码。
为了将来的参考，有人能告诉我他们将如何着手解决这样的问题吗？
编辑1（增加了我在面试中的尝试）：

var isWin = function (position) {

    if (position === null) return;
    if (position === "") return true;

    var possibleMoves = listMoves(position);

    var win;

    if (possibleMoves.length < 1) {
        win = true;
    } else if (possibleMoves.length == 1) {
        win = false;
    } else {
        for (move in possibleMoves) {
            isWin(move);
        }
    }

    return win;
}

最佳答案

通过对结果递归调用listMoves，可以获得所有可能结果的树。
例如：
所有终端节点都可能是游戏的结束状态。然而，我们正试图从任何一个开始的位置，当球员发挥最佳，如果这个状态是一个胜利的状态。
这可以通过检查是否存在一个动作链而导致另一个游戏被迫选择一个动作，从而使开始的玩家得到一个赢条件状态：
因此，在前面的例子中，starting player有5个选择：
选择1将给下一个玩家3个选择：
其中一个选择是在轮到首发球员时获胜。
其他两个选择导致开始的球员得到另一轮。在这种情况下，首发球员只有选择，导致他们失败作为一个聪明的下一个球员，他会选择其中之一。
选择2会给下一个玩家2个选择。下一个玩家的两个选择都将导致开始的玩家在轮到他们时获胜。
选择3会给下一个玩家2个选择。下一个玩家的两个选择都会导致开始的玩家只有一个选择。当下一个玩家得到他们的回合时，他们的单选结果将获胜。
与选择2相同。
与选择1相同。
因为选择2和4存在，所以起始状态是开始玩家的一个胜利。
------是一个递归函数，它使用该逻辑来查找起始位置是否是起始玩家的胜负。
对于我们的问题，我们可以将起始播放器minimax标记为player1另一个玩家，True，作为player2。
如果对某个状态调用了False，则该状态没有可能的移动然后minimax将返回调用它的播放器。
当为s和minimax，minimax调用s时，如果有任何导致player1返回player == True的移动，则返回minimax(move, player2)（如果有任何player1结果，玩家将选择该结果）。
当为player1和minimax，s调用player2时，如果有可能的移动，则如果player == False的所有结果返回minimax(move, player1)，则返回（如果没有返回player1的结果，player2必须选择导致player2的移动，否则player1将选择导致player2获胜的移动）。
javascript代码：

function listMoves(s) {
  var moves = [];
  for (var i = 0; i < s.length - 1; i++) {
    if (s.substring(i, i + 2) === '--') {
      moves.push(s.substring(0, i) + '++' + s.substring(i + 2));
    }
  }
  return moves;
}

function minimax(s, player) {
  var moves = listMoves(s);
  if (moves.length === 0) {
    return player;
  }
  if (player) {
    return moves.some(function(move) {
      return minimax(move, !player)
    });
  } else {
    return moves.every(function(move) {
      return minimax(move, !player);
    });
  }
}

function isWin(s) {
  return minimax(s, true);
}

document.write("<pre>" + isWin("--+----+--+---++--"), '"--+----+--+---++--"' + "</pre>");

// From http://stackoverflow.com/a/12628791/635411
function cartesianProductOf() {
  return _.reduce(arguments, function(a, b) {
    return _.flatten(_.map(a, function(x) {
      return _.map(b, function(y) {
        return x.concat([y]);
      });
    }), true);
  }, [[]]);
};

var res = {}
for (var i = 1; i <= 6; i++) {
  var s = Array.apply(null, new Array(i)).map(String.prototype.valueOf, "-+");
  res[i] = {};
  cartesianProductOf.apply(null, s).forEach(function(state) {
    res[i][state] = isWin(state);
  });
}

document.write("<pre>" + JSON.stringify(res, null, 4) + "</pre>");

<script type="text/javascript" src="//cdnjs.cloudflare.com/ajax/libs/lodash.js/3.8.0/lodash.min.js"></script>

蟒蛇：

def list_moves(s):
    moves = []
    for i in range(len(s) - 1):
        if s[i] == "-" and s[i + 1] == "-":
            moves.append(s[:i] + "++" + s[i + 2:])
    return moves

def minimax(s, player=True):
    moves = list_moves(s)
    if not moves:
        return player
    n = (minimax(move, not player) for move in moves)
    return any(n) if player else all(n)

def is_win(s):
    return minimax(s)

print is_win(""), '""'
print
print is_win("-"), '"-"'
print is_win("+"), '"+"'
print
print is_win("--"), '"--"'
print is_win("+-"), '"+-"'
print is_win("-+"), '"-+"'
print is_win("++"), '"++"'
print
print is_win("----"), '"----"'
print is_win("+---"), '"+---"'
print is_win("-+--"), '"-+--"'
print is_win("--+-"), '"--+-"'
print is_win("---+"), '"---+"'
print is_win("++--"), '"++--"'
print is_win("-++-"), '"-++-"'
print is_win("--++"), '"--++"'
print is_win("-+-+"), '"-+-+"'
print is_win("+-+-"), '"+-+-"'
print is_win("+--+"), '"+--+"'
print is_win("+++-"), '"+++-"'
print is_win("-+++"), '"-+++"'
print is_win("++++"), '"++++"'
print
print is_win("-----"), '"-----"'
print is_win("------"), '"------"'
print is_win("-------"), '"-------"'
print
print is_win("--+----+--+---++--"), '"--+----+--+---++--"'

<pre>
True ""

True "-"
True "+"

False "--"
True "+-"
True "-+"
True "++"

True "----"
False "+---"
False "-+--"
False "--+-"
False "---+"
False "++--"
True "-++-"
False "--++"
True "-+-+"
True "+-+-"
False "+--+"
True "+++-"
True "-+++"
True "++++"

True "-----"
True "------"
False "-------"

True "--+----+--+---++--"
</pre>