CODEWITHSUNDEEP
javascriptrecursion
Ghoul Fool
Ghoul Fool

Reputation: 6949

Recursion without overun

I've been looking for real world examples of recursion. Remember, programming Wizards, I'm and artist and in Photoshop scripting (scriptus modus operandi) it's normally used to loop over all layers and sub layers.

I'm working on a (simple) recursion script to solve a four digit combination lock. You know, start with 1, then try 2, then 3 etc until the solution is found. To make things easy in the example the second digit is correct so we know that we don't have to change that. Also the initial state the numbers start zero, but we know there are no zeroes in the final solution.

This may seem a bit stoppid, but I want to put in a two part condition of the solution, mainly because I can then apply what I've learned and write a brute force suduko solver. But you must crawl before you can ice skate...

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
}

The script is incomplete. This what I have so far, it falls over with an overflow error. Note solvePuzzle and checkTotal functions are not called because I realised that solvePuzzle needs to call itself and work out the solution...which is when I ran into overflow problems and got a bit confused.

I realise that this type of question runs dangerously close to a "fix my code" venture, so I'm prepared to put a bounty out for it. Thanks.

Upvotes: 3

Views: 106

Answers (5)

Dharman
Dharman

Reputation: 33238

Maybe little bit off topic but I have created the easiest recursion example possible in my opinion.

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)

Upvotes: 0

gpgekko
gpgekko

Reputation: 3606

There are a couple of problems with your code. First up, your checkSolution function stops at the very first number that matches. You probably want it to check every number before returning true, so you should move return true outside the for loop. It only gets there if all numbers match up.

Another flaw is the superCopy function, which as Nostradamnit pointed out has a flawed condition.

Your next problem is in solvePuzzle, where you have this: 

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

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

The thing is, because arr[i] is 0 and you only add 1, cell will never be 4. So your if is never going to fire. This is where your infinite loop is: it only increments values that are zero with one, so after all zeros became one, it never goes further and you keep checking if "1111" is the solution.

Now the overflow: you shouldn't be calling solvePuzzle for every cell, this grows exponentially:

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

Also, you never check the result again, so the looping never ends. You would probably want to change this to this:

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

As a side note (not a bug causing thing): your checkTotal function isn't using the source parameter, so you can probably leave that out. Also, there is a rogue variable called cell in solvePuzzle, which isn't a big deal in this case, but it would be better to put var in front of it so it doesn't become global. Also, there is a sourceCell variable that never gets used.

Upvotes: 1

Tibos
Tibos

Reputation: 27823

I haven't looked over your solution yet, but i did write a recursive one for myself to solve the problem. Perhaps it can be of help as a guideline?

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]

Upvotes: 0

basilikum
basilikum

Reputation: 10528

The problem seems to be that you call solvePuzzle(arr, source) multiple times in the same iteration:

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

So you iterate over every item in the array, and if it is not equal to the source item, you call solvePuzzle again. But if you have several items that don't match, solvePuzzle will get called multiple times on the same array. And for each call, it gets called again multiple times. Therefore your function calls grow exponentially and result finally in a stack overflow.

What you probably intended to do, is the following:

  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);
  }

Upvotes: 0

Nostradamnit
Nostradamnit

Reputation: 860

At first glance, it seems that your superCopy function is flawed. You create an empty array, then compare its 0 index (which doesn't exist) to the input array. Is that where you are getting your "overflow"?

Upvotes: 0

Related Questions