Выбор ответа Middle Сложность обновлено
Память рекурсии
Вопрос
Какая дополнительная память у рекурсивной суммы массива?
function sum(arr, i = 0) {
if (i === arr.length) return 0;
return arr[i] + sum(arr, i + 1);
}
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(n) на стек вызовов. Глубина рекурсии n, каждый кадр стека хранит i и адрес возврата: O(n) памяти.
Варианты ответа
- O(1), новых массивов не создаётся
- O(log n)
- O(n²), потому что каждый вызов хранит массив
- O(n) на стек вызововправильный ответ
Разбор
Глубина рекурсии n, каждый кадр стека хранит i и адрес возврата: O(n) памяти. Массив передаётся по ссылке, не копируется. На больших n (порядка десятков тысяч и выше, зависит от движка) это ещё и риск RangeError: Maximum call stack size exceeded.
- O(1): забыли про стек вызовов.
- O(log n): глубина не делится пополам.
- O(n²): ссылка на массив не копирует его.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.