Рекурсия - приём, когда функция вызывает саму себя.
Разберём на примере функции возведения в степень.
Логика функции должна быть следующей: при её вызове передаются два аргумента, первый из них само число, а второй - степень, в которую возводится это число.
То есть, при вызове функции должно получаться следующее:
Цитата
pow(2, 2); // 4
pow(2, 3); // 8
pow(2, 4); // 16
Собственно, сама функция:
Код
function pow (x, n) {
let result = 1;
for (let i = 0; i < n; i++) {
result *= x;
}
console.log(result);
}
Начальное значение для
result поставили равным 1, для того, чтобы функция правильно отработала в случае, если при вызове функции второй аргумент (
n) будет равным нулю. Ведь любое число в нулевой степени даёт 1. И у нас вернётся единица, так как цикл не сработает, то просто выведется в консоль начальное содержимое
result, то есть 1.
Цитата
pow(2, 0); // 1
pow(2, 1); // 2
pow(2, 2); // 4
pow(2, 3); // 8
pow(2, 4); // 16
Альтернативным вариантом циклу может быть решение, когда внутри функции запускать эту же функцию (рекурсия).
Код
function pow(x, n) {
if (n === 1) {
return x;
} else {
return x * pow(x, n - 1);
}
};
Разберём для вызова функции с параметрами (2, 4)
Вызываем функцию
pow Получаем на выходе:
Код
return 2 * pow(2, 4 - 1);
Или, после вычитания в скобках:
Здесь запускается таже функция
pow, но внутри себя, с параметрами (2, 3), получаем на выходе:
Код
return 2 * pow(2, 3 - 1);
Или, после вычитания в скобках:
Опять запускается функция
pow, уже внутри этой функции и с параметрами (2, 2), получаем:
Код
return 2 * pow(2, 2 - 1);
Или, после вычитания в скобках:
И это уже
база рекурсии - любое число в первой степени будет самим этим числом, поэтому теперь идём в обратную сторону:
2 умножаем на результат вызова функции
pow(2, 1) получаем 2 * 2 = 4
2 умножаем на результат вызова функции
pow(2, 2) получаем 2 * 4 = 8
2 умножаем на результат вызова функции
pow(2, 3) получаем 2 * 8 = 16
Код
return 2 * pow(2, 3); // => вернёт 2 * 8 = 16
return 2 * pow(2, 2); // => вернёт 2 * 4 = 8
return 2 * pow(2, 1); // => вернёт 2 * 2 = 4
- это случай, который сразу приводит к завершению функции. В примере выше база рекурсии этот вариант вызова при
n === 1, потому что в этом случае сразу возвращается число
x.
Шаг рекурсии - это запуск вложенной функции, но уже с другим значением. В нашем случае это
n - 1 Глубина рекурсии - это общее количество вложенных вызовов включая самый первый. У нас она равна числу
n Решать задачу через рекурсию или через перебор - личное дело каждого, программисты больше склоняются к рекурсии.
Разберём ещё один пример.
Есть объект:
Код
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
}]
}
};
Перед нами стоит задача просуммировать все цифры прогресса всех студентов. Данную задачу можно решить как через цикл, так и через рекурсию.
Решение через цикл Моё решение на данном этапе было такое:
Код
let summaryProgress = 0;
for (let key in students) {
if (Array.isArray(students[key])) {
for (let i = 0; i < students[key].length; i++) {
summaryProgress += students[key][i].progress;
}
}
for (let item in students[key]) {
if (Array.isArray(students[key][item])) {
for (let i = 0; i < students[key][item].length; i++) {
summaryProgress += students[key][item][i].progress;
}
}
}
};
console.log(summaryProgress); // 208
Немного рефакторинга своего кода, за счёт оптимизации созданной универсальной функцией, которая вызывается для разных массивов:
Код
let summaryProgress = 0;
function isArray(arr) {
if (Array.isArray(arr)) {
for (let i = 0; i < arr.length; i++) {
summaryProgress += arr[i].progress;
}
}
};
for (let key in students) {
isArray(students[key]);
for (let item in students[key]) {
isArray(students[key][item]);
}
};
console.log(summaryProgress);
Потом оказалось, что нужно посчитать средний прогноз среди всех студентов, то есть узнать сколько вообще студентов и общий прогноз разделить на их количество:
Код
let summaryProgress = 0;
let summaryStudents = 0;
function isArray(arr) {
if (Array.isArray(arr)) {
for (let i = 0; i < arr.length; i++) {
summaryProgress += arr[i].progress;
summaryStudents++;
}
}
};
for (let key in students) {
isArray(students[key]);
for (let item in students[key]) {
isArray(students[key][item]);
}
};
let averageProgress = summaryProgress / summaryStudents;
console.log(summaryProgress); // 208
console.log(summaryStudents); // 5
console.log(averageProgress); // 41.6
Решение преподавателя:
Код
function getTotalProgressByIteration(data) {
let total = 0; // общий прогресс
let students = 0; // общее число студентов
for (let course of Object.values(data)) {
if (Array.isArray(course)) {
students += course.length;
for (let i = 0; i < course.length; i++) {
total += course[i].progress;
}
} else {
for (let subCourse of Object.values(course)) {
students += subCourse.length;
for (let i = 0; i < subCourse.length; i++) {
total += subCourse[i].progress;
}
}
}
}
return total / students;
};
getTotalProgressByIteration(students);
По шагам решение преподавателя:
1.
Object.values(data) даёт нам массив значений перечисляемых свойств объекта
data (точнее, нашего объекта
students, который попадает в
data как аргумент)
то есть, данный массив будет по-сути содержать значение свойств
js и
html:
Код
[
[ { name: 'John', progress: 100 }, { name: 'Ivan', progress: 60 } ],
{ basic: [ [Object], [Object] ], pro: [ [Object] ] }
]
2. Далее идёт проверка, что если в
course попал массив, то к начальному значению студентов мы прибавляем длину этого массива (число его элементов, соответственно, число студентов в этом массиве)
3. Далее с помощью цикла мы заходим в каждый элемент массива (а это объект, ведь массив содержит в себе объекты), получаем значение свойства
progress для каждого из этих объектов и суммируем его с значением переменной
total.
4. Если в
course попадает не массив, а объект (у нас это значение свойства
html), мы делаем перебор значений его свойств, также задействуя при этом для получения значений свойств
Object.values На этом этапе
Object.values(course) нам даст массив, содержащий два массива внутри себя:
Код
[
[ { name: 'Peter', progress: 20 }, { name: 'Ann', progress: 18 } ],
[ { name: 'Sam', progress: 10 } ]
]
5. По аналогии также из каждого из этих массивов достаем число содержащихся в нем студентов (через значение длины этого массива) и с помощью цикла для каждого элемента массива (а каждый элемент в них это объект) получаем значение свойства
progress и суммируем.
Вариант решения с рекурсией
Базой рекурсии в нашем случае будет массив.
Код
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];
} 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]);
Всего комментариев: 0