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

The parameters (arr, size) passed in to isPalindrome never actually change, so each time isPalindrome is called, it runs exactly the same way. For the recursion to work, you'll want to solve part of the problem and then call isPalindrome with the smaller remaining problem. — forrert
– forrert, Commented Dec 10, 2015 at 18:42

Dharman · Accepted Answer · 2022-01-11 02:35:39Z

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:

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.

cFreed · Accepted Answer · 2015-12-11 10:55:27Z

You may achieve it much more simply.

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

we know that any 1-item array is a palindrome, so we can already retain that size == 1 >> 1
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
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;
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
}

Collectives™ on Stack Overflow

Debugging JS Recursion?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related