Действительно ли рекурсия Tail действительно эффективна на языке C?

Я думаю, что Tail-recursive действительно полезен в функциональном языке программирования. Как насчет С?

  • Поддерживает ли язык C или компилятор устранение хвостовых вызовов?
  • Создает ли программа новый кадр стека для нового вызова?

Из вики:

Хвостовые вызовы могут быть реализованы без добавления нового кадра стека в стек вызовов. Большая часть фрейма текущей процедуры больше не нужна, и ее можно заменить фреймом хвостового вызова, соответствующим образом модифицированным (аналогично оверлею для процессов, но для вызовов функций).

Затем программа может перейти к вызванной подпрограмме. Создание такого кода вместо стандартной последовательности вызовов называется удалением хвостовых вызовов.


c tail-recursion
person Ngo Thanh Nhan    schedule 02.02.2016    source источник
comment
Дело не в C, а в конкретных компиляторах. Большинство современных компиляторов могут оптимизировать хвостовую рекурсию.   -  person Eugene Sh.    schedule 02.02.2016
comment
Вы понимаете, что та же самая страница википедии, на которую вы ссылаетесь, дает вам примеры хвостовой рекурсии в C, верно?   -  person AntonH    schedule 02.02.2016
comment
Это похоже на вопрос мнения, но идентификация и устранение хвостовой рекурсии очень полезны в любом рекурсивном приложении, включая C, поскольку они позволяют вам выполнять операции, которые в противном случае были бы ограничены размером стека.   -  person David Hoelzer    schedule 02.02.2016
comment
Я работаю над микроконтроллером с небольшим объемом оперативной памяти. Хвостовая рекурсия может упростить реализацию, но stackoverflow   -  person Ngo Thanh Nhan    schedule 03.02.2016

Ответы (4)


arrow_upward
1
arrow_downward

Стандарт C вообще не определяет хвостовую рекурсию как часть языка. Единственное, что стандарт C99 говорит о рекурсивных вызовах функций:

6.5.2.2 Вызовы функций

11 Должны быть разрешены рекурсивные вызовы функций, как прямо, так и косвенно через любую цепочку других функций.

Если компилятор может обнаружить хвостовую рекурсию и преобразовать рекурсивный вызов как хвостовую рекурсию, он может, но не обязан делать это по стандарту.

person R Sahu    schedule 02.02.2016

arrow_upward
4
arrow_downward

Хвостовая рекурсия обычно используется в функциональных языках, потому что это естественный способ реализации циклов в структурах, которые на самом деле не так уж рекурсивны в процедурных языках.

Поэтому процедурные языки в этом не нуждаются. Однако компилятор должен решить, найдет ли он такую ​​оптимизацию.

person Zbynek Vyskovsky - kvr000    schedule 02.02.2016

arrow_upward
2
arrow_downward

Ни стандарт C, ни компиляторы не должны поддерживать хвостовую рекурсию. Реализация определяет, поддерживает ли компилятор хвостовую рекурсию.

person Vlad from Moscow    schedule 02.02.2016
comment
Что вы имеете в виду под опорами? Это способ написания функций. Компилятор может обнаружить это и развернуть. Или не может. - person Eugene Sh.; 02.02.2016
comment
@ЕвгенийШ. Я имею в виду, что нет необходимости, чтобы компилятор действительно генерировал объектный код, соответствующий хвостовой рекурсии. - person Vlad from Moscow; 03.02.2016

arrow_upward
1
arrow_downward

ANSI (стандарт) C не требует хвостовой рекурсии. Большинство компиляторов C реализуют его, потому что оптимизация не очень сложна и обеспечивает огромную экономию в стеке и кэш-памяти.

Однако язык C до ANSI определенно поддерживал хвостовую рекурсию. Это было сделано с помощью goto:

fact(n,m) { m =+ n; n--; if(n) goto fact; return n; }

Обратите внимание на другие странности: += записывается как =+, а int используется по умолчанию для всех переменных. Примеры исходного кода pre-ansi C сейчас редкость, но v6 ed.c в частности использует этот метод для обработки ошибок.

person geocar    schedule 02.02.2016
comment
в чем разница между =+ и += ? - person Ngo Thanh Nhan; 03.02.2016
comment
x+=y было записано как x=+ y (обратите внимание на пробел) - person geocar; 18.02.2016