Javascript recursion with array

Question

I was following the Eloquent Javascript book and making the linked list exercise. I am stuck with recursion. I use the following code:

function arrayToList(array){
    var list = {};
    length = array.length;
    while(array.length > 0){
        element = array.pop();
        if (length == array.length + 1 )
            list = { value: element, rest: null};
        else
            list = { value: element, rest: list};
    }
    return list;

}

function nth(list , number){
    array = [];
    if (list.rest != null && number !=0 ) {
        number--;
        array.push(list.value);
        nth(list.rest, number);
    }
    answer = list.value
    array.push(list.value);
    return array[0];
}

example_list = arrayToList([1,2,3,4]);
a = nth(example_list, 3);
console.log(a);

My question now is how the recursion exactly works for the "nth()" function.

I wrote this myself but I can only to get it working when using the array[0] way and I was expecting to be able to just use list.value as the return value. When debugging I see that it goes to the correct value(4), but then it comes back to the first value (1).

So my questions is can this be done, not using an array? It feels like an array is not the correct way and I only want to get the correct value? If any other mistakes in the code gladly get advice about the style as well.

Answer 1

This implementation of nth should be what you are looking for:

function nth(list, number){
    if (list.rest != null && number !=0 ) {
        number--;
        return nth(list.rest, number);
    }
    return list.value;
}

When the recursion "termination condition" is reached i.e. that the list rest element is null and that number === 0 it returns the list.value. Otherwise, it recurses into nth and returns its value instead.

Sometimes it can be clearer and simpler to understand the recursion if you invert the logic so that the termination condition is what is checked for explicitly. For example:

function nth(list, number){
    if (list.rest == null || number <= 0 ) {
        return list.value;
    }
    number--;
    return nth(list.rest, number);
}

In addition, having the recursive call as the last line in the block also makes it clear to the programmer that this function is eligible for "tail-call optimization" by a clever runtime. That optimization allows a runtime to convert the recursion (which is relatively slow because it requires adding stack frames on each recursion) into a loop (which requires no additional stack frames). See What is tail recursion?. In this case the original method can also be optimized (since no operation is done on the result of the recursive call), its just not as clear.