遞歸沒有超過

Question

我一直在尋找遞歸的真實世界的例子。請記住，編程嚮導，我和藝術家，並在Photoshop腳本（腳本模式操作）它通常用於循環所有圖層和子圖層。

我正在處理（簡單）遞歸腳本來解決四位數組合鎖。你知道，從1開始，然後嘗試2，然後3等，直到找到解決方案。爲了讓事情變得簡單，第二個數字是正確的，所以我們知道我們不需要改變它。初始狀態的數字從零開始，但我們知道最終解決方案中沒有零。

• 該嘗試必須匹配的解決方案，也加起來10以便 被解決。

這看起來似乎有點不穩定，但我想把解決方案的兩個部分放在一起，主要是因爲我可以應用我學到的東西並編寫一個蠻力suduko求解器。但是，你必須爬之前，你可以滑冰...

var puzzle = [0,2,0,0]; // source 
var solution = [1,2,3,4]; 
var s = superCopy(puzzle); // working array 


drawPuzzle(s); 
solvePuzzle(s, puzzle); 

var total = checkTotal(s, solution); 
var solution = checkSolution(s, solution); 


function checkTotal(arr, source) 
{ 
    var c = 0; 

    // count the total 
    for (var i = 0; i < arr.length; i++) 
    { 
    c += arr[i]; 
    } 
    if (c == 10) 
    { 
    alert("Total OK") 
    return true; 
    } 
} 

function checkSolution(arr, source) 
{ 
    // check the solution 
    for (var i in arr) 
    { 
    if (arr[i] != source[i]) return false 
    return true; 
    } 
} 

function solvePuzzle(arr, source) 
{ 
    for (var i = 0; i < arr.length; i++) 
    { 
    // check the source 
    var sourceCell = source[i]; 
    //alert("checking source " + sourceCell) 
    //if it's a zero we can change it 
    if (arr[i] == 0) 
    { 
     cell = arr[i]; 

     cell+=1; 
     if (cell > 4) cell = 0; 
     arr[i] = cell; 
    } 
    } 

    // check the solution 
    for (var i in arr) 
    { 
    // overflow time! 
    if (arr[i] != source[i]) solvePuzzle(arr, source) 
    else 
    { 
     alert("All done!") 
    } 
    } 
} 

function drawPuzzle(arr) 
{ 
    var p = ""; 
    var c = 0; 
    for (var i = 0; i < arr.length; i++) 
    { 
    if (arr[i] == 0) p += "-" 
    else p += arr[i]; 
    c+=1; 
    } 
    alert(p); 
} 

function superCopy(arr) 
{ 
    // returns a true copy of an array 
    tempArr = new Array(); 
    for (var i = 0; i < arr.length; i++) 
    { 
    if (arr[i] == 0) tempArr[i] = 1 // changed, thanks Nostradamnit! 
    else tempArr[i] = arr[i] 
    } 
    return tempArr 
} 

的腳本是不完整的。這是我迄今爲止，它溢出錯誤。注意solvePuzzle和checkTotal函數沒有被調用，因爲我意識到solvePuzzle需要調用它自己並找出解決方案......當我遇到溢出問題並且有點困惑時。

我意識到這種類型的問題危險地靠近「修復我的代碼」冒險，所以我準備爲它付出恩典。謝謝。

Answer 1

乍一看，你的超複製功能似乎有缺陷。您創建一個空數組，然後將其索引0（不存在）與輸入數組進行比較。那是你在哪裏得到你的「溢出」？

Answer 2

的問題似乎是，你調用在同一個迭代solvePuzzle(arr, source)多次：

for (var i in arr) 
    { 
    // overflow time! 
    if (arr[i] != source[i]) solvePuzzle(arr, source) 
    else 
    { 
     alert("All done!") 
    } 
    } 

所以你遍歷數組中的每個項目，如果它不等於source項目，你打電話再次請求solvePuzzle。但是如果你有幾個不匹配的項目，solvePuzzle將在同一個數組上被多次調用。並且對於每次呼叫，它都會被多次調用。因此你的函數調用會以指數方式增長，並最終導致堆棧溢出。

什麼你可能打算這樣做，是這樣的：

var areArraysEqual = true; 
    for (var i in arr) 
    { 
    if (arr[i] != source[i]) { 
     areArraysEqual = false; 
     break; 
    } 
    } 

    if (areArraysEqual) { 
     alert("All done!"); 
    } else { 
     solvePuzzle(arr, source); 
    } 

Answer 3

我還沒看過了你的解決辦法，但我的確寫了一個遞歸一個爲自己解決問題。也許它可以作爲指導的幫助？

var solution = [1,2,3,4]; 

function checkSolution(arr) { 
    return solution.every(function(item, index){ return item === arr[index]; }); 
} 

function increment(arr) { 
    for (var i=0; arr[i] === 9; i++) { 
    arr[i] = 0; 
    } 
    arr[i]++; 
    return arr; 
} 

function solvePuzzle(arr) { 
    if (isNaN(arr[arr.length-1])) { 
     return null; 
    } 
    if (checkSolution(arr)) { 
    return arr; 
    } 

    return solvePuzzle(increment(arr)); 
} 



var solution = solvePuzzle([1,1,1,1]); 
console.log(solution); // [1,2,3,4] 

Answer 4

您的代碼有幾個問題。首先，你的checkSolution函數停在第一個匹配的數字上。您可能希望它在返回true之前檢查每個數字，因此您應該將return true移至for循環之外。如果所有數字匹配，它只會到達那裏。

另一個缺陷是超級拷貝功能，正如Nostradamnit指出的那樣，有一個缺陷。

你的下一個問題是solvePuzzle，你有這樣的：

if (arr[i] == 0) 
{ 
    cell = arr[i]; 

    cell+=1; 
    if (cell > 4) cell = 0; 
    arr[i] = cell; 
} 

的事情是，因爲arr[i]是0，你只加1，電池將永遠4.所以，你如果是永遠不會火。這是你的無限循環的地方：它只增加一個爲零的值，因此，在所有零成爲一個零後，它永遠不會進一步發展，並且不斷檢查「1111」是否是解決方案。

現在溢出：你不應該叫solvePuzzle的每一個細胞，這種呈指數級增長：

for (var i in arr) 
{ 
    // overflow time! 
    if (arr[i] != source[i]) solvePuzzle(arr, source) 
    else 
    { 
    alert("All done!") 
    } 
} 

而且，你永遠不會再次檢查的結果，所以在循環永遠不會結束。你可能會想這個改成這樣：

if(checkTotal(arr) && checkSolution(arr, source)) 
{ 
    alert("All done!"); 
    return; 
} 
solvePuzzle(arr, source); 

作爲一個側面說明（不是一個錯誤造成的東西）：你的checkTotal功能不使用源參數，所以你可能會保留這一點。另外，在solvePuzzle中有一個叫做cell的流氓變量，在這種情況下這不是什麼大問題，但最好把var放在它的前面，這樣它就不會變成全局的。此外，還有一個永遠不會被使用的sourceCell變量。

Answer 5

也許有點題外話，但我已經創建了我認爲最簡單的遞歸示例。

http://jsfiddle.net/33yfS/

var str = "9785"; 
function rec(a, b) 
{ 
    var c=0; 
    if(b==-1) 
     return ""; 
     if(a!=str.charAt(b)) 
      return rec(a+1, b); 
     else 
     { 
      return rec(0,b-1)+""+a; 
     } 
} 
var ans = rec(0,str.length-1)