Debugging JS Recursion?

Question

I'm trying to learn recursion on my own and have come across an exercise that asks: " Write a recursive function that determines whether an array is a palindrome, where the array and its size are given as parameters. Returns 1 if a[] is a palindrome, 0 otherwise."

I've tried a lot of things, but my code is still not working. I am accessing the console.log check in the last section of code, but the x, y, and stepsLeft variables do not appear to update. (WARNING:)The code is, therefore, an unclosed loop and either the maximum call stack size is exceeded or the code recurses infinitely. Help in fixing it?

function isPalindrome(arr, size) {
    var stepsLeft;
    var x;
    var y;
    // initialize variables that will change in subsequent calls
    if (stepsLeft === undefined) {
        var hold = size / 2;
        stepsLeft = Math.floor(hold);
        x = 0;
        y = size - 1;
    }

    logged = console.log(stepsLeft);

    //base case: if you go through all steps towards the center and     everything matches, return true
    if (stepsLeft === 0) {
        return 1;
    }

    //recursion cases
    if (arr[x] !== arr[y]) {
        // if the x and y EVER don't match, return false. 
        return 0;
    }

    //increase the x and decrease the y, and check again
    x++;
    y--;
    stepsLeft--;
    console.log("here");
    return isPalindrome(arr, size);
}

Answer 1

I was trying to debug recursion is JavaScript as well and thought this might help anyone who's still struggling with a debugging method.

Task: I have a target integer s, 7 and I need to sum the vertex values from root to leaf path where the total equals to the target.

Basically, given a simple binary tree input:

t = {
    "value": 4,
    "left": {
        "value": 1,
        "left": {
            "value": -2,
            "left": null,
            "right": {
                "value": 3,
                "left": null,
                "right": null
            }
        },
        "right": null
    },
    "right": {
        "value": 3,
        "left": {
            "value": 1,
            "left": null,
            "right": null
        },
        "right": {
            "value": 2,
            "left": {
                "value": -2,
                "left": null,
                "right": null
            },
            "right": {
                "value": -3,
                "left": null,
                "right": null
            }
        }
    }
}

Which, the tree looks like:

      4
     / \
    1   3
   /   / \
  -2  1   2
    \    / \
     3  -2 -3

So, in our case the answer would be: Path 4 -> 3 -> 2 -> -2 which gives us 7.

My function:

function solution(t, s, depth = 0, direction = 'root: ') {
    if (t === null) {
        return false
    }
    
    if (isLeaf(t)) {
        console.log("-----------------")
        print(direction, t.value, " in ", depth)
        console.log("=================")
    } else {
        print(direction, t.value, " in ", depth)
    }
    
    s -= t.value;
    
    if (s == 0 && isLeaf(t)) {
        return true
    }
    
    let left = solution(t.left, s, depth + 1, direction = "left-child: ");
    let right = solution(t.right, s, depth + 1, direction = "right-child: ");
    console.log("-> node " + t.value + " has been visited.")
    return left || right
}

Then, if there's a solution return true, otherwise false.

Try to read the console logs and understand it. Shouldn't be too complex.

Answer 2

You may achieve it much more simply.

Begin thinking to the smallest possible arr, then growing its length:

1. we know that any 1-item array is a palindrome, so we can already retain that size == 1 >> 1
2. beyond that first case, it doesn't matter arr have odd or even length, so we can also notice that for 2 or 3 items then arr[0] === arr[size - 1] >> 1
3. combining the two previous rules, for an arr of at most 3 items we could simply write return (size == 1 || arr[0] == arr[size - 1]) ? 1 : 0;
4. now that we are sure for these reduced lengths, if we increase length by 2 (adding an item at both begin and end of arr) we observe that the rule #2 keeps applying for the newly added first and last items

So can now use recursion, like this:

isPalindrome = function(arr, size) {
  return size > 3 ? isPalindrome(arr.slice(1, -1), size - 2) :
    (size == 1 || arr[0] == arr[size - 1]) ? 1 :
      0
}

Last point, we observe that the above function doesn't care yet about the first and last items, as soon as there are more than 3 items. We must look at them and immediately return 0 it these extreme items don't match, so it becomes:

isPalindrome = function(arr, size) {
  return arr[0] != arr[size - 1] ? 0 :
    size > 3 ? isPalindrome(arr.slice(1, -1), size - 2) :
      (size == 1 || arr[0] == arr[size - 1]) ? 1 :
        0
}