Я надеюсь что это неожиданное название заставит вас обратить внимание на эту статью, но самое главное на что я надеюсь что прочитав эту статью вы уже не сможете так просто игнорировать факты.
Когда я учился программированию меня учили что рекурсия это плохо и нельзя надеятся что компилятор сможет заменить написанную тобой рекурсию на итеративный процесс. В какой то степени нас учили искать способ замены рекурсии итеративным алгоритмом(в те годы терминология была не очень проработана — понятия размыты). На сколько я понимаю замена рекурсии итеративным алгоритмом это одна из базовых задач программирования. Здорово когда она уже решена в компиляторе (в интерпретаторе) и в языке таком как диалект LISP-а который используется для примеров в книге известной под абревиатурой SICP, но в любом случае не помешает знание о том как эта задача решается. Как минимум это поможет вам лучше понимать работу компилятора и эффективнее его использовать.
Книга Structure and Interpretation of Computer Programs известна даже через аббревиатуру своего названия SICP. И хотя я ее раньше и не читал, прочитав ее я понял что меня когда-то учили на материалах из этой книги.
В часности из этой книги можно узнать про хвостовую рекурсию или как некоторый частный случай рекурсии заменить на итеративный процесс. Я совершенно согласен с автором книги по поводу того что рекурсия это, во многих случаях, очень удобный способ для формулировки вычислительных алгоритмов, особенно мне понравилась задача подсчета вариантов размена купюр монетами. Кстати единственная проблема этой задачи состоит в том что вам никогда и нигде не понадобится посчитать количество вариантов размена, это число никак не связано со стратегией, которая может применяться автоматом (кофе например) для поддержания способности этого автомата сдавать сдачу с покупок за наличные, например. Вообще в мире бизнеса (в мире купи-продай) самыми эффективными и востребованными являются самая примитивная арифметика и такие же тактика и стратегия.
К сожалению (а может к счастью) мир не так прост и задачи программирования не сводятся к задачам школьной арифметики или даже не так. Даже задачи уровня школьной арифметики при их комплексном и интегральном рассмотрении трансформируются в целые области научного знания. Чтобы в этом убедиться можно перечислить, например, методы вычисления квадратного корня из числа.
Знаете ли вы сколько существует способов вычисления квадратных корней и какая математика стоит за каждым из этих названий:
Метод Герона
Метод Бахшали
Посчитать цифру за цифрой
Экспоненциальное тождество
Итерационный метод с двумя переменными
Итерационные методы получения обратных квадратных корней
Ряд Тейлора
Продолжение дробь
Приближения, зависящие от представления с плавающей запятой
Отрицательный или комплексный квадрат
Я не думаю что можно найти человека который с легкостью сможет выбрать какой из методов применить в некотором гипотетическом алгоритме, который требует вычисления квадратного корня, хотя... Когда мне нужен был алгоритм (а лучше простая формула) для вычисления квадратного корня из целочисленного значения с датчика мощности в реальном времени в системе управления усилителем ВЧ мощности, я использовал табличную линейную апроксимацию функции квадратного корня. Это еще и упрощало задачу калибровки системы. Этот пример из моей практики говорит нам, что логика предметной области тоже не стремиться использовать самую заумную математику на практике, особенно в режиме вычислений в реальном времени.
Как говорится лучше одним выстрелом убить двух зайцев, чем разбивать процесс на итерации, первой из которых было бы только измерение скорости тех же зайцев, особенно, когда уже очень кушать хочется.
Но давайте все таки:
Вернемся к заявленной теме про хвостовую рекурсию.
Понятие о хвостовой рекурсии вводится в книге SICP со следующим примером на языке Scheme (диалект языка LISP) для реализации функции вычисления факториала числа
n! = n · (n − 1) · (n − 2) · · · 3 · 2 · 1.
Первый вариант реализации такой функции выглядит предельно компактно:
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))Но оказывается что такой вариант несмотря на компактность и очевидное преимущество с точки зрения так называемой читаемости или ясности для того, кто впервые посмотрит на этот код обладает рядом недостатков с точки зрения эффективности организации вычислений, чтобы понять в чем же заключаются эти недостатки нам предлагается альтернативная реализация функции:
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))Хотя это не конечный вариант, конечный вариант получается после применения некоторой оптимизации синтаксиса:
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))В чем же была проблема первой, самой компактной реализации алгоритма вычислений? Проблема в том что самая компактная запись выполняется самым неэффективным способом. Дело в том что машина которая выполняет вычисления, в этом случае выполняет эти вычисления по самому обобщенному сценарию просто разворачивает и "запоминает" строки рекурсии до конца, в книге вы сможете найти такую иллюстрацию процесса выполнения первой реализации алгоритма:
тогда как вторая и третья реализации выполняют те же самые вычисления гораздо более экономно с точки зрения количества операций которые должна выполнить машина для получения результата:
Если мы сравним эту реализацию на языке LISP с реализацией на языке Си и с циклом, что мы увидим:
int factorial(int n)
{
int res = 1;
int counter = 1;
while ( n > counter )
{
res *= counter;
counter += 1;
}
return res;
}
Так что же мы обнаружим? В Си-коде у нас пропал IF ! Дело в том что оператор цикла while это и есть на самом деле самый обычный оператор IF в сочетании с оператором безусловного перехода GOTO который всегда возвращает поток исполнения к этому самому IF переобозначенному как while.
Таким образом мы видим что в реализации на основе рекурсивных вызовов, рекурсивный вызов на самом деле надо рассматривать в комбинации с оператором ветвления IF, который и обеспечивает нам выход из рекурсии (из цикла рекурсии), а при наличии стандартных операторов цикла, эта комбинация заменяется единственным оператором цикла и принадлежащем этому циклу блоком кода (реализации итерации). Как видим в этом случае оператор цикла экономнее он заменяет как минимум две машинных операции (IF и goto), в то время как код с рекурсией требует явно писать тот же IF в сочетании с рекурсивным вызовом функции и определением этой самой функции.
Кто-то скажет что в Си коде мы должны явно декларировать-объявить переменные состояния алгоритма, но лично я не вижу ничего плохого в таком явном объявлении, мне кажется явные декларации позволяют лучше понимать намерения автора. Но вообще говоря в процедурном коде мы тоже объявляем переменную counter как параметер функции, а заменой переменной res там служит имя функции iter ведь функция возвращает значение и это значение занимает место в памяти, но нам не надо обращаться к этой ячейке памяти в коде напрямую, мы обращаемся к нему через имя функции которая его подставляет по месту своего вызова в коде. То есть в этом случае имя iter это и имя функции, и имя переменной в которой хранится значение, которое возвращает эта функция. Согласитесь объявление функции выглядит тяжелее чем объявление переменной в которую по факту трансформируется эта функция при выполнении.
Интересно что авторы этой книги объявляют начичие инструкций циклов (special-purpose “looping constructs” such as do, repeat, until, for, and while) фактически недостатком языка, так как
that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while.
Если перевести описание причины из цитаты, то она звучит примерно так:
Реализация языков общего назначения спроектирована таким образом что интерпретация (видимо компиляция в случае языка Си) рекурсивных процедур потребляет такое количиство памяти, которое увеличивается с увеличением количества рекурсивных вызовов, даже в том случае когда описанный (закодированный на данном языке) процесс, в принципе, итеративный, то есть просто циклический. То есть высказывается очень вывернутая наизнанку (на мой взгляд) претензия что для итеративных процесов, которые по определению циклические, в языках общего назначения существуют операторы организации циклов.
При этом выясняется что не любая рекурсия может быть выражена через итеративный процесс в терминах даннной книги, а только некоторое подмножество. И именно для рекурсивных алгоритмов из этого подмножества вводится термин tail-recursive или хвостовая рекурсия:
It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive.
При этом в сноске мелкими буквами вы можете прочитать что
Tail recursion has long been known as a compiler optimization trick. A coherent semantic basis for tail recursion was provided by Carl Hewi (1977)
то есть хвостовая рекурсия это на самом деле, дословно: «трюк компиляторной оптимизации». И я не думаю что умные слова далее вроде: когерентная семантическая основа была подведена под понятие хвостовой рекурсии Карлом Хеви в 77 году, что-то принципиально меняют в том факте что хвостовая рекурсия это всего лишь оптимизация компилятора.
Язык Си и его стандарт допускает наличие любой оптимизации в реализациях компиляторов, поэтому можно утверждать что стандарт языка Си уже давно разрешил реализацию такой оптимизации, проблема видимо в том что на языке Си просто не принято писать итеративные процессы через рекурсию, в языке Си очень удобно писать итеративные процессы с помощью явных операторов цикла. Видимо по этому разработчики компиляторов языка Си не озаботились созданием такой оптимизации. Кстати в компиляторах языка Си существуют некоторые виды оптимизаций которые не совместимы друг с другом, по этому даже если бы кто-то взялся сделать такого рода оптимизацию для языка Си, возник бы достаточно сложный вопрос о том насколько такая оптимизация эффективна на фоне уже существующих типов оптимизации.
Кстати, наличие ключевого слова inline в языке Си возможно, в каких-то случаях, способно решать проблему эффективной компиляции алгоритмов с хвостовой рекурсией. Возможно не нужно придумывать никакого специального флага оптимизации для компилятора, а достаточно пометить соответствующюю рекурсивно вызываемую функцию этим ключевым словом и тогда компилятор сможет догадаться что для этой функции в рамках этой рекурсии надо попробовать применить оптимизацию хвостовой рекурсии.
В любом случае я призываю всех внимательно прочитать эту книгу Structure and Interpretation of Computer Programs до конца и прорешать примеры приведенные в этой книге не только на языке который используется в книге, но и на языке на котором вы работаете или собираетесь работать. Это очень хорошая книга и я не знаю книги в которой лучше определены и изложены базовые термины програмирования как способа описания реальных вычислительных задач (кодирования). Я сам когда-то учился на материалах из этой книги, но я не считаю способность переписать алгоритм с рекурсивными вызовами, алгоритмом на базе всем понятных циклов какой-то сверх способностью, доступной только разработчикам компиляторов.
Комментарии (68)
vadimr
12.02.2025 04:58Реализация программ в машинном коде идёт от условных переходов, к которым близок цикл, а теория вычислений идёт от рекурсии. Поэтому цикл проще и естественнее практически, а рекурсия теоретически. Что касается человеческой привычки, то она формируется первым изученным языком программирования.
rukhi7 Автор
12.02.2025 04:58Что касается человеческой привычки, то она формируется первым изученным языком программирования.
ну не скажите! первым я изучал Basic (если не рассматривать коды на калькуляторе как язык :) ), практически парралельно Фортран и PL/1, еще Фокал, но родным(так сказать) я для себя ощущаю любой Си-подобный язык от чистого Си через С++, до C# и даже Java-код для меня прост и понятен с первого взгляда. Конечно более менее навороченные конструкции всегда требуют задуматься, но это уже не зависит от языка.
Вообще базовые конструкции во всех языках одинаковы, например рекурсия это уже производная конструкция основанная на операциях вызова функции и соответствующего синтаксиса для такого вызова который может отличаться в разных языках, но что-то что можно определить как функцию и соответственно как ее вызов есть в любом языке. Также как оператор цикла вызов функции может использоваться чтобы многократно возвращаться в одну и ту же точку в коде, то есть как средство управления потоком исполнения.
vadimr
12.02.2025 04:58Если в привычных вам языках рекурсия является производной конструкцией, то вы её и воспринимаете как таковую.
Я лично начинал изучения программирования в школе с языка Лого, в котором, как и в Scheme, рекурсия является основным механизмом организации циклических вычислений, а цикл в основном реализуется через рекурсию. Поэтому во многих случаях мне проще думать через рекурсию. Если же вы начинали со старого Бейсика и калькуляторных кодов, то конечно рекурсия является для вас крайне неестественным механизмом, искусственным наворотом поверх базовых конструкций.
rukhi7 Автор
12.02.2025 04:58Если же вы начинали со старого Бейсика и калькуляторных кодов
На сколько я понимаю Scheme постарше Бейсика будет. Вообще я начинал с алгебры Буля и схем на логических элементах в стиле VHDL, а еще раньше с таблицы умножения (впрочем как и вы наверно) если на то пошло.
vadimr
12.02.2025 04:58Я имел в виду Бейсик с номерами строк, где рекурсия невозможна в принципе.
rukhi7 Автор
12.02.2025 04:58действительно Бейсик был с номерами строк, мне кажется там все таки были функции, но я уже не помню можно ли было вызвать функцию из самой себя, но нас точно учили тогда так не делать. В школе дети послушные, особенно склонные к математике. Математика воспитывает дисциплину, хотя не запрещает задавать и задаваться вопросами.
vadimr
12.02.2025 04:58В бейсике с номерами строк не было функций в обычном понимании и, соответственно, не было и рекурсивного вызова. Там был оператор
GOSUB, делающий точно то же, что иcallв ассемблере, то есть просто переход с запоминанием адреса возврата.Что касается того, как вас учили, то это частное мнение вашего преподавателя. Лично я его не одобряю, и нас учили по-другому.
rukhi7 Автор
12.02.2025 04:58а теория вычислений идёт от рекурсии
я бы посмотрел как бы вы реализовали, например, Быстрое Преобразование Фурье (FFT) через рекурсию. А это такой хороший пример из теории построения таких практических сложных вычислительных алгоритмов. Теории бывают разные.
vadimr
12.02.2025 04:58Тут в русском языке есть нехорошая неоднозначность. Я говорю о вычислениях в смысле evaluation, а не calculation. То есть именно о теории вычислений, а не о вычислительной математики. Основа теории вычислений – это лямбда-исчисление и оператор неподвижной точки, из которого путём использования именованных функций получается рекурсия. Всё это крутится вокруг чисто синтаксических преобразований кода программы, к которым цикл не относится.
Вызов функции (в том числе и рекурсивный) чисто формально можно представить заменой её имени на её тело с заменой формальных параметров на фактические*. И нас при этом вообще не будет волновать семантика операторов, из которых она состоит. Просто синтаксическая подстановка. Поэтому в лямбда-исчислении бета-редукция не имеет семантики, это чисто синтаксическая операция.
А с циклом надо углубляться в его семантику.
А что касается БПФ, то любой циклический алгоритм элементарно реализуется с помощью рекурсии, это ничем не сложнее циклов. Конкретно на Scheme БПФ будет сложнее написать только из-за отсутствия матриц в ядре языка.
*) Встанет, правда, вопрос с аппликативным порядком вычислений, но это второе дело.
rukhi7 Автор
12.02.2025 04:58Я говорю о вычислениях в смысле evaluation, а не calculation.
ну это как раз из области той аналогии чтобы на охоте вместо того чтобы подстрелить зайца вы предлагаете начать с измерения скорости зайца, то есть вы предлагаете разделить процес на evaluation (измерение-анализ-оценки), и на calculation (собственно получение результата). Конечно измерение-анализ-оценки на практике тоже важны, но они уже в подавляющем большинстве приложений уже давно существуют их надо просто уметь использовать по моему.
Конкретно на Scheme БПФ будет сложнее написать только из-за отсутствия матриц в ядре языка.
я думаю реализация БПФ на Scheme просто не будет иметь смысла, так как оно не будет быстрым. Да вы смогли бы продемонстрировать универсальность применения рекурсии в том смысле что результат в конце концов получить можно, но в случае БПФ результатом является не только полученные числа, но и время (тоже кстати число в тиках например) за которые эти числа получены.
vadimr
12.02.2025 04:58А тут вас подводит уже неоднозначность английского языка. В наиболее общем смысле evaluation означает просто получение значения чего-либо. Ещё есть третье английское слово из этой же серии, computation.
я думаю реализация БПФ на Scheme просто не будет иметь смысла, так как оно не будет быстрым. Да вы смогли бы продемонстрировать универсальность применения рекурсии в том смысле что результат в конце концов получить можно, но в случае БПФ результатом является не только полученные числа, но и время (тоже кстати число в тиках например) за которые эти числа получены.
Если вы хотите получить наиболее быструю реализацию БПФ, то вам надо писать в машинных кодах (или воспользоваться готовой библиотекой, написанной в машинных кодах). В ней наиболее глубокие повторяющиеся вычисления будут выполняться векторными машинными командами, а более наружные – условными переходами. Понятно, что операторов цикла в машинном коде не будет.
rukhi7 Автор
12.02.2025 04:58Если вы хотите получить наиболее быструю реализацию БПФ, то вам надо писать в машинных кодах
а вы разве не знаете что
Современные оптимизирующие компиляторы,
как правило, не создают для хвостовой рекурсии дополнительные входы и выходы в функцию.умеют и оптимизацию для:
глубокие повторяющиеся вычисления будут выполняться векторными машинными командами
только все равно надо понимать (пример) когда они способны сделать тот или иной тип оптимизации, а когда нет. И надо понимать как это проконтролировать и как это поправить если что-то не получилось. А то получается что-то вроде:
вот я написал самую правильную рекурсию, а все тормозит потому что это компилятор не справился, напишите мне новый компилятор, который правильно понимает рекурсии.
vadimr
12.02.2025 04:58Конечно, чтобы писать эффективные программы, необходимо понимать, как именно реализуются на машине конструкции языка. Но это и к циклам относится в той же самой мере.
adeshere
12.02.2025 04:58> Но это и к циклам относится в той же самой мере.
Вот как раз на циклы все современные компиляторы натасканы круче некуда. Если эффективность не стоит на последнем месте, конечно. В том же фортране никому и в страшном сне не придет в голову заменять массивный оператор a=f(b), или a=b+c, где a, b и c- многомерные массивы, а f -
элементная функция
т.е. каждый элемент массива a = результат применения функции f к соответствующему элементу массива и b
на рекурсию. Мало того, что далеко не всякий фортранист с этим справится, так еще и машинный код с 99.9999%-ной гарантией получится в разы менее эффективным.
vadimr
12.02.2025 04:58Вы сами себе здесь противоречите. Пишете здравицу за циклы, а приводите в пример массивный оператор.
Если вы основываетесь на представлении, что для массивного оператора можно написать эквивалентный цикл
DO, то с тем же успехом для него можно написать и эквивалентную рекурсивную форму. А фактически он реализуется векторными машинными командами и условными переходами.А так всё зависит от конкретного языка и его реализации. В языке Scheme цикл является макроопределением над рекурсией.
adeshere
12.02.2025 04:58> Пишете здравицу за циклы, а приводите в пример массивный оператор.
Я бы тут с Вами не согласился. В моем представлении, массивный оператор - это именно форма записи цикла. Во всяком случае, абсолютно все знакомые мне программисты (причем не только пишущие на фортране!) воспринимают его именно так.
Я не сомневаюсь, что рекурсией его записать тоже можно. Вот только удобно ли? А главное, зачем? Напишите, для примера, рекурсию для двух-трехмерного массива - и сравните, какой код
легче понять среднестатистическому программеру/математику?
Я бы сам с удовольствием написал, но вряд ли сумею реализовать рекурсию оптимально. Поэтому мне правда интересно посмотреть на по-настоящему неплохую реализацию
Я уж не говорю, что если вдруг компилятор окажется недостаточно умным, и вдруг все-таки реализует рекурсию через call, то на одной только передаче параметров (которая в фортране реализована максимально эффективно!) мы сразу проиграем не проценты, а много крат.
А распознать ее ему будет очень непросто, так как массивный оператор (=цикл) может оказаться гораздо более хитрым, чем приведенные выше тривиальные примеры. В том неидеальном мире, где я живу, я вот сплошь и рядом использую, например, массивный оператор where для отсечения Nan-значений. В комбинации с другими массивными операторами в не очень простых выражениях (и это мы еще про сечения массивов не вспомнили).
И если циклами я это все еще могу более-менее расписать, то аналогичный код на рекурсии - даже не представляю, сколько сил и времени может отнять. Его же надо не только написать, но еще и отладить. Я конечно верю, что специалисту все это - раз плюнуть. Но мы же сейчас говорим о
среднестатистическом программисте?
У которого, разумеется, есть в том числе и какой-то практический опыт с рекурсией. Лично у меня в таком стиле работа с файловой системой закручена. Ну и плюс к этому еще 500 тысяч строк лично написанного кода в продакте (работающих прямо сейчас). На основании чего я все-таки наберусь наглости выдвинуть свою кандидатуру на должность этого самого "среднего" программиста. Для которого цикл:
а) на порядок естественнее и понятнее, и
б) при решении реальных задач позволяет писать гораздо более эффективный кодА в остальном Вы, конечно же, правы.
vadimr
12.02.2025 04:58Я бы тут с Вами не согласился. В моем представлении, массивный оператор - это именно форма записи цикла. Во всяком случае, абсолютно все знакомые мне программисты (причем не только пишущие на фортране!) воспринимают его именно так.
Это говорит только о том, что Вы и ваши друзья привыкли представлять себе массивный оператор таким образом.
Вот три программы, о которых Вы говорили:
program m1 integer, parameter :: s = 512 real (8), allocatable, dimension (:,:,:) :: a, b, c allocate (b(s,s,s), c(s,s,s)) call random_number (b) call random_number (c) a = b+c print *, (sum(a)) end program m1program m2 integer, parameter :: s = 512 real (8), allocatable, dimension (:,:,:) :: a, b, c integer :: i,j,k allocate (b(s,s,s), c(s,s,s)) call random_number (b) call random_number (c) allocate (a(s,s,s)) do k=1,s do j=1,s do i=1,s a(i,j,k) = b(i,j,k)+c(i,j,k) end do end do end do print *, (sum(a)) end program m2program m3 integer, parameter :: s = 512 real (8), allocatable, dimension (:,:,:) :: a, b, c integer :: i,j,k allocate (b(s,s,s), c(s,s,s)) call random_number (b) call random_number (c) allocate (a(s,s,s)) call recsum(a, b, c, s, s, s) print *, (sum(a)) contains pure recursive subroutine recsum (a, b, c, i, j, k) real (8), dimension (s,s,s) :: a, b, c integer :: i, j, k intent (in) :: b, c, i, j, k intent (out) :: a if (i==0) then return else if (j==0) then call recsum (a, b, c, i-1, s, s) else if (k==0) then call recsum (a, b, c, i, j-1, s) else a(k,j,i) = b(k,j,i)+c(k,j,i) call recsum (a, b, c, i, j, k-1) end if end if end subroutine recsum end program m3
adeshere
12.02.2025 04:58> Вот три программы, о которых Вы говорили:
Спасибо, действительно интересно!
Мне конечно сложно оценивать, так как я и мои друзья правда "...привыкли представлять себе массивный оператор таким образом". Но на мой субъективный вкус, тройной цикл в программе m2 все-таки попонятнее, чем нанизанные if - else в m3. Поэтому было бы очень интересно узнать: а как оценивается этот код с точки зрения человека, привыкшего к рекурсивной форме выражения мыслей?
> Но проблема в том, что gfortran не понимает, что здесь рекурсия хвостовая.
Давайте все-таки разделим два эти вопроса? Или даже точнее три:
1) Читаемость и понятность кода с точки зрения типичного программиста
2) Способность конкретного компилятора эффективно оптимизировать рекурсивные вызовы
3) Насколько пострадает задача (1), если мы будем вынуждены искусственно помогать компиляторусправиться с (2)?
допустим, он такое умеет
Мое субъективное мнение:
1) Циклы все же понятнее (Но! это зависит от "воспитания" и предыдущего опыта);
2) Компилятору наверное проще оптимизировать цикл, чем рекурсию?
3) Если такая задача становится актуальной, значит выбран не самый подходящий для данного случая язык программированияНу и конечно, наилучшим решением задач (1) и (3) я по-прежнему считаю массивные операторы. А задачу (2) компилятору в этом случае вообще не нужно решать ;-).
vadimr
12.02.2025 04:58С моей точки зрения, если вам надо сложить два трёхмерных массива, то надо брать Фортран и массивный оператор a=b+c и не выпендриваться, так как это инструмент, специально предназначенный для решения этой задачи. А писать рекурсивные подпрограммы на Фортране – извращение, даже притом, что я люблю и ценю рекурсию как способ выражения своих мыслей. В каждом языке существует определённая идиоматика и культура написания кода.
Я с Вами полностью согласен в том, что массивный оператор в данном случае самый понятный, за ним идёт тройной цикл, а замыкает рейтинг понятности рекурсивный вызов. Но! Я спорил и продолжаю спорить с тем, что массивный оператор является представлением именно цикла. В моём понимании, здесь представлены три разные операционные формы представления одной и той же денотационной семантики операции сложения массивов, и нельзя сказать, что цикл как-то сущностно ближе к массивному оператору, чем рекурсия.
Например, массивный оператор не обязан внутри себя выполняться последовательно, и это подрывает его операционную связь как с циклическим, так и с рекурсивным алгоритмом.
А для компилятора в принципе что цикл, что рекурсия – один фиг. Другое дело, что компилятор Фортрана гораздо больше ориентирован на оптимизацию циклов, чем рекурсивных вызовов, по чисто прагматической причине.
adeshere
12.02.2025 04:58> Например, массивный оператор не обязан внутри себя выполняться последовательно
Кстати, да! Что резко расширяет свободу компилятора оптимизизировать или распараллеливаать вычисления,
> и это подрывает его операционную связь как с циклическим, так и с рекурсивным алгоритмом.
Но тогда получается, что оптимизация рекурсивного алгоритма - это на порядок более сложная задача для компилятора, чем даже оптимизация цикла?!
> А для компилятора в принципе что цикл, что рекурсия – один фиг.
Если моя гипотеза выше (в прошлой фразе) верна, то совсем даже нет. Как только мы начинаем оптимизацию, будет две больших разницы?
> Другое дело, что компилятор Фортрана гораздо больше ориентирован на оптимизацию циклов, чем рекурсивных вызовов, по чисто прагматической причине.
А вот тут я бы не подписался безоговорочно. С одной стороны, спору нет: циклы конечно встречаются чаще и оптимизировать их важнее. Но может быть, есть и вторая сторона медали, что оптимизировать циклы банально проще?
vadimr
12.02.2025 04:58Но тогда получается, что оптимизация рекурсивного алгоритма - это на порядок более сложная задача для компилятора, чем даже оптимизация цикла?!
Почему?
adeshere
12.02.2025 04:58Но тогда получается, что оптимизация рекурсивного алгоритма - это на порядок более сложная задача для компилятора, чем даже оптимизация цикла?!
> Почему?
Я не специалист по компиляторам, поэтому никаких серьезных обоснований у меня нет. Просто есть такое впечатление, основанное на том, что в цикле все прописано в явном виде, а рекурсию надо распознавать и раскручивать. Взять, например , количество итераций: многие формы записи цикла позволяют его определить сразу при входе в цикл. При итеративной записи даже в самом простейшем случае компилятору придется задуматься. А еще, если в коде есть этот самый call, то это уже получается межпроцедурная оптимизация, что по идее сложнее. Особенно когда этих вложенных вызовов несколько...
В общем, определенные причины так думать у меня есть, но не более того. Для получения обоснованного ответа надо
вызывать чистильщикаобращаться к специалисту по компиляторам. Такому, как уже упомянутый здесь уважаемый @xortator. Ну или может еще кто-то откликнется?
IUIUIUIUIUIUIUI
12.02.2025 04:58Компилятору наверное проще оптимизировать цикл, чем рекурсию?
Компилятору проще оптимизировать то, смысл чего он «понимает». При этом даже loop-invariant code motion можно делать не всегда, потому что не факт, что цикл выполнится хотя бы один раз, и не факт, что у LICMнутого выражения нет сайд-эффектов.
А про рекурсию и свёртки есть конкретные математические теоремы, которые показывают, когда конкретно их можно объединять или делать другие преобразования, тогда как операции над циклами — это всегда эвристики.
Конечно, тут смешиваются различия между циклами/рекурсией и чистотой/эффектами, но циклы по своей природе требуют мутации, поэтому это смешение чуть более оправдано, чем может показаться.
vadimr
12.02.2025 04:58Но проблема в том, что gfortran не понимает, что здесь рекурсия хвостовая.
Конечно, фортрановский компилятор по своей природе не предназначен разматывать рекурсию.
vadimr
12.02.2025 04:58Естественно, что цикл и массив – близнецы-братья, и сложение матриц естественнее писать в виде цикла. Но, например, обход мультисписка вы немного замучаетесь делать на циклах. Как Вы сами и говорите про работу с файловой системой.
vadimr
12.02.2025 04:58Если убрать множественные рекурсивные вызовы, дурящие голову компилятору Фортрана, и оставить одномерный массив такого же размера:
program m0 integer, parameter :: s = 512*512*512 real (8), allocatable, dimension (:) :: a, b, c allocate (b(s), c(s)) call random_number (b) call random_number (c) allocate (a(s)) call recsum(a, b, c, s) print *, (sum(a)) contains pure recursive subroutine recsum (a, b, c, i) real (8), dimension (s) :: a, b, c integer :: i intent (in) :: b, c, i intent (inout) :: a if (i==0) then return else a(i) = b(i)+c(i) call recsum (a, b, c, i-1) end if end subroutine recsum end program m0то тогда компилятор понимает, что рекурсия является хвостовой, и время работы всех трёх программ оказывается равно между собой.
adeshere
12.02.2025 04:58> Если убрать множественные рекурсивные вызовы, дурящие голову компилятору Фортрана, и оставить одномерный массив такого же размера (...) то тогда компилятор понимает, что рекурсия является хвостовой, и время работы всех трёх программ оказывается равно между собой.
Вот в этом-то и проблема. В реальной жизни часто встречаются всякие прибамбасы, которые могут кому угодно запудрить мозги. Моя гипотеза - что обычно компилятору сложнее разобраться в рекурсивной записи, чем в нерекурсивной. Или нет?
Недавно здесь на Хабре был замечательный цикл статей про оптимизирующие компиляторы от уважаемого @xortator. В том числе, там довольно подробно рассматривались циклы и их "размотка". Если вдруг этот мудрый человек нас сейчас слышит, было бы очень интересно узнать его мнение по этим вопросам.. Пожалуйста...
AlexAiZzz
12.02.2025 04:58Учитывая, что оптимизация выполняется в несколько проходов, то компилятор сначала задетектит хвостовую рекурсию (что относительно легко), потом развернет цикл. Может даже больше:
// Type your code here, or load an example. int factorial(int n) { if (n == 1) return 1; else return n * factorial(n - 1); } int main() { return factorial(5); }factorial: mov eax, 1 cmp edi, 1 je .L1 .L2: mov edx, edi sub edi, 1 imul eax, edx cmp edi, 1 jne .L2 .L1: ret main: mov eax, 120 retСм. предпоследнюю строку, где функция даже не вызывается, а заменяется вычисленным во время компиляции значением..
adeshere
12.02.2025 04:58См. предпоследнюю строку, где функция даже не вызывается, а заменяется вычисленным во время компиляции значением..
$-)
Да, конечно ;-) Но это все-таки довольно простой случай. А мне хочется понять, что произойдет по мере накопления сложности? Есть подозрение, что на каком-то уровне сложности (например, если в вычислениях задействовано много функций, и не все они "чистые", ну или еще почему-то), компилятор перестанет воспринимать задачу в целом, и вместо полной оптимизации ограничится локальными улучшениями кода. Гипотеза состоит в том, что при записи одного и того же алгоритма через циклы и через рекурсию в последнем случае этот момент наступит раньше.
Но, это именно мое "подозрение" и "гипотеза". А вот как оно реально работает - я бы сам очень хотел узнать.
Дисклеймер
Главное - это не забывать, что в действительности все не так, как на самом деле (с). На заре моей компьютерной молодости это было моим девизом ;-)
UPD
Я этой фразой много лет пользовался, не зная, кто автор (дело было еще до интернета). А недавно открыл, что это Станислав Ежи Лец. Хорошо топтать плечи гигантов! ;-)
IUIUIUIUIUIUIUI
12.02.2025 04:58Я в хаскеле спокойно пишу условный
mapM_/forM_, который, вообще говоря, реализован рекурсией-свёрткой, да ещё и абстрактно поверх любого тайпкласса Foldable. И ничего, получаю производительность на уровне C++. Функциональные компиляторы натасканы на рекурсию так же, как императивные — на циклы.rukhi7 Автор
12.02.2025 04:58А вы попробуйте Быстрое Преобразование Фурье в хаскеле написать с производительностью на уровне С++, вот это будет номер!
Только учтите что вам на слово никто не поверит что вы уже написали, желательно графики продемонстрировать.
IUIUIUIUIUIUIUI
12.02.2025 04:58Я многие другие вещи писал (и писал о некоторых из них на хабре), от расстояния Левенштейна до разных регулярок. Вполне себе плюсовая производительность.
БПФ что на хаскеле, что на плюсах я буду писать не явными поэлементными циклами, а с использованием векторных примитивов.
AlexAiZzz
12.02.2025 04:58В том же фортране никому и в страшном сне не придет в голову заменять массивный оператор a=f(b), или a=b+c, где a, b и c- многомерные массивы, а f - на рекурсию.
Я кажется понял в чем проблема в дискуссии :)
"Человек купивший себе молоток везде видит гвозди" :)
Надо же идти от задачи к выбору о том как ее записывать: если задача легче "решается" (в смысле понимается мозгом) итеративно, то и надо выбирать итеративную форму, но большой класс задач легче воспринимается в рекурсивном виде (декларативный подход, пишем что "что" решаем, вместо "как"), и если компилятор помогает в хвостовой рекурсией, то ее в таком виде ее и надо записывать. А часть задач в итеративный вид и не перевести (легко), и вам так или иначе придется эмулировать стек в этом случае (т.е. "закат солнца вручную"), что только затруднит понимание собственного кода.
Dooez
12.02.2025 04:58БПФ же как раз определен через рекурсию, реализовать его рекурсивно вовсе не сложно.
Я бы даже сказал что через рекурсию он понятнее, но это обсуждаемо.
vadimr
12.02.2025 04:58Согласитесь объявление функции выглядит тяжелее чем объявление переменной в которую по факту трансформируется эта функция при выполнении.
В языке Scheme, использующемся в SICP, это одно и то же.
И, собственно, там и необязательно объявлять функцию для использования рекурсивного вызова. Можно обойтись примитивной рекурсивной формой
letrec. Просто примеры даны более многословно для лучшего восприятия.rukhi7 Автор
12.02.2025 04:58Можно обойтись примитивной рекурсивной формой letrec.
так а я о чем: чтобы реализовать цикл - то есть повторное выполнение сегмента кода нужна какая то иструкция ветвления и инструкция возврата в исходную точку, функция обеспечивает возврат, но не обеспечивает ветвление поэтому нужна некоторая специальная конструкция-ключевое слово которая объединяет вызов функции и условие для ветвтления.
А в более поздних языках появились операторы цикла для этой цели потому что использование функции для возврата сопряжено с избыточными накладными расходами памяти и производительности, потому что чтобы вернуться из функции в нее еще надо войти.
vadimr
12.02.2025 04:58Если в вашей реализации языка хвостовой рекурсивный вызов функции сопряжён с какими-то дополнительными расходами памяти и производительности, то это дефект реализации и ничего больше. Именно потому, что, во-первых, хвостовая рекурсия эквивалентна циклу, а во-вторых, её легко распознать. Современные оптимизирующие компиляторы, как правило, не создают для хвостовой рекурсии дополнительные входы и выходы в функцию. Собственно, если рассматривать дело с точки зрения машинного кода, то и так понятно, что пара команд
call/retпрагматически эквивалентнаjmp.В каких-то реализациях языков вход в каждый инстанс рекурсивной функции может подразумевать небесплатное создание нового контекста, но ведь и каждая итерация цикла потенциально может это делать (например, если в языке PL/I поместить внутрь цикла begin-блок). Это не вопрос рекурсии и цикла самих по себе.
rukhi7 Автор
12.02.2025 04:58и так понятно, что пара команд call/ret прагматически эквивалентна jmp.
на самом деле эквивалентной jmp командой является только call, именно call позволяет нам вернуться в начало функции, ret и все что с ним связано (загрузка выгрузка контекста) как раз является не нужным довеском в таком случае и, соответственно, является проблемой.
На самом деле call это и есть jmp только с дополнительной нагрузкой (а icall, это расширенный ijmp).
vadimr
12.02.2025 04:58Я говорю о том, что пару непосредственно следующих друг за другом команд
call f / ret, представляющую собой реализацию в машинном языке окончания хвостово-рекурсивной функции (рекурсивный вызов и потом сразу выход), прагматически можно заменить на одну командуjmp, что и называется собственно элиминацией хвостовой рекурсии при кодогенерации. Это не совсем формально эквивалентно, потому что параcall/retещё оставит адрес возврата над верхушкой стека, что в машинном коде иногда используется для определения своего адреса, но в прагматическом случае обычного рекурсивного вызова так можно сделать.rukhi7 Автор
12.02.2025 04:58представляющую собой реализацию в машинном языке окончания хвостово-рекурсивной функции (рекурсивный вызов и потом сразу выход)
тут я что-то не понял! Как это: "потом сразу выход"? Потом сразу код функций по новой и новый рекурсивный вызов, выходы будут когда-то потом, если будут.
Я на ассемблерах очень много писал, по машинным языкам меня не запутаешь.
vadimr
12.02.2025 04:58Ну вот вы в своей статье привели код на Scheme:
(define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1))))Если писать на ассемблере, то это будет что-то вроде (предполагая, что counter, n и product лежат в регистрах и, соответственно, являются именами регистров):
iter cmp counter, n bgt exit mul product, counter inc counter call iter exit retСтроки 5 и 6 (пара call/ret) – это собственно реализация хвостовой рекурсии. И их можно заменить просто одним оператором
jmp:iter cmp counter, n bgt exit mul product, counter inc counter jmp iter exit retчто в точности соответствует реализации цикла с предусловием.
rukhi7 Автор
12.02.2025 04:58Строки 5 и 6 (пара call/ret) – это собственно реализация хвостовой рекурсии. И их можно заменить просто одним оператором jmp
вы видимо так увлеклись идеей переубедить меня, что, кажется не заметили что вы заменили только call на jmp!
retостался на месте :) !Это такая психологическая ловушка когда ты кого-то хочешь убедить в чем то, перестаешь критически оценивать материал, я сам часто ловлю себя на том что попадаюсь. Это видимо предрасположенность людей которые работают с текстовыми абстракциями.
vadimr
12.02.2025 04:58Это вы невнимательны.
ret, оставшийся в коде – это цель условного перехода, не имеющая отношения к реализации рекурсивного вызова. Если тупо формально писать, то в первом случае в программе должно было бы быть две командыretдруг за другом, потому что фактически из-за хвостовой рекурсии выход из функции происходит независимо в двух ветках формыif. Но можно было сэкономить.rukhi7 Автор
12.02.2025 04:58ну да я попал в ту же ловушку - думал о своем! Вы меня все таки запутали :) .
Просто надо было тогда код полностью писать:
с рекурсией:
iter: cmp counter, n bgt exit mul product, counter inc counter call iter exit: ret factorial: set counter, 1 set n, param call iter set acc, counter//значение надо вернуть каким то стандартным способом retбез рекурсии
factorial: set counter, 1 set n, param iter: cmp counter, n bgt exit mul product, counter inc counter jmp iter exit: set acc, counter retвсе равно ret это довесок к call, действительно без call не нужен ret, только еще код итерации надо заинлайнить.
Все равно , с точки зрения порядка исполнения jmp заменяет только call,
ret заменяется как раз тем что блок кода инлайнится по месту формального вызова. Если бы мы оставили блок итерации вне кода основной функции нам бы понадобился второй jmp.
vadimr
12.02.2025 04:58jmp чисто формально не может заменить только call, так как одним из результатов выполнения call является рост стека. Так что где-то должен быть и ret для обратного уменьшения стека. И вот, в хвостовой рекурсии ret как раз и написан сразу после call.
Я хочу сказать только то, что коды команд call и ret, следующие в тексте программы сразу друг за другом, вместе прагматически эквивалентны одному jmp.
rukhi7 Автор
12.02.2025 04:58Теперь я хотя бы понял про что вы толкуете. С этим можно согласиться в общем.
Только в частности надо иметь в виду пример о том что когда мы подставляем вместо вызова функции (обычной не рекурсивной) ее тело, у нас call и ret просто исчезают, то есть ни на что не заменяются, то есть с точки зрения машины это, в каком то смысле, всегда избыточные операции.
adeshere
12.02.2025 04:58> На самом деле call это и есть jmp только с дополнительной нагрузкой (а icall, это расширенный ijmp).
Именно что!
Я не могу сейчас сгенерировать пример кода, чтобы проверить, распознает ли компилятор рекурсию,
и заменит ли циклом
дело даже не в том, что нет времени, но у меня компилятор 2008 года, так что ответ про современные компиляторы мы все равно не получим
Но когда-то давно я в учебных целях экспериментировал с рекурсивными вызовами в фортране. И машинный код при любом уровне оптимизации получался гораздо хуже. Собственно, не потому ли на протяжении всей моей жизни перемалыватели чисел пишутся на тех языках, где базовая структура - цикл? А рекурсия представляет собой скорее
синтаксический сахарполезную нишевую фичу для особых задач, чем базовый элемент языка, без которого все остальное рассыпается вдребезги пополам?AlexAiZzz
12.02.2025 04:58Тот же gcc вполне себе распознает хвостовую рекурсию уже достаточно давно, нужно лишь указать тип оптимизации, работает при -O2 и -O3 как минимум
Пожалуйста с codebolt для факториала:
factorial(int): mov eax, 1 cmp edi, 1 je .L1 .L2: mov edx, edi sub edi, 1 imul eax, edx cmp edi, 1 jne .L2 .L1: retОн еще и проверку базового случая продублировал в конце цикла, видать так еще быстрее.
AlexAiZzz
12.02.2025 04:58И это переведено не верно:
that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while.
Тут говорится о том, что в языках типа С, у которого непрописанно в стандарте обязательной оптимизации хвостовой рекурсии в отличие от той же Scheme, вам приходится отказываться от рекурсивной записи алгоритма. Т.е. фактически приходится самому проводить эту оптимизацию, переписывая алгоритм в итеративной форме т.е. прибегая к различным формам циклов.
rukhi7 Автор
12.02.2025 04:58тут интересно кстати что будет если ИНТы заменить на шорты (чтобы долго не ждать как для ИНТа) и вызвать для числа для которого факториал выходит за пределы шорта чтобы уже в процессе вычисления все вышло за пределы шорта - я думаю тоже посчитает, но с соответствующей ошибкой.
AlexAiZzz
12.02.2025 04:58Если речь про ассемблерный код, что я привел, то там нет никакой обработки переполнения, поэтому он тупо будет считать некорректно после этого, т.к. начнет умножать на огрызок от переполненного значения.
IUIUIUIUIUIUIUI
12.02.2025 04:58Распознавать-то распознаёт, только иногда делает с этим адовую ерунду, когда там требуются какие-то дополнительные оптимизации: https://gcc.godbolt.org/z/bh6Gx5hxq
Мне лень по ассемблеру строить полный call graph, но у clang есть хотя бы один рекурсивный путь с
call, а gcc делает что-то либо очень гениальное, либо очень тупое для-DSHITTY_CODEGEN-случая (и там тоже есть какие-то рекурсивные пути сcall— gcc'шный кодген мне понимать сильно тяжелее, чемclangовский в этом случае).При этом аналогичный
SHITTY_CODEGENу (с паттерн-матчингом и вот этим всем) ФП-код компилируется в хвостовую рекурсию без всяких вызовов, как и ожидается.
viordash
12.02.2025 04:58вероятно у вас в сишном коде ошибка, должно быть
while( counter <= n)rukhi7 Автор
12.02.2025 04:58спасибо, поправил!
while( n > counter)мне больше нравится.AlexAiZzz
12.02.2025 04:58Ну и кстати ближе к исходному определению факториала будет:
int factorial(int n) { int accumulator = n; while (--n) { accumulator *= n; } return accumulator; }rukhi7 Автор
12.02.2025 04:58вот интересно это язык Си такой что побуждает тех кто на нем пишет доводить код до совершенства или это те кто останавливают свой выбор на Си подобных языках имеют предрасположенность доводить код до совершенства?
Кажется вопрос еще ждет своего увлеченного исследователя.
AlexAiZzz
12.02.2025 04:58Про совершенство я не знаю :)
Но тот код, что я привел, просто соответствует тому рекурсивному определению, в которое развернется хвостовая рекурсия. Т.е. это раскрытие (всегда?) приводит к циклу с накопителем. Вариант со второй переменной (счетчиком) соответствует факториалу в записи:
AlexAiZzz
12.02.2025 04:58вот интересно это язык Си такой что побуждает тех кто на нем пишет доводить код до совершенства или это те кто останавливают свой выбор на Си подобных языках имеют предрасположенность доводить код до совершенства?
Кажется вопрос еще ждет своего увлеченного исследователя.
Кстати, наверное на это вопрос могу ответить :)
Я язык не выбирал :) это сделали Вы, а я отвечал на том же.
Так то я очень хорошо отношусь ко многим языкам, начиная с ассемблера, си, паскаля и их некоторых продолжателей, и продолжая лиспо-подобыными, да и вообще функциональными, и включая и такие "странные" как форт. Правда я пока не понял как можно применять Хаскель на практике, но думаю и с этим я разберусь :)
rukhi7 Автор
12.02.2025 04:58вы еще декларативные языки забыли (видимо) упомянуть. XSLT вот например очень интересно работает, причем работает на практике!
AlexAiZzz
12.02.2025 04:58Ну данном случае, этот декларативный язык не является языком программирования. Хотя это и не отменяет его прикольности. Вот декларативный пролог, это да. Но вот ему в дальнейшем я применений не вижу, хотя он и позиционировался когда-то как язык 4го поколения.
Timick
12.02.2025 04:58Перемножение на единицу тут вижу я.
AlexAiZzz
12.02.2025 04:58В каком месте?
Timick
12.02.2025 04:58когда n==1
AlexAiZzz
12.02.2025 04:58А, с этой точки зрения. Ну так я не оптимизировал код, он и в определения факториала умножает на единицу. Но на самом деле в коде все равно будет переход по сравнению с нулем и чтобы и не умножать на 1, перед переходом будет сравнение с 1, что будет делаться во внутрях через вычитание. Умножение на 1, как на нейтральный элемент скорее всего будет выполняться достаточно эффективно, так что я тут без измерений не буду утверждать что будет быстрее: вычесть единицу на каждой итерации или один раз умножить на 1. Зависит оттого что реализовано в схемотехнике. Вполне вероятно зависит от n.
rukhi7 Автор
12.02.2025 04:58я тоже об этом подумал, но потом подумал что заменять сравнение с нулем на сравнение с 1 испортит совершенство :). Эфект от введения константы в ассемблер может перекрыть эффект от лишнего умножения. Как минимум эти эффекты можно рассматривать как сравнимые по затратам производительности в некоторых случаях, поэтому разницей можно пренебречь, по моему.
Jijiki
12.02.2025 04:58рекурсии и фракталы ) пока делится идёт рекурсия ) интересно будет так работать? или будет упор в стек (просто предположил возможно без рекурсии наверно, я в этом не силён )
Timick
Не вижу проблем с рекурсией если количество вызовов строго ограниченно. В противном случае можно оказаться в call stack overflow. Ну это будет сильно дурацкая имплементации как в задаче заливки фигуры.
vadimr
Ну собственно как и с любым другим алгоритмом, бесконтрольно выделяющим память.