Комментарии 27
Хорошая статья.
Чтобы совсем прочувствовать рекурсию желательно ещё и использовать чистые функции, тогда всё становится совсем красиво. Вместо того, чтобы рекурсивно посылать емейлы просто соберите список, кому собственно посылать емейлы, а потом это делайте:
function getEmails(value : object | string): string[] {
if (typeof value === 'string') {
return [value];
}
return Object.values(value).flatMap(getEmails);
}
...
getEmails(companyEmailAddresses).forEach(sendEmail);Таким образом во-первых мы разделяем подготовку данных с использованием их во всяких "грязных" делах, во-вторых мы можем бесплатно эти данные трансформировать. Например, во втором случае мы практически бесплатно можем починить баг "приходят дубликаты емейлов если одна почта указана в разных департаментах":
[...new Set(getEmails(companyEmailAddresses))].forEach(sendEmail);В общем, "разделяй и влавствуй" относится не только к рекурсии, но и к программированию в целом. В ООП его ещё называют SRP
желательно ещё и использовать чистые функции, тогда всё становится совсем красиво
Всё, кроме асимптотики.
Связи — никакой
Я высказался не против подхода с возвращением массива адресов, а против чистых функций как универсального средства.
function getEmails(value) {
const ret = [];
function getEmailsRec(v) {
if (typeof v === 'string') {
ret.push(v);
} else {
Object.values(v).forEach(getEmailsRec);
}
}
getEmailsRec(value);
return ret;
}Внутренняя функция не чистая, зато с асимптотикой всё в порядке.
У них одинаковая асимптотика — O(N) от количества ключей на всех уровнях. Вы только чуть-чуть сэкономили на работе сборщика мусора.
https://jsfiddle.net/rp746hy9/
Рост времени выполнения вашего варианта совсем не похож на линейный.
const flat = (input) =>
Array.isArray(input)
? input
: Object.values(input).reduce((acc, item) => [...acc, ...flat(item)], [])
const sendMail = (email) => console.log(`Send to: ${email}`)
flat(companyEmailAddresses).forEach((email) => sendMail(email))
Редьюсер почти всегда повышает сложность кода. Лучше обходиться без него.
Редьюсер это фолд, который по одному имени показывает что происходит. Вместо того чтобы держать весь стейт в голове достаточно посмотреть как обрабатываются 2 переменных — аккумулятор и текущее значение.
Если шаг редьюса очень сложный — то он просто выносится в отдельную функцию и все опять становится просто
На сколько я понимаю глубина стека ограничена везде, поэтому в контроллерах, например, рекурсию не используют либо запретив на уровне coding guide'а, либо на уровне ЯП.
В общем использовать рекурсию можно, если быть уверенным, что памяти всегда хватит на необходимое количество итераций, но, в реальной жизни этого ГАРАНТИРОВАТЬ, наверное, нельзя в 99% случаев.
В реальных проектах мне ее использование не встречалось.
Мне кажется тут джаве должно быть стыдно что в 2021 году она не научилась в хвостовую рекурсию.
Ваш случай не должен стек взрывать, должно происходить обычное вечное зацикливание.
Что до примера выше: то обход дерева очевидно имеет глубину log(N), таким образом чтобы выбить рекурсию в 5000 фреймов нужно иметь (в случае сбалансированного дерева) 2^5000 элементов. Даже если учесть сильно разбалансированное дерево, то 2^1000 вам скорее всего будет достаточно.
// Оба подхода приводят к одному и тому же выводу. Если вы возьмёте одинаковые входные данные, то функции дадут один и тот же результат.
Использование Фиббоначи в качестве примера рекурсии это одна из величайших ошибок педагогики.
Возьмите и ручками запустите ваш рекурсивный пример с х = 50. (чтобы не думать о размерах переменных — ну в питоне скажем)
Сколько она будет выполняться по сравнению с итеративной? А почему?
(про глубину стека уже расписали, так что не буду разоряться)
Для того, чтобы переложить N дисков со стержня A на стержень B, надо:
- Переложить N-1 дисков с A на С
- Переложить 1 диск с A на B
- Переложить N-1 дисков с C на B
В то же время итеративное решение далеко не очевидно.
Простите, а чем рекурсивный факториал хуже итеративного или наоборот? Кмк вполне эквивалентны, только цикл расписывать дольше
Простите, но О малое и О большое — это как раз-таки математические нотации, и ни про какой стек они не знают. О чем я и сказал — асимптотически это эквивалентные вещи.
Дальше можно смотреть уже про поведение в конкретных языках. В том же хаскелле переполнения не будет даже после миллионов рекурсивных вызовов по причине собственно отсутствия коллстека в сишном смысле.
Простите, но термин "асимптотически" в эту ветку вы ввели только что. Раньше про асимптотику никто не говорил. Вы точно ветки не перепутали?
Прошу прощения, перепутал с веткой https://habr.com/ru/company/skillfactory/blog/540300/#comment_22668986
Но поинт остается про то, что во всех приличных языках есть tailrec, а в некоторых и без него стек не вылетает.
Ну а дальше у нас происходит обычный программерский трейдоф читаемости в производительность.
Рекурсивное решение Фибоначчи отработает влёт, если добавить мемоизацию. Конкретно здесь это изыски, но в целом подход имеет место быть.
function gatherEmailAddresses(departments) {
let departmentKeys = Object.keys(departments);
departmentKeys.forEach((dept) => {
if (Array.isArray(departments[dept])) {
return departments[dept].forEach((email) => sendEmail(email));
}
return gatherEmailAddresses(departments[dept]);
});
}
А куда return в forEach возвращать будет? Выглядит легально, но обескураживает.
И, кстати, итеративный вариант фибоначчи можно было написать в динамическом стиле, а не пугать массивами.
Как учить рекурсию разработчикам программного обеспечения