|
Рекурсивные функцииНачиная с этого занятия, мы немного глубже рассмотрим работу с функциями в JavaScript и начнем с понятия рекурсии. Рекурсивные функции – это функции, которые вызывают сами себя. Понять работу рекурсии проще всего на примере. Предположим, мы хотим вычислить значение числа x в степени n. Для простоты степень n у нас будет натуральным числом: n = 1, 2, 3,… Один из вариантов реализации может быть такой: function pow(x, n) { let res = 1; for(let i = 0;i < n;++i) res *= x; return res; } Вызываем функцию, проверяем как она работает: console.log( pow(2, 2) ); Реализуем эту же функцию через рекурсию. Для этого заметим, что
то есть, для вычисления значения на текущем n-м шаге достаточно взять значение на предыдущем n-1-м шаге и умножить его на x. Эта формула, по сути, отражает принцип рекурсии. В нашем случае она будет выглядеть так: x*pow(x,n-1) Получаем такую реализацию: function pow(x, n) { if(n <= 0) return 1; else return x*pow(x, n-1); } let res = pow(2, 3); Как это работает? Сначала вызывается функция pow(2, 3). Она помещается в стек вызова функций, в котором хранится контекст выполнения (execution context) текущей функции pow(2, 3). Далее, выполняется тело функции. Проверяется первое условие. Оно оказывается ложным, так как 3 <= 0 дает false. Поэтому идет переход на else и прежде чем выполнить оператор return, снова вызывается та же функция pow(2, 2). Выполнение функции pow(2, 3) останавливается, в стек помещается контекст выполнения второй функции pow(2, 2) и она запускается. Снова проверяется первое условие, оно ложно, переходим по else к оператору return и опять вызываем функцию pow(2, 1). Здесь снова все повторяется, в стек помещается очередной вызов функции и по условию вызывается следующая функция pow(2, 0).
Теперь первое условие становится истинным и функция pow(2,0) возвращает значение 1 и рекурсия не идет дальше вглубь – она останавливается. Функция pow(2.0) завершается, ее контекст выполнения удаляется из стека вызовов и управление передается функции pow(2, 1). Но она частично уже выполнена. Поэтому, берется значение 1 от pow(2, 0), результат умножается на x=2 и величина 2 возвращается функцией pow(2, 1). Контекст выполнения функции pow(2,1) удаляется из стека, управление переходит к вышестоящей функции pow(2,2) и здесь мы уже имеем результат умножения x*x, то есть, 2*2 = 4. Далее, возвращаемся к самой верхней функции pow(2,3), здесь 2*4=8 и этот результат становится результатом вычисления рекурсивной функции. Рекурсию очень удобно применять для обхода свойств объекта сложной структуры. Представьте, что у нас есть компания, состоящая из нескольких отделов и в каждом отделе работают свои сотрудники: let company = { sales: [{name: 'Иван', salary: 1000}, {name: 'Михаил', salary: 600}], development: { sites: [{name: 'Евгений', salary: 2000}, {name: 'Алексей', salary: 1800}], internals: [{name: 'Федор', salary: 1300}] } }; И нужно написать функцию вычисления суммарной зарплаты для всей компании и для каждого из отделов. Это можно реализовать так: function sumSalary(department) { if(Array.isArray(department)) { return department.reduce((prev, current) => prev + current.salary, 0); } else { let sum = 0; for(let prop in department) { sum += sumSalary(department[prop]); } return sum; } } И вызывать для любого отдела или компании в целом: console.log( sumSalary(company) ); console.log( sumSalary(company.sales) ); console.log( sumSalary(company.development) ); Вот что из себя представляют рекурсивные функции. У них есть только одно важное ограничение: стек вызова не бесконечный – нельзя рекурсию делать слишком глубокой. Разумное значение – не более 1000 рекурсивных итераций. Если требуется больше, то алгоритм лучше подкорректировать. Видео по теме |
