Рекурсия Javascript с массивом

Question

Я следил за яркой книгой Javascript и делал упражнение связанного списка. Я застрял с рекурсией. Я использую следующий код:

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

Мой вопрос в том, как рекурсия точно работает для «п-го) (» функции.

Я написал это сам, но я могу только заставить его работать при использовании массива [0], и я ожидал, что смогу просто использовать list.value в качестве возвращаемого значения. При отладке я вижу, что он переходит к правильному значению (4), но затем возвращается к первому значению (1).

Так что мои вопросы можно это сделать, не использовать массив? Похоже, что массив неправильный, и я хочу только получить правильное значение? Если какие-либо ошибки в коде также получают советы по поводу стиля.

Answer 1

Эта реализация nth должно быть то, что вы ищете:

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

Когда рекурсия «условие завершения» достигается то, что элемент списка rest является недействительным и что number === 0 возвращает list.value. В противном случае он возвращается к nth и вместо этого возвращает его значение.

Иногда может быть яснее и проще понять рекурсию, если вы инвертируете логику, чтобы условие завершения было проверено явно. Например:

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

Кроме того, имея рекурсивный вызов в качестве последней строки в блоке также проясняет для программиста, что эта функция имеет право на «оптимизацию хвостового вызова» умным выполнением. Эта оптимизация позволяет среде выполнения преобразовывать рекурсию (которая относительно медленна, потому что требует добавления кадров стека на каждую рекурсию) в цикл (который не требует дополнительных кадров стека). См. What is tail recursion?. В этом случае исходный метод также может быть оптимизирован (поскольку операция не выполняется по результату рекурсивного вызова), его просто не так ясно.