Ресурсы: Object.values() Array.isArray() Статья про рекурсию
Рекурсия - это приём, когда функция вызывает сама себя.
Рассмотрим на классическом примере функции возведения в степень. Логика следующая: есть база (2) и второй аргумент, показывающий сколько раз нужно при умножении повторить базовое число:
Код
pow(2, 1); // 2
pow(2, 2); // 4
pow(2, 3); // 8
pow(2, 4); // 16
Чтобы написать функцию возведения в степень, есть два варианта.
Первый вариант: Код
function pow(x, n) {
let result = 1; // не 0 потому что иначе все время будет 0 при умножении
for (let i = 0; i < n; i++) {
result *= x;
}
return result;
}
Логика работы функции здесь такова:
Цитата
// 2, 0
0 < 0 => false => return result = 1
// 2, 1
i = 0; 0 < 1 => true => return result = 1 * 2 = 2
// 2, 2
i = 0; 0 < 2 => true => result = 1 * 2 = 2
i = 1; 1 < 2 => true => return result = 2 * 2 = 4
// 2, 3
i = 0; 0 < 3 => true => result = 1 * 2 = 2
i = 1; 1 < 3 => true => result = 2 * 2 = 4
i = 2; 2 < 3 => true => return result = 4 * 2 = 8
Что значит возвести число в степень
n?
Возвести число
x в степень
n – значит найти произведение
n множителей, каждый из которых равен
x.
Код
function pow(x, n) {
if (n === 1) {
return x;
} else {
return x * pow(x, n - 1);
}
}
Функция принимает два аргумента: x = 2, n = 3, и, так как n не равен 1, срабатывает альтернативное условие
Код
function pow(2, 3) {
return 2 * pow(2, 3 - 1);
}
Внутри функции происходит вызов функцией самой себя, но уже с параметрами x = 2, n = 2
Код
function pow(2, 2) {
return 2 * pow(2, 2 - 1);
}
Теперь внутри этой функции также происходит вызов функцией самой себя, с параметрами x = 2, n = 1. Так как n = 1, то срабатывает основное условие и возвращается x = 2
Код
function pow(2, 1) {
return 2;
}
Мы добрались до базы рекурсии, знаем результат её вычисления, это цифра 2, она возвращается и подставляется в вызове функции с параметрами (2, 2)
Код
function pow(2, 2) {
return 2 * 2; // 4
}
Число 4, как результат работы этой функции, возвращается и подставляется в вызове функции с параметрами (2, 3)
Код
function pow(2, 3) {
return 2 * 4; // 8
}
Таким образом, функция, вызываемая с параметрами (2, 3), возвращает число 8.
База рекурсии - случай, приводящий сразу к завершению работы функции. В примере выше базой рекурсии будет 1.
Шаг рекурсии - запуск вложенной функции, но уже с другим значением. В примере выше шаг рекурсии это n - 1
Глубина рекурсии - это общее количество вложенных вызовов вместе с самым первым. В примере выше это n (максимальная глубина рекурсии может быть в районе 10 000)
При решении подобных задач вариант с перебором с помощью цикла предпочтительнее, но большинство программистов выбирают рекурсию.
Попробуем понять почему на примере. Есть такой объект со студентами и стоит задача посчитать общий прогресс студентов со всех доступных курсов:
Код
let students = {
js: [{
name: 'John',
progress: 100
}, {
name: 'Ivan',
progress: 60
}],
html: {
basic: [{
name: 'Peter',
progress: 20
}, {
name: 'Ann',
progress: 18
}],
pro: [{
name: 'Sam',
progress: 10
}]
}
};
Задачу можно решить как с использованием цикла, так и рекурсией.
Решение задачи можно разбить на этапы:
1. Выяснить общее число студентов
2. Узнать общее число прогресса в процентах
3. Общее число прогресса разделить на количество студентов
Решение задачи с использованием цикла
Создадим функцию, в которую как аргумент будут приходить какие-то данные:
Код
function getTotalProgressByIteration(data) {
let total = 0; // общий прогресс
let studentsTotal = 0; // общее кличество студентов
return total / studentsTotal;
}
console.log(getTotalProgressByIteration(students));
Цитата
У объектов есть метод
Object.values(), возвращающий массив значений перечисляемых свойств объекта.
Пример:
Код
const obj = {
a: 'something',
b: 42,
c: false
};
console.log(Object.values(obj)); // [ 'something', 42, false ]
Внутри нашей функции мы задаём цикл, объявляем внутри него переменную, назовём её
course Код
function getTotalProgressByIteration(data) {
let total = 0; // общий прогресс
let studentsTotal = 0; // общее кличество студентов
for (let course of Object.values(data)) {
}
return total / studentsTotal;
}
нам вернёт, таким образом, массив, состоящий из значений свойств объекта
students, то есть получим такой массив, первый элемент которого также массив, а второй элемент это объект:
Код
[
[{
name: 'John',
progress: 100
}, {
name: 'Ivan',
progress: 60
}],
{
basic: [{
name: 'Peter',
progress: 20
}, {
name: 'Ann',
progress: 18
}],
pro: [{
name: 'Sam',
progress: 10
}]
}
]
И в нашем цикле в переменную
course будут поочередно попадать эти два элемента.
И мы получаем развилку, элемент, попадающий в
course, будет либо массивом, либо чем-то еще, в данном случае, объектом.
Соответственно, нам нужно прописать условие, проверяющее тип элемента, который попадает в переменную
course Цитата
Метод
Array.isArray() возвращает
true, если объект является массивом и
false, если он таковым не является.
Синтаксис:
Проверяем, является ли элемент массивом:
Код
function getTotalProgressByIteration(data) {
let total = 0; // общий прогресс
let studentsTotal = 0; // общее кличество студентов
for (let course of Object.values(data)) {
if (Array.isArray(course)) {
}
}
return total / studentsTotal;
}
Если условие истинное (элемент является массивом), то:
1. считаем, сколько в этом массиве студентов
2. складываем значения всех свойств
progress Первый пункт реализовать легко, поскольку в массиве содержатся два объекта, каждый из которых описывает одного студента.
Соответственно, взяв длину массива, мы узнаем число студентов в нем. Прибавляем его в переменную
studentsTotal Код
function getTotalProgressByIteration(data) {
let total = 0; // общий прогресс
let studentsTotal = 0; // общее кличество студентов
for (let course of Object.values(data)) {
if (Array.isArray(course)) {
studentsTotal += course.length;
}
}
return total / studentsTotal;
}
Для второго пункта используем цикл, в котором для каждого из объектов, входящих в массив из переменной
course, мы обращаемся к его свойству
progress и полученное его значение прибавляем в
total:
Код
function getTotalProgressByIteration(data) {
let total = 0; // общий прогресс
let studentsTotal = 0; // общее кличество студентов
for (let course of Object.values(data)) {
if (Array.isArray(course)) {
studentsTotal += course.length;
for (let i = 0; i < course.length; i++) {
total += course[i].progress;
}
}
}
return total / studentsTotal;
}
Если же в переменную
course попадает не массив, а что-то другое, в нашем случае это объект, то мы опять с помощью
Object.values() получаем доступ к значениям его свойств, а это также два массива.
Пишем перебор массива с помощью
for/of, как мы это делали ранее
Код
function getTotalProgressByIteration(data) {
let total = 0; // общий прогресс
let studentsTotal = 0; // общее кличество студентов
for (let course of Object.values(data)) {
if (Array.isArray(course)) {
studentsTotal += course.length;
for (let i = 0; i < course.length; i++) {
total += course[i].progress;
}
} else {
for (let subCourse of Object.values(course)) {
studentsTotal += subCourse.length;
for (let j = 0; j < subCourse.length; j++) {
total += subCourse[j].progress;
}
}
}
}
return total / studentsTotal;
}
В результате получаем 41.6 средний прогресс студентов по всем доступным курсам.
Решение с использованием рекурсии Напишем теперь новую функцию, в которой будем использовать рекурсию:
Код
function getTotalProgressByRecursion(data) {
}
Для начала нужно определиться с базовыми понятиями рекурсии, базой рекурсии у нас будет массив, поскольку как только мы натыкаемся на массив, происходят вычисления количества студентов и их прогресс.
Код
function getTotalProgressByRecursion(data) {
if (Array.isArray(data)) {
let total = 0;
for (let i = 0; i < data.length; i++) {
total += data[i].progress;
}
return [total, data.length]; // так как нам нужно 2 значения, используем массив
} else {
let total = [0, 0];
for (let subData of Object.values(data)) {
const subDataArr = getTotalProgressByRecursion(subData);
total[0] += subDataArr[0];
total[1] += subDataArr[1];
}
return total;
}
}
const result = getTotalProgressByRecursion(students);
console.log(result[0] / result[1]);
Итак, что здесь происходит:
1. Базовым случаем рекурсии у нас будет, как мы решили, массив, поэтому, когда функция наталкивается на массив, происходит его перебор и вычисляется суммарный прогресс студентов из этого массива.
Число студентов при этом - это длина массива, поскольку каждый его элемент описывает одного студента.
В результате возвращается массив с данными типа
[суммарный прогресс, число студентов].
2. Если же функция наталкивается на объект, то:
- с помощью метода
Object.values() получает значения свойств объекта в виде массива
- Запускается перебор для этого массива, в котором каждый элемент этого массива (а им может быть и объект, и также массив) попадает в переменную
subData - Теперь функция вызывает сама себя, принимая в качестве аргумента переменную
subData и результат вызова сохраняется в переменную
subDataArr - При этом, если в
subData попадает массив, то происходит его перебор и вычисляется суммарный прогресс студентов из этого массива, и в переменную
subDataArr сохраняется массив с данными типа
[суммарный прогресс, число студентов] - Если же в
subData попадает объект, то функция опять вызовет саму себя и так до тех пор, пока функция не дойдёт до массива.
- Новые значения элементов массива в переменной
total получаются прибавлением значений элементов массива из переменной
subDataArr Благодаря рекурсии, функция будет работать с любым уровнем вложенности.
Добавлять комментарии могут только зарегистрированные пользователи.
