堆栈片段中的代码应按如下方式工作：
propagateChanges相反，当我单击表格中最右上角的单元格时，算法似乎会产生正确的结果。地图（由 HTML 表格表示）在视觉上看起来是正确的，这意味着所有图块编号都解析为它们预期和打算具有的最终值。
但是，即使在地图出现
达到最终稳定的配置之后，递归调用仍然会在
for底部的
propagateChanges循环内生成。
应该防止算法创建“循环”，其中相邻图块在彼此之间来回生成递归调用。
那么，这里出了什么问题？显然，我一定错过了一个基本情况，因为无限递归正在发生，但多次查看代码后我仍然不明白它是什么。
const rows = document.getElementsByTagName('tr');
var tiles = [];
for (var r = 0; r < rows.length; r++) {
tiles[r] = [];
for (var c = 0; c < rows[r].cells.length; c++) {
// Store table cell's row and column indices, along with the cell itself, to simplify later accesses
tiles[r][c] = {
r: r,
c: c,
tile: rows[r].cells[c]
};
}
}
// Helper function: avoid out-of-bounds errors when accessing array elements by returning a table cell only if its indices exist in the 'tiles' array
function getTile(r, c) {
if (r > -1 && r < 4 && c > -1 && c < 5) {
return tiles[r][c];
}
}
// If the current tile is NOT within 4 steps of any centers (i.e. tiles numbered 0), increase its number by 1 until it reaches the maximum value of 4. Then do the same for each neighboring tile, after a 1-second delay.
// Eventually, after a *maximum* of 4 iterations, the grid should stabilize, meaning all numbers should have reached their final values.
// All tiles will either have value 4, or else be within 4 steps of a center tile (numbered 0), in which case their values will NOT increase.
function propagateChanges(currentTile, R, C, depth) {
var rDist = Math.abs(currentTile.r - R);
var cDist = Math.abs(currentTile.c - C);
if (depth > maxDepth) {
maxDepth = depth;
}
if (depth > 4) {
overflowed = true;
return;
} else if (rDist < 3 && cDist < 3 && (rDist + cDist < 3)) {
var val = Number(currentTile.tile.textContent);
// Somehow, this function got called on a tile with value <= 0 or >= 4. This shouldn't happen: exit without performing any recursive steps.
if (val >= 4 || val <= 0) {
return;
} else {
var centerCoords = isCenterWithin4Tiles(currentTile.r, currentTile.c);
const adjacents = [getTile(currentTile.r - 1, currentTile.c), getTile(currentTile.r + 1, currentTile.c), getTile(currentTile.r, currentTile.c - 1), getTile(currentTile.r, currentTile.c + 1)];
// Don't increase the tile's number value if there's a center nearby (i.e. within 4 steps)
if (!centerCoords) {
currentTile.tile.textContent = val + 1;
// Perform recursive call on original block after 1 second delay
setTimeout(function() {
propagateChanges(currentTile, R, C, depth + 1);
}, 1000);
}
// Recursive calls on the 4 adjacent tiles
// Only proceed in a given direction if either no nearby centers were found, or else the adjacent tile in that direction will be further from any/all centers than currentTile is (in either the row [r] or column [c] direction).
// Not being able to move back in the direction of a center is intended to prevent an infinite cycle of recursive calls from being generated.
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
let adjVal = Number(adjacents[i].tile.textContent);
if (adjVal < 4 && adjVal > 0 && (!centerCoords || isFurtherFromAll(adjacents[i], currentTile, centerCoords))) {
/* THIS IS WHERE THE PROBLEM OCCURS */
setTimeout(function() {
propagateChanges(adjacents[i], R, C, depth + 1);
}, 1000);
}
}
}
}
}
}
// Find the lowest numbered tile within 4 steps of the origin (i.e. the tile the user clicked), and invoke the propagateChanges function on it IF it is not a true center (which are numbered 0)
function locateCenter(currentTile, R, C, depth) {
if (depth > maxDepth) {
maxDepth = depth;
}
if (depth > 4) {
overflowed = true;
return;
} else {
const val = Number(currentTile.tile.textContent);
var rDist = Math.abs(currentTile.r - R);
var cDist = Math.abs(currentTile.c - C);
// If a center is encountered, do not continue. Don't check any tiles that are more than 4 steps away from the origin coordinates.
if (val > 0 && (rDist < 4 && cDist < 4 && (rDist + cDist < 4))) {
const adjacents = [getTile(currentTile.r - 1, currentTile.c), getTile(currentTile.r + 1, currentTile.c), getTile(currentTile.r, currentTile.c - 1), getTile(currentTile.r, currentTile.c + 1)];
var hasLowerNumberedNeighbor = false;
var adjVal;
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
adjVal = Number(adjacents[i].tile.textContent);
// Encountered a center within 4 steps of the origin: do not continue.
if (adjVal == 0) {
return;
}
// Encountered neighboring tile with value less than that of the current tile, and < 4: perform *instant* recursive step horizontally and update boolean.
// USE <, NOT <=, or else it will be an infinite cycle!
else if (adjVal < 4 && adjVal < val) {
hasLowerNumberedNeighbor = true;
locateCenter(adjacents[i], R, C, depth + 1);
}
}
}
// If no adjacent tile has a lower number, then currentTile must be cut off from all centers.
if (!hasLowerNumberedNeighbor) {
// The current tile should begin counting up to 4, and propagate changes outward to its neighbors
propagateChanges(currentTile, currentTile.r, currentTile.c, 0);
}
}
}
}
/* Return type of this function will vary. If any centers (tile value == 0) are located within the specified distance, it will return an array of objects containing their x and z coordinates.
(This evaluates to *true* in conditional statements.) Otherwise, it will return false. */
function isCenterWithin4Tiles(r, c) {
var coords = [];
for (var rAway = -3; rAway < 4; rAway++) {
for (var cAway = -3; cAway < 4; cAway++) {
if ((Math.abs(rAway) + Math.abs(cAway) < 4) && ((r + rAway) > -1 && (c + cAway) > -1 && (r + rAway) < 4 && (c + cAway) < 5)) {
const val = tiles[r + rAway][c + cAway].tile.textContent;
if (val == 0) {
coords.push({
r: r + rAway,
c: c + cAway
});
}
}
}
}
return (coords.length) ? coords : false;
}
// Returns true if the coordinates for 'next' are further from ALL centers (i.e., coordinate pairs in the 'comparisons' array) than are the coordinates for 'current', and false otherwise.
function isFurtherFromAll(next, current, comparisons) {
var compared = {};
for (var i = 0; i < comparisons.length; i++) {
// 'next' is further than 'current' from the center in a given direction: Value for that direction will be *positive*.
// 'next' and 'current' are an equal distance from the center: Value will be *0*.
// 'next' is closer to center than current: Value will be *negative*.
compared.r = Math.abs(next.r - comparisons[i].r) - Math.abs(current.r - comparisons[i].r);
compared.c = Math.abs(next.c - comparisons[i].c) - Math.abs(current.c - comparisons[i].c);
// If 'next' is closer than 'current' to the source *in either direction*, OR 'next' is *not* further than 'current' in *at least one* direction, return false
if ((compared.r < 0) || (compared.c < 0) || (compared.r + compared.c === 0)) {
return false;
}
}
return true;
}
// Limit max recursion depth to 4, as the function reaching a greater depth than this indicates the algorithm will never terminate
var maxDepth = 0;
var overflowed = false; // If this becomes true, the function will exit without generating further recursive calls.
function progressReport() {
console.log("Maximum depth reached in recursive function: " + maxDepth);
if (overflowed) {
console.warn("OVERFLOW");
} else {
setTimeout(progressReport, 3000); // Every 3 seconds
}
}
progressReport();
// When the tile in the top right corner is clicked, set its number to the max value (4) and invoke the incrementation algorithm on it
var clicked = false;
document.getElementById("clickHere").addEventListener('click', function() {
if (!clicked) {
clicked = true;
tiles[0][4].tile.textContent = 4;
locateCenter(tiles[0][4], 0, 4, 0);
}
});table {
font-size: 18px;
}
table {
td {
width: 20px;
height: 20px;
}
}<body>
<table>
<tr>
<td>2</td>
<td>2</td>
<td>2</td>
<td>1</td>
<td id="clickHere">0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>2</td>
<td>2</td>
<td>1</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>2</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>3</td>
</tr>
</table>
</body>
“在‘中心’图块的 4 个步骤内”有关。
似乎一旦到达一个图块，如果当前或相邻图块均不在任何“中心”（值 = 0）图块的 4 步内，则您只想对每个相邻图块执行递归调用。 这
必须是意图，因为您已经指定，如果图块位于“中心”的 4 个方块内，您不希望它们的数量减少，并且一旦确定不再进行进一步的更改给定图块的数值，没有理由在该图块上调用递归函数。 就目前情况而言，您的条件语句：
if (adjVal < 4 && adjVal > 0 && (!centerCoords || isFurtherFromAll(adjacents[i], currentTile, centerCoords))) {仅检查中心图块是否位于当前图块的4步之内，并且不检查“中心”与相邻图块的接近程度。 这意味着位于“中心”周围区域最边缘
的图块将距离中心 3 步，而下一个相邻图块将距离中心 4 步（导致isFurtherFromAll(adjacents[i], currentTile, centerCoords) 计算为 true
，因为 4 > 3)。因此，条件语句的值与您是否打算实际执行
adjacents[i]上的递归调用之间存在不匹配。递归应该不
实际发生，因为相邻的图块距任何/所有中心 4 步，但这从未被实际检查过！添加额外检查以检查相邻
图块是否位于任何中心的 4 步之内，从而解决了问题。 因此，循环内递归调用的条件语句实际上应该是：
if (adjVal < 4 && adjVal > 0 && ((!centerCoords || isFurtherFromAll(adjacents[i], currentTile, centerCoords)) && (!adjCenterCoords || isFurtherFromAll(adjacents[i], currentTile, adjCenterCoords)))) {
完整（工作）代码：
const rows = document.getElementsByTagName('tr');
var tiles = [];
for (var r = 0; r < rows.length; r++) {
tiles[r] = [];
for (var c = 0; c < rows[r].cells.length; c++) {
// Store table cell's row and column indices, along with the cell itself, to simplify later accesses
tiles[r][c] = {
r: r,
c: c,
tile: rows[r].cells[c]
};
}
}
// Helper function: avoid out-of-bounds errors when accessing array elements by returning a table cell only if its indices exist in the 'tiles' array
function getTile(r, c) {
if (r > -1 && r < 4 && c > -1 && c < 5) {
return tiles[r][c];
}
}
// If the current tile is NOT within 4 steps of any centers (i.e. tiles numbered 0), increase its number by 1 until it reaches the maximum value of 4. Then do the same for each neighboring tile, after a 1-second delay.
// Eventually, after a *maximum* of 4 iterations, the grid should stabilize, meaning all numbers should have reached their final values.
// All tiles will either have value 4, or else be within 4 steps of a center tile (numbered 0), in which case their values will NOT increase.
function propagateChanges(currentTile, R, C, depth) {
var rDist = Math.abs(currentTile.r - R);
var cDist = Math.abs(currentTile.c - C);
if (depth > maxDepth) {
maxDepth = depth;
}
if (depth > 4) {
overflowed = true;
return;
} else if (rDist < 3 && cDist < 3 && (rDist + cDist < 3)) {
var val = Number(currentTile.tile.textContent);
// Somehow, this function got called on a tile with value <= 0 or >= 4. This shouldn't happen: exit without performing any recursive steps.
if (val >= 4 || val <= 0) {
return;
} else {
var centerCoords = isCenterWithin4Tiles(currentTile.r, currentTile.c);
var adjCenterCoords; // Will be used to test whether each tile adjacent to the current one is near a center, inside the loop at the end of this function
const adjacents = [getTile(currentTile.r - 1, currentTile.c), getTile(currentTile.r + 1, currentTile.c), getTile(currentTile.r, currentTile.c - 1), getTile(currentTile.r, currentTile.c + 1)];
// Don't increase the tile's number value if there's a center nearby (i.e. within 4 steps)
if (!centerCoords) {
currentTile.tile.textContent = val + 1;
// Perform recursive call on original block after 1 second delay
setTimeout(function() {
propagateChanges(currentTile, R, C, depth + 1);
}, 1000);
}
// Recursive calls on the 4 adjacent tiles
// Only proceed in a given direction if either no nearby centers were found, or else the adjacent tile in that direction will be further from any/all centers than currentTile is (in either the row [r] or column [c] direction).
// Not being able to move back in the direction of a center is intended to prevent an infinite cycle of recursive calls from being generated.
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
let adjVal = Number(adjacents[i].tile.textContent);
adjCenterCoords = isCenterWithin4Tiles(adjacents[i].r, adjacents[i].c);
// This time, ensure the adjacent tile is further NOT ONLY from any center tiles near *currentTile*, BUT ALSO from any centers near *itself*!
if (adjVal < 4 && adjVal > 0 && ((!centerCoords || isFurtherFromAll(adjacents[i], currentTile, centerCoords)) && (!adjCenterCoords || isFurtherFromAll(adjacents[i], currentTile, adjCenterCoords)))) {
/* WITH THE EXTRA CONDITION, THIS WILL NO LONGER GENERATE INFINITE BACK-AND-FORTH CYCLES BETWEEN ADJACENT TILES */
setTimeout(function() {
propagateChanges(adjacents[i], R, C, depth + 1);
}, 1000);
}
}
}
}
}
}
// Find the lowest numbered tile within 4 steps of the origin (i.e. the tile the user clicked), and invoke the propagateChanges function on it IF it is not a true center (which are numbered 0)
function locateCenter(currentTile, R, C, depth) {
if (depth > maxDepth) {
maxDepth = depth;
}
if (depth > 4) {
overflowed = true;
return;
} else {
const val = Number(currentTile.tile.textContent);
var rDist = Math.abs(currentTile.r - R);
var cDist = Math.abs(currentTile.c - C);
// If a center is encountered, do not continue. Don't check any tiles that are more than 4 steps away from the origin coordinates.
if (val > 0 && (rDist < 4 && cDist < 4 && (rDist + cDist < 4))) {
const adjacents = [getTile(currentTile.r - 1, currentTile.c), getTile(currentTile.r + 1, currentTile.c), getTile(currentTile.r, currentTile.c - 1), getTile(currentTile.r, currentTile.c + 1)];
var hasLowerNumberedNeighbor = false;
var adjVal;
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
adjVal = Number(adjacents[i].tile.textContent);
// Encountered a center within 4 steps of the origin: do not continue.
if (adjVal == 0) {
return;
}
// Encountered neighboring tile with value less than that of the current tile, and < 4: perform *instant* recursive step horizontally and update boolean.
// USE <, NOT <=, or else it will be an infinite cycle!
else if (adjVal < 4 && adjVal < val) {
hasLowerNumberedNeighbor = true;
locateCenter(adjacents[i], R, C, depth + 1);
}
}
}
// If no adjacent tile has a lower number, then currentTile must be cut off from all centers.
if (!hasLowerNumberedNeighbor) {
// The current tile should begin counting up to 4, and propagate changes outward to its neighbors
propagateChanges(currentTile, currentTile.r, currentTile.c, 0);
}
}
}
}
/* Return type of this function will vary. If any centers (tile value == 0) are located within the specified distance, it will return an array of objects containing their x and z coordinates.
(This evaluates to *true* in conditional statements.) Otherwise, it will return false. */
function isCenterWithin4Tiles(r, c) {
var coords = [];
for (var rAway = -3; rAway < 4; rAway++) {
for (var cAway = -3; cAway < 4; cAway++) {
if ((Math.abs(rAway) + Math.abs(cAway) < 4) && ((r + rAway) > -1 && (c + cAway) > -1 && (r + rAway) < 4 && (c + cAway) < 5)) {
const val = tiles[r + rAway][c + cAway].tile.textContent;
if (val == 0) {
coords.push({
r: r + rAway,
c: c + cAway
});
}
}
}
}
return (coords.length) ? coords : false;
}
// Returns true if the coordinates for 'next' are further from ALL centers (i.e., coordinate pairs in the 'comparisons' array) than are the coordinates for 'current', and false otherwise.
function isFurtherFromAll(next, current, comparisons) {
var compared = {};
for (var i = 0; i < comparisons.length; i++) {
// 'next' is further than 'current' from the center in a given direction: Value for that direction will be *positive*.
// 'next' and 'current' are an equal distance from the center: Value will be *0*.
// 'next' is closer to center than current: Value will be *negative*.
compared.r = Math.abs(next.r - comparisons[i].r) - Math.abs(current.r - comparisons[i].r);
compared.c = Math.abs(next.c - comparisons[i].c) - Math.abs(current.c - comparisons[i].c);
// If 'next' is closer than 'current' to the source *in either direction*, OR 'next' is *not* further than 'current' in *at least one* direction, return false
if ((compared.r < 0) || (compared.c < 0) || (compared.r + compared.c === 0)) {
return false;
}
}
return true;
}
// Limit max recursion depth to 4, as the function reaching a greater depth than this indicates the algorithm will never terminate
var maxDepth = 0;
var overflowed = false; // If this becomes true, the function will exit without generating further recursive calls.
function progressReport() {
console.log("Maximum depth reached in recursive function: " + maxDepth);
if (overflowed) {
console.warn("OVERFLOW");
} else {
setTimeout(progressReport, 3000); // Every 3 seconds
}
}
progressReport();
// When the tile in the top right corner is clicked, set its number to the max value (4) and invoke the incrementation algorithm on it
var clicked = false;
document.getElementById("clickHere").addEventListener('click', function() {
if (!clicked) {
clicked = true;
tiles[0][4].tile.textContent = 4;
locateCenter(tiles[0][4], 0, 4, 0);
}
});table {
font-size: 18px;
}
table {
td {
width: 20px;
height: 20px;
}
}<body>
<table>
<tr>
<td>2</td>
<td>2</td>
<td>2</td>
<td>1</td>
<td id="clickHere">0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>2</td>
<td>2</td>
<td>1</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>2</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>3</td>
</tr>
</table>
</body>