Comments 42
В основе работы всех компьютеров лежат рассуждения о Машине Тьюринга, а доказательство её работы основано, в том числе, и за счет использования рекурсии, и очень жаль, что многие забывают, что это чистая математическая абстракция.
Ужасы рекурсии.
Скрытый текст
Обнаружился у меня как-то геморрой. Я боюсь медицины и операций, но терпеть больше не мог, что поделать, согласился на лазерное прижигание. Оно под местной анастезией происходит, так что терзания скорее психологические, полежал, надел штаны и домой. Меня предупредили, что самое суровое будет потом, когда первый раз сходишь в туалет. Поэтому я оттягивал этот момент подальше, старался есть поменьше, но вот оно наступило. Когда процесс закончился, я встал и решился посмотреть на результат. Вы, наверное, слышали выражение "пердак бомбанул", оно лучше всего описывает то, что я увидел: ошмётки крови и отходов жизнедеятельности разлетелись по унитазу. Увидев это, я чуть не обосрался, но вовремя сдержался, поняв, что это создаст рекурсию, и не простую, а, так сказать, "хвостовую". В чём же мораль этой истории? В организме и в рекурсии очень важно, чтобы правильно работал выход.
Извините.
"напишем два неэквивалентных кода и свалим всё на рекурсию". Я не понимаю, почему вы постоянно зовёте имлпментации без единого рекурсивного вызова рекурсиями. Это не считая того что зачем-то ещё и стек впендюриваете, хотя он там нафиг не нужен ни в одном из вариантов. Ещё и циклы никак не ограничены.
Лично мне чтобы понять как это работает и написать эквивалентный код потребовались и отладочный вывод и пошаговый разбор в отладчике и всё равно это оказалось не просто, потому что много нюансов.
ну не знаю, пробовали открыть учебник пятого класса и посмореть как работат степени? Ну и такое свойство как ассоциативность умножения вроде тогда же рассматривается, а то и ещё раньше. Как у вас из этого внезапно ДВА цикла появилось вообще не понимаю.
Ну, и основной прикол в том что правильная рекурсивная чистая функция отлично оптимизируется в цикле, в отличие всего того ахутнга, что вы понаписали. Ключевое слово - чистая, что прямо противоречит вашему желанию зачем-то впихнуть в неё ещё что-то, поломав скорость работы на том же спекулятивном исполнении на процессоре.
Я не понимаю, почему вы постоянно зовёте имлпментации без единого рекурсивного вызова рекурсиями.
В смысле без единого? - везде под "код x.2" идёт пример с рекурсией, а сопровождающие его два примера с циклами иллюстрируют как это нормально запрограммировать и что на самом деле делает рекурсия если посмотреть её под пошаговым отладчиком и/или через добавление отладочной информации.
Это не считая того что зачем-то ещё и стек впендюриваете, хотя он там нафиг не нужен ни в одном из вариантов.
Затем что рекурсия Всегда неявно использует стек процессора и в данных примерах делает это именно так как описано в статье, но если смотреть только на код рекурсии не пытаясь вникнуть в происходящее то этого не видно. Об этом и статья что "вы не видите суслика, а он есть!"
Ещё и циклы никак не ограничены.
При применении рекурсии всегда "автоматически" формируется как минимум два (может значительно больше) "псевдоцикла" и программист никак не может на это повлиять или оптимизировать. Точнее может если откажется от рекурсии.
правильная рекурсивная чистая функция отлично оптимизируется в цикле
Можно пример такой "чистой" рекурсивной функции?
Не во всех языках. Функциональные языки содержат tail call optimization, и хвостовая рекурсия не отъедает стек, там даже call заменяется на jmp. Вся статья должна называться "Я не знаю, что такое хвостовая рекурсия".
Вся статья должна называться "Я не знаю, что такое хвостовая рекурсия".
Нет, это называется кто-то не заметил:
Компиляторы функциональных языков программирования умеют преобразовывать так называемую «хвостовую» рекурсию в цикл, убирая её негативные эффекты. Но «хвостовая» рекурсия позволяет реализовать лишь простейшие варианты рекурсии. В общем случае рекурсия эквивалентна нескольким псевдоциклам и анализ количества и функционала этих псевдоциклов нетривиален, а потому не подлежит оптимизации компилятором. По сути «хвостовая» рекурсия не более чем «заплатка» позволяющая вернуть в функциональные языки программирования опрометчиво удалённые из них циклы. Вред от мышления рекурсиями в программировании будет рассмотрен ниже на конкретных примерах.
И да, это вводная часть с простейшими примерами, дальше будут примеры невозможность оптимизации которых на уровне компилятора будет очевидна.
Был неправ, не заметил. Но продолжаю считать, что вы не очень хорошо понимаете, что такое хвостовая рекурсия. Те два примера, которые вы привели, отлично переписываются на хвосто-рекурсивный вариант и могут выполнять сколько угодно долгие вычисления, не вызывая переполнения стека. Иначе говоря, нельзя говорить об алгоритмической эффективности просто рекурсии, одну и ту же задачу часто можно решить несколькими рекурсивными способами.
Буду ждать следующих статей. Есть подозрение, что для решения задач без рекурсии вы будете вводить явный стек данных.
Затем что рекурсия Всегда неявно использует стек процессора
у процессора есть регистры, а не стек. Ну и для того чтобы использовать стек достаточно объявить локальные переменные без аллокаций. То бишь пока у вас не появляется malloc/new ваши переменные будут на стеке. Ваши же примеры совершенно точно начинают использовать кучу для того чтобы сделать инсепшн и использовать стек для хранения рассчитанных значений. Только проблема в том что у вас значения рассчитываются и кладутся в стек, а в том же дебаггере рассчёт значений будет происходить только после того как вы достигните точки останова рекурсии и только потом с каждым pop станет вычислять значение. То есть даже симуляция стека кривая. Попробуйте переписать на какой-нибудь Forth/Porth или хотя бы lua FFI, чтобы понимать как это работает.
формируется как минимум два (может значительно больше) "псевдоцикла"
никаких там псевдоциклов. с точки зрения потоков данных оно вполне себе обычный цикл, в случае с конечной рекурсией - как в ваших примерах - с вполне себе понятной точкой останова этого цикла. Так что ни один while true в статье не оправдан.
Можно пример такой "чистой" рекурсивной функции?
Всё что не полагается на внешнее состояние фактически будет чистой функцией. Один вход - один выход, и никаких влияний и зависимостей на внешние контексты. Так что формально любая из коротких функций в статье по идее будет чистой. С аллоцирующими функциями (читай - используют std::stack/vector/etc) есть нюансы, поэтому они не будут чистыми.
Ваши же примеры совершенно точно начинают использовать кучу
Да, std::stack использует кучу, но он здесь исключительно для того чтобы проиллюстрировать логику поведения рекуррентного варианта, использующего стек неявно.
Сделать варианты с контейнером без лишних обращений к куче не проблема. Просто это не имеет отношения к алгоритмической логике рассматриваемого кода, поэтому не стал усложнять этим примеры.
В остальном вижу что мы говорим на разных языках. Если придумаю другие слова чтобы вам стало понятнее о чём я, то потом напишу дополнительно.
Как у вас из этого внезапно ДВА цикла появилось вообще не понимаю.
Просто возьмите Код 1.2. и Код 2.2. и пошагайте в них отладчиком и/или взгляните на приведённую в статье отладочную информацию которую выводит Код 1.4. и Код 2.4. и вы наглядно увидите что этот код ведёт себя именно как два цикла, выполняющиеся один за другим.
И да, статья как раз о том что появление этих двух (и более) циклов для читающего программу может оказаться внезапным и неочевидным.
Категорически не согласен со статьей. Главное возражение: учите, блин, матчасть. Почитайте про динамическое программирование, про обход в глубину. Тогда вся эта непонятность рекурсии быстро улетучится. Да, если не знать алгоритмы и computer science, то их писать и понимать будет сложно. Но это не проблема алгоритмов и рекурсии.
Рекурсия часто позволяет писать более простой и понятный код. Как то же возведение в степень в виде рекурсии гораздо понятнее. И выводится напрямую из арифметики. Тривиальная же логика x^2k = (x^k)^2 = (x^2)^k, x^(2k+1) = x(x^k)^2 = x(x^2)^k. И переводится в код напрямую, сначала с двумя случаями четного/нечетного, а потом их можно объединить для краткости кода.
Обход графа в глубину без рекурсии написать сложно и непонятно, почти любая работа с древовидными структурами данных в виде рекурсии получается читабельнее и понятнее.
Да, у рекурсии есть накладные расходы - вызовы не бесплатны, тратится стек. Но часто это тривиальная цена за более простой код, а иногда рекурсия даже оказывается быстрее. Например, в динамическом программировании рекурсивная реализация обходит только достижимые состояния, когда как реализация циклами снизу-вверх обходит вообще все. И во многих задачах достижимых состояний гораздо меньше чем вообще возможных, в результате чего рекурсивная реализация заметно быстрее, даже несмотря на накладные расходы на вызовы функций.
Да, пихать рекурсию туда, где это не надо - не надо. Как не надо городить фабрики билдеров фабрик или ассемблерные вставки там, где это не надо. Это не какая-то особенность рекурсии, это про целесообразность применения инструментов.
И переводится в код напрямую, сначала с двумя случаями четного/нечетного, а потом их можно объединить для краткости кода.
Да у меня там есть ссылка на эту логику с чётностью / не чётностью и комментарий к ней: "Однако с логикой там всё мутно и сложно - много букв и формул, а в конструкции 
усматривается сакральный смысл по преобразованию нечётных чисел в чётные, хотя на самом деле вычитание единицы из нечётного числа обнуляет младший двоичный разряд, а целочисленное деление на два этот младший разряд отбрасывает независимо от того был он предварительно обнулён вычитанием единицы или нет. "
почти любая работа с древовидными структурами данных в виде рекурсии получается читабельнее и понятнее.
Про древовидные структуры будет в следующих частях. Есть что сказать, но пока не буду спойлерить.
Но часто это тривиальная цена за более простой код,
Примеры с очень дорогой и главное неочевидной ценой тоже будут в продолжении. Причём цена там из серии когда в супермаркете выбрал товар по выгодной цене, а на кассе пробивают чек на цену х10 или х1000.
Однако с логикой там всё мутно и сложно - много букв и формул
Чего сложного? Вот самая естественная реализация рекурсивного подхода, которая напрямую выводится из арифметики сразу же. Никаких обнуляемых двоичных разрядов, никакого вычитания единицы, никаких битовых операций. Раз x^(2k+1) = x*(x^2)^k, то можно сначала посчитать (x^2)^k рекурсивно:
double Pow(double x, int n) {
if (n == 0) return 1.0;
if (n % 2 == 1) {
// x^(2k+1) = x*(x^2)^k
return x*Pow(x*x, n/2);
} else {
// x^(2k) = (x^2)^k
return Pow(x*x, n/2);
}
}Ну или вот, основываясь на возведении в квадрат: x^n = x^(n//2 * 2 + n%2) = (x^(n//2))^2 * x ^ (n%2):
double Pow(double x, int n) {
if (n == 0) return 1.0;
double res = Pow(x, n/2); // x^(floor(n/2))
res = res*res; // x^(floor(n/2)*2)
if (n % 2 == 1) res *= x; // x^n
return res;
}Этот подход чуть эффективнее для длинной арифметики, потому что тут числа растут медленнее.
Единственный тонкий момент: надо догадаться свести возведение в степень к возведению в половинную степень. Вот это деление на 2 и дает логарифмическую сложность вместо линейной. Но это один из самых заезженных приемов в computer science. И именно этот прием естественно приводит к рекурсии, потому что это метод "разделяй и властвуй" - вы разделяете данные на части, и решаете задачу в каждой меньшей части, потом как-то объединяете. Ту же самую задачу для каждой части. Вот и возникает рекурентность. Если про этот метод знать, вы сразу же придумываете оптимальное рекурсивное решение.
Вот когда вы пытаетесь циклы перевести в рекурсию, не понимая основного принципа деления пополам, вот там сложности в логике возникают, да.
Ждем следующей статьи с примерами по деревьям и неочевидной ценой (уж не баян ли про экспоненциальный рост и числа Фибоначчи там?).
Ваш первый вариант полностью эквивалентен моему варианту Код 2.6. с поправкой на то что ваше n % 2 эквивалентно моему n & 1, а n/2 эквивалентно n>>1. И компилятор скорее всего скомпилирует на этих конструкциях одинаковый машинный код.
Второй вариант интереснее про него отвечу позже, возможно добавлю этот ответ в статью.
Вот когда вы пытаетесь циклы перевести в рекурсию, не понимая основного принципа деления пополам, вот там сложности в логике возникают, да.
На мой взгляд описанная мною логика основанная на двоичном представлении n и использовании сдвига вместо деления более точно и наглядно описывает процесс, но повторюсь - формально и с точки зрения машинного кода после оптимизирующего компилятора эти варианты эквивалентны, поэтому ваша логика равноправна с моей.
И всё это не отменяет моего последующего разбора этого варианта. Как его вывести из рекуррентной или цикловой логики это прелюдия - важнее как он потом реально работает.
Да, про числа Фибоначчи тоже будет, может кому-то это и баян, а по мне так яркий и наглядный пример.
Ваш первый вариант полностью эквивалентен моему
Да. И он выдумывается почти сразу же, как только вы объясните человеку, незнакомому с алгоритмом, что надо сначала посчитать значение половинной степени, потом это возвести в квадрат и подправить, если четность не та.
На мой взгляд описанная мною логика основанная на двоичном представлении
nи использовании сдвига вместо деления более точно и наглядно описывает процесс
Не совсем. Это другой по сути алгоритм, до которого по моему мнению гораздо сложнее додуматься и понять его. Это фактически умножение в столбик степени в двоичной системе. Вот надо вам подсчитать x^(1*n), вы это 1*n считаете в столбик. Только поразрядный сдвиг степени (умножение ее на 2) становится возведением в квадрат, а сложение степени - умножением. По сути получается развернутся задом наперед версия рекурсивного алгоритма, но это потому тут как в математике - можно разными способами решать уравнения, получите одинаковый в итоге ответ.
поэтому ваша логика равноправна с моей.
Но моя сильно проще и понятнее. И объяснение и код. Так что ваш аргумент, что рекурсия сложна и непонятна по сути своей, тут не работает.
Но моя сильно проще и понятнее.
:)) Боюсь тут уже пошла вкусовщина - одним проще и понятнее одно, другим другое.
Лично мне значительно проще заметить что: "
, обойдясь 4 умножениями вместо 16." Но это работает только при 
. Дальше остаётся вспомнить что любое целое положительное n в двоичной системе и есть сумма чисел 
"например, десятичное число 11 в двоичном виде 0b1011, где 1 в нулевом, первом и третьем битах означают 
, а 0 во втором бите означает что 
в этой сумме нет (отсчёт битов начинается с нулевого бита, поэтому второй бит в 0b1011 визуально находится на третьей позиции)." А суммирование степеней при одинаковом основании эквивалентно перемножению, "например, 
. " И исходя из этой логики проверка очередного разряда как n & 1 и переход к следующему разряду n>>1 выглядят значительно логичнее чем n % 2 и n/2 хотя формально это одно и тоже.
И никакого умножения в столбик я здесь не вижу.
А вот ваша версия:
надо сначала посчитать значение половинной степени, потом это возвести в квадрат и подправить, если четность не та.
звучит конечно короче, но у меня в голове укладывается плохо ;)
https://godbolt.org/z/dd6qPo9Kh я так сделал, но глубоко не тестил, спасибо, интересно
А вот ваша версия ... звучит конечно короче, но у меня в голове укладывается плохо ;)
Всё очень просто. Если знать и активно применять динамическое программирование, то подход половинного деления абсолютно естественный и его проще придумать. Аналогично, если иметь много опыта с разделяй и властвуй. Если быть от этого далёким - то действительно может быть непривычно.
А вот подход с двоичным разложением существенно завязан на структуру задачи. Двоичное разложение редко когда применимо к задачам. И нужно быть достаточно сильно погружённым в домен, чтобы догадаться до такого инварианта как двоичное разложение. Иными словами, этот подход достаточно тяжело переносить на другие задачи.
Как аналогию можно сравить дерево отрезков и дерево фенвика. Дерево отрезков гораздо проще придумать и доказать. Также в дерево отрезков гораздо проще вносить всякие интересные вариации. С деревом фенвика это делать гораздо сложнее.
Ну и в целом, я, например, достаточно много трачу времени на то, чтобы устранить рекурсию. И это очень сложно (ну кроме банального эмулирования стека - но это медленно довольно таки). Поэтому всё же в общем случае рекурсия более общий механизм чем циклы. Рекурсию можно заменить на цикл только в очень ограниченном наборе юзкейсов - и лишь в части из них, это выглядит естественно.
Банально, попробуйте написать поиск в дереве отрезков без рекурсии и сложность кода.
Двоичное разложение редко когда применимо к задачам.
Наверное да, но здесь речь идёт не об разложении, а об естественном представлении чисел в компьютере. Т.е. его даже "разлагать" не нужно - оно уже именно так и представлено - бери и пользуйся! Возможно мне это просто и естественно потому что у меня в голове понимание двоичной системы неразрывно связано с программированием, а для кого-то она может показаться и экзотикой.
Как аналогию можно сравнить дерево отрезков и дерево фенвика.
Спасибо, включу это в план того что описывать когда кончатся уже заготовленные мною примеры.
не, ну с деревом согласен, я себе bvh представил - вспомнил там мы прыгаем в лево и право, да там рекурсия по стандартному траверсу
а кстати в случае бвх дерева, оно вообще клёвое, может содержать чо хочешь, главное классифицировать обьект геометрически - на слове геометрически надо призадуматься над что такое текст ) - ну это лично моё мнение
возможно это лазеечка к бигинт )
то что вы пишите поидее это взгляд на разные подходы, например в грид мы делаем смещения!, а в дереве мы делаем обход по дереву, это то как представлены данные, и то как мы к ним получаем доступ, и то как генерируем и рисуем например
тоесть pow это верхушка сама по себе вроде законченная, но в тот же момент в рендере на деревьях вы будете делать обход, а в системе грид вы будете делать битовое смещение и получать сразу нужную координану чанка в грид внутри чанка уже определять плавающую составляющую, но после чанка надо найти блок в мире или перед этим чанк в мире, кароче там интересно тоже, что лучше смещение или нет это такой тонкий нюанс походу дела
Ещё моё объяснение такое длинное потому что я подробно разъясняю все шаги с примерами, хотя тому кто в курсе как устроена двоичная система достаточно сказать: "заметьте что: и здесь 4 умножения вместо 16. Но это работает только при . Дальше остаётся вспомнить как устроен двоичный формат числа и про математическое свойство 
".
надо сначала посчитать значение половинной степени, потом это возвести в квадрат и подправить, если четность не та.
А ваше объяснение такое короткое и непонятное потому что вы просто опускаете какие-то очевидные лично вам, но совсем не очевидные мне пункты.
Мне из вашего объяснения понятно только то, что ваша "половинная степень" это аналог моего n>>1 , а ваше "подправить, если четность не та" - аналог моего и за счёт этого ваша логика приводит к правильному результату. Но вы в это явно вкладываете какие-то другие смыслы, которые от меня ускользают ;)
Запилите в следующей статье голосовалку, посмотрим, какое объяснение покажется проще народу.
Если мое объяснение расписвать полностью, ону будет максимум в пару раз длиннее и все равно проще вашего:
Чтобы подсчитать x^n быстро, будем делить степень пополам. Вычислим x^floor(n/2) рекурсивно, возведем в квадрат, возможно надо будет домножить на x, если n было нечетно. Таким образом, для вычисления степени n надо сначала найти степень n//2. Для нее надо будет найти степень n//4, и т.д. Рано или поздно мы придем к степени 0, которая тривиальна и равна 1.0. Это работает за O(log n), потому что надо будет максимум сeil(log_2(n))+1 делений пополам, чтобы из n получить 0 по определению логарифма.
Плюс, это универсалный подход разделяй и властвуй, переносимый на другие задачи, в отличии от вашего. Поэтому любой программист, знакомый с матчастью это сразу поймет.
На простых задачах это неинтересно. Попробуйте сравнить на более сложных, особенно где есть нетривиальное состояние. Например:
quick sort: его, конечно, можно написать без рекурсии, но код будет, мягко говоря, нечитабельным
задача с литкода про восстановление дерева по его inorder и preorder. Решается элементарно за 5 минут с помощью рекурсии, в 5 строк кода на питоне. У нее есть нерекурсивное решение, в чем-то изящное, но оно сильно нетривиальное, и там надо додуматься до хитрого инварианта того, что пихать в стек.
Здесь наглядно видно результат работы обоих псевдоциклов. Увидеть эти циклы можно и при пошаговой отладке программы. Но в программе с рекурсией (код 1.2) мы не видим никаких циклов, а значит у программиста нет возможности выкинуть лишний цикл. Это иллюстрация того что рекурсия неуправляема и плохо читаема (красивый лаконичный код рекурсии не соответствует реальному поведению программы и надо разбираться что там подразумевается между строк).
Наглядно, но неправильно. Правильно смотреть вот здесь: https://godbolt.org/z/86nxErzxW - найдите 10 отличий.
Вообще, Вы в этой статье смешиваете семантический уровень и уровень железа. Как там оно будет исполняться на железе - вопрос весьма нетривиальный, на который в общем случае ответить нельзя. Например в том же хаскеле рекурсия не тратит стек в принципе (и там вообще нет стека в привычном понимании).
Рекурсия захламляет стек не только последовательностью
n-1, n-2, n-3, ..., а ещё и адресом возврата из функции, но здесь и далее разбор этих "накладных расходов" опущен, поскольку рекурсия здесь рассматривается с точки зрения алгоритмической эффективности.
А что именно в Вашем понимании "алгоритмическая эффективность"?
Edit:
здравомыслящий программист не станет писать громоздкий и нелогичный код 2.3 вместо простого и наглядного кода 2.1, но именно код 2.3 является наглядной демонстрацией алгоритма работы "простого и красивого" рекуррентного кода 2.2.
Явно писать код со стеком - конечно не будет. Но это не означает, что наличие этого стека как-то мешает. В тот момент, когда глубина стека, или наличие там лишних значений становиться проблемой - тогда уже не мыслят категориями "рекурсия"/"цикл". В таких ситуациях мыслят бенчмарками и асмом. А в типовом коде, рекурсию используют не потому что быстро - а потому что просто - и с этим, вроде, даже Вы согласны, что никаких проблем нет.
Наглядно, но неправильно. Правильно смотреть вот здесь: https://godbolt.org/z/86nxErzxW - найдите 10 отличий.
Кстати на https://godbolt.org msvc совсем древний и он так не умеет. Сейчас смог докопаться до релиз варианта в последнем msvc v145 из VS2026, но и он не справился с задачей превратить рекуррентный факториал в цикл и сделал так как у меня в статье. Так что ваше "правильно" пока компиляторозависимо.
А clang в варианте с рекурсией ухитрился не только превратить в цикл, а ещё и сделать разворачивание цикла.
Так что ваше "правильно" пока компиляторозависимо
"Неправильно" - это я с методологической точки зрения. Не важно, есть там использование стека или нет, важно что дебаг-принты и отладчик нельзя использовать для анализа на уровне "тактов" - они просто рисуют фантазию на тему, а не реальное поведение.
А так, понятное дело, что оптимизации компиляторозависимы. Более того, эти оптимизации ещё могут отваливаться при любом обновлении компилятора. Но, как уже говорил, подсчёт тактов в целом компиляторозависим.
А так я и не про такты. Я про "внутреннюю кухню" рекурсии, которая в этих простых примерах пока только "мусорит" но в более сложных примерах станет неотъемлемой частью алгоритма, поэтому я и подчёркиваю что уже здесь важно понимать что она там есть и как именно она выглядит.
Ассимтотически, по крайней мере в этих примерах, и рекурсия и цикл оба работают за линейное/логарифмическое время (в зависимости от примера). Поэтому ассимптотически они одинаково оптимальные, либо неоптимальны*.
А наличие лишнего прохода - это как раз про "такты". Потому что если мы не учитываем такты, то замедление алгоритма даже в 2-10 раз, зачастую не является принципиальным.
*: ну если придираться, то рекурсия в этих примерах использует линейную доп. память, против константного у циклов. Но это по большей части вызвано вырожденностью этих примеров.
Наглядно, но неправильно. Правильно смотреть вот здесь: https://godbolt.org/z/86nxErzxW - найдите 10 отличий.
Спасибо интересно - я смотрел пошаговое выполнение в msvc в дебаг режиме (в релизе нужные точки останова просто не ставятся, поэтому трудно найти нужное место) поэтому не увидел способность С++ компилятора нормально превратить простую рекурсию в цикл. Поправлю в статье и учту на будущее. Но я по прежнему уверен что с более сложными примерами компилятор так не сможет. Да, дальше буду проверять и там тоже.
А что именно в Вашем понимании "алгоритмическая эффективность"?
Не приписывать лишних циклов с бессмысленными действиями.
И ещё то, что количество итераций может внезапно оказаться значительно больше чем это реально необходимо. В приведённых здесь примерах этого нет, но дальше такие примеры появятся.
Явно писать код со стеком - конечно не будет.
std::stack здесь исключительно для иллюстрации того что рекурсия неявно использует стек, во всяком случае на x86_64, где он есть. И в более сложных примерах это использование стека будет не "шумом", который умный компилятор может даже выкинуть как здесь, а неотъемлемой частью алгоритма, поэтому я и сомневаюсь в способности компилятора различать эти ситуации за пределами совсем уж тривиальных случаев.
А "не будет" относится к тому что не будет приписывать второй цикл, который выполняет исключительно бессмысленные действия.
Обычно, под "алгоритмической эффективностью" подразумевают что-то в стиле "оптимальная ассимптотика". Поэтому возможно стоит сменить термин.
В приведённых здесь примерах этого нет, но дальше такие примеры появятся.
Так может стоило начать именно с таких примеров? Потому что пока что приведённые примеры весьма нереалистичны (никто не пишет факториал в виде рекурсии кроме как в учебниках по программированию :)). Впрочем, редко кто вообще пишет факториал (потому что его нужно либо фьюзить, либо просто предпосчитать во всех практических кейсах)
А "не будет" относится к тому что не будет приписывать второй цикл, который выполняет исключительно бессмысленные действия.
Вообще, с эффективностью в плане "не делать лишнего".есть всякие неочевидные сложности. Например, можете ли Вы сказать, оптимален ли такой код (с точки зрение Вашей "алгоритмической эффективности"):
Скрытый текст
size_t bespoke_strlcpy(char *dst, const char *src, size_t size)
{
size_t len = 0;
for (; src[len] != '\0'; ++len) {} // strlen() loop
if (size > 0) {
size_t to_copy = len < size ? len : size - 1;
for (size_t i = 0; i < to_copy; ++i) // memcpy() loop
dst[i] = src[i];
dst[to_copy] = '\0';
}
return len;
}Первый проход здесь почти бесмысленный. Можно его легко совместить со вторым проходом.
Ответ
При совмещении проходов код станет более "оптимальным", но при этом более "медленным" :) (тык)
Поэтому говорить об оптимальности без бенчмарков - как минимум странно.
P.S. Я честно говоря, не до конца понимаю, какой тезис Вы пытаетесь отстоять в данной статье. То ли, что "рекурсия вредит читаемости кода/усложняет код", то ли что "рекурсия - это медленно". Это, если что, разные тезисы, которые обычно могут быть важны в разных ситуациях (и чаще всего несовместимы!).
никто не пишет факториал в виде рекурсии кроме как в учебниках по программированию :)). Впрочем, редко кто вообще пишет факториал (потому что его нужно либо фьюзить, либо просто предпосчитать во всех практических кейсах)
Но большинство начинает знакомство с программированием как раз с учебников. А там эти примеры без достаточных пояснений и раскрытия того что "между строк". Поэтому я и решил начать именно с них, чтобы просто восполнить этот пробел.
какой тезис Вы пытаетесь отстоять в данной статье. То ли, что "рекурсия вредит читаемости кода/усложняет код", то ли что "рекурсия - это медленно"
Да, и что "рекурсия вредит читаемости кода/усложняет код" и то что рекурсия не просто бывает медленной, а может оказаться внезапно и трудно предсказуемо ресурсоёмкой (медленно лишь один из аспектов ресурсоёмкости), а это тоже про "вредит читаемости".
А там эти примеры без достаточных пояснений и раскрытия того что "между строк"
Я не знаю, в каких учебниках Вы смотрели, но когда я изучал рекурсию, там было вполне себе рассказано, что происходит между строк. Поэтому не могу согласиться с этим порывом.
Да, и что "рекурсия вредит читаемости кода/усложняет код" и то что рекурсия не просто бывает медленной, а может оказаться внезапно и трудно предсказуемо ресурсоёмкой (медленно лишь один из аспектов ресурсоёмкости), а это тоже про "вредит читаемости".
Так не пойдёт. Эти тезисы находятся в конфликте, поэтому не имеет смысла пытаться их доказывать одновременно - просто получите кашу из мнений. Читаемость важна в первую очередь в "желтой" и "зелёной" зоне проекта, а вот ресурсоёмкость становиться важна, в основном, в красной зоне проекта. Пытаться доказать их одновременно - это доказательство запутыванием (ввиду неясного контекста!).
При совмещении проходов код станет более "оптимальным", но при этом более "медленным" :) (тык)
Отличный пример! Он прекрасен тем что "лишний" цикл прописан явно и для читающего это повод задуматься о том что он здесь не случайно.
А рекурсия добавляет свои псевдоциклы неявно, втихаря, скрытно и полностью по собственной инициативе без контроля со стороны программиста. И программисту остаётся либо их "не замечать" либо надеяться что они пойдут на пользу, хотя в общем случае это не факт.
Поэтому говорить об оптимальности без бенчмарков - как минимум странно.
Повторю свой ответ выше: А так я и не про такты, поэтому и бенчмарков тут нет. Я про "внутреннюю кухню" рекурсии, которая в этих простых примерах пока только "мусорит" но в более сложных примерах станет неотъемлемой частью алгоритма, поэтому я и подчёркиваю что уже здесь важно понимать что она там есть и как именно она выглядит.
немного странно, учитывая, что что факториал, что возведение в степень легко переписать через хвостовую рекурсию (хоть, конечно, и потребуется от компилятора её поддержка — но на gcc или clang это просто один флаг поставить)
далее планируемые числа фибоначи тоже
хотя вот числа аккермана и определитель без введения какого-то списка на куче кажутся тяжёлыми в этом плане (хотя я никогда не писал реализацию для аккермана хоть какую, так что знать не могу… вообще, это наверное просто вопрос того, чтоб немного поразмыслить)
в любом случае, для восстановления справедливости, не было бы неинтересным видеть тоже самое что писалось через "адекватные" циклы, написанным через tailrec
(впрочем, всё же очевидным минусом тут является в любом случае, что компилятор волен поступить как захочет)
далее планируемые числа фибоначи тоже
Ну нет, там хвостовая рекурсия невозможна, хотя бы потому, что там 2 рекурсивных вызова. Один из них хвостовым не будет никак. Хотя, сильно извратившись и добавив в функцию параметр аккумулятор, можно один из двух вызовов сделать хвостовым. Но это не сильно чем поможет.
я её уже однажды придумав написал, и потому легко повторю ещё раз :)
uint64_t fib(uint64_t n, uint64_t curr = 0, uint64_t prev = 1) {
if (n == 0) return curr;
return fib (n-1, curr + prev, curr);
}можно даже легко переписать для случаев, когда n < 0
по сути, все аргументы это просто всё те же мутабельные переменные, если бы мы писали через обычные циклы
Это другой алгоритм. Попробуйте словами описать, что считает вот эта вот функция, что ей передается. Ей передаются f_k и f_k+1 и она возвращает f_(k+n). Согласитесь, это совсем не функция, которая считает f_n.
Тут же все наизнанку вывернуто. Зачем тут рекурсия вообще? Вы взяли рекурсивную функцию Фибоначчи f(n) = f(n-1) + f(n-2), добавили мемоизацию, получив ДП, переписали это в виде цикла снизу-вверх в массиве, потом применили оптимизацию для хранения только двух последних чисел, а потом зачем-то взяли вот этот цикл и переписали его в виде рекурсии. Это как раз тот случай, где рекурсию применять смысла вообще нет. Если компилятор не развернет ее в цикл, это лишь зря потраченная память на локальные переменные. Только в каких-нибудь чисто функциональных языках программирования придется вот так извращаться, но это не от хорошей жизни, а из-за того что в ЯП циклов не завезли.
И это совсем не та же самая оптимизация хвостовой рекурсии, о которой речь идет в статье. Так-то, вообще любую рекурсию можно заменить на хвостовую. Технически - это правда, ведь можно просто переписать стек вручную, а потом основной цикл заменить на хвостовую рекурсию. Но это просто заметание сложности под ковер и никакой пользы такой трюк не дает.
я не говорил о какой-то пользе трюка. это и есть просто цикл, записанный через рекурсию
собственно, суть лишь в том, что всё можно записать через циклы и мутабельные переменные, можно аналогично реализовать с неизменяемыми переменными и хвостовой рекурсией — вопрос лишь в тяжести (да и в любом случае, компилятор это обратно соптимизирует в обычный цикл)
не буду говорить, что в этом есть хоть какая-то польза с точки зрения исполнения кода, но как нечто на подумать — это может быть забавным.
да и просто то, что рекурсия написана нехвостовая, когда её почти тривиально можно сделать таковой, всё равно кажется не самой приятной вещью
Это другой алгоритм.
Нет, это то же самое
Антирекурсия. Часть 1