Я надеюсь что это неожиданное название заставит вас обратить внимание на эту статью, но самое главное на что я надеюсь что прочитав эту статью вы уже не сможете так просто игнорировать факты.
Когда я учился программированию меня учили что рекурсия это плохо и нельзя надеятся что компилятор сможет заменить написанную тобой рекурсию на итеративный процесс. В какой то степени нас учили искать способ замены рекурсии итеративным алгоритмом(в те годы терминология была не очень проработана — понятия размыты). На сколько я понимаю замена рекурсии итеративным алгоритмом это одна из базовых задач программирования. Здорово когда она уже решена в компиляторе (в интерпретаторе) и в языке таком как диалект 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 до конца и прорешать примеры приведенные в этой книге не только на языке который используется в книге, но и на языке на котором вы работаете или собираетесь работать. Это очень хорошая книга и я не знаю книги в которой лучше определены и изложены базовые термины програмирования как способа описания реальных вычислительных задач (кодирования). Я сам когда-то учился на материалах из этой книги, но я не считаю способность переписать алгоритм с рекурсивными вызовами, алгоритмом на базе всем понятных циклов какой-то сверх способностью, доступной только разработчикам компиляторов.