Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / C++ Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
 Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Привет друзья.

Илья. Сов. Саша. Зяма. Дима. И все-все другие мемберы.

Давайте поговорим про хорошие сценарии использования рекурсий в С++.
Степанов в своей книге различает "хвостовую" и "строгую хвостовую рекурсию".

У меня соотв. Вопросы. В каких случаях она не детектируется и код будет собран как чисто-рекурсивный?

Спасибо всем.

Ваш покорный слуга
mayton
15 дек 17, 22:13    [21038417]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
White Owl
Member

Откуда:
Сообщений: 12682
Зависит от умности оптимизатора. Но чаще всего, только строгая разворачивается в цикл.
16 дек 17, 00:01    [21038598]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
White Owl
Member

Откуда:
Сообщений: 12682
последний раз я это ковырял в третьем gcc лет пять назад, и классический пример не разворачивался.
int fact(n) {
  if (n==0) return 1;
  return n * fact(n-1);
}
16 дек 17, 00:05    [21038606]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6422
https://godbolt.org

Ставим для gcc что нибудь типа -O2 -m32
16 дек 17, 09:20    [21038830]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
x0n1x
Guest
сорри, Степанова не читал,
но всегда думал, что "оптимизация хвостовой рекурсии" может быть сделана уже на уровне машинного кода тупой заменой
CALL xxx
RET
на
JMP xxx
(если мы знаем, что xxx - адрес начала этой же функции)

на уровне генерации машинного кода такая замена явно не сложнее
22 дек 17, 11:42    [21054747]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34688
Я вообще не знаю за Степанова, за строгую хвостовую рекурсию, но
оптимизироваться она может просто за счёт "схлопывания" фрейма стека: вместо того, чтобы при вызове функции
делать новый фрейм с пермеменными, новый вызов может использовать старый фрейм со старыми переменными, переписав их новыми значениями, если нужно.

Это ка бы не цикл, но эффективно как цикл.
22 дек 17, 15:03    [21055444]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6626
MasterZiv
Это ка бы не цикл, но эффективно как цикл.

Это цикл. Там goto на начало ))
22 дек 17, 22:12    [21056499]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
mayton,
слишком специфично под каждый компилятор

скорее всего только самые простые оптимизации под "строгую хвостовую рекурсию" если повезёт
в языке без явных гарантий нельзя полагаться на это 100%

https://habrahabr.ru/company/pvs-studio/blog/261027/
https://habrahabr.ru/company/pvs-studio/blog/261029/
22 дек 17, 22:59    [21056628]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
mayton,

klirichek
Я, может, сейчас жутко крамольную вещь скажу…
Но не кажется ли, что в ДАННОМ случае вместо массажа опций компилятора и рассматривания дизассемблера можно просто написать goto в исходном коде и получить нужный результат независимо от положения звёзд?
+1
22 дек 17, 23:04    [21056645]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6626
Многие алгоритмы намного проще и понятнее выглядят именно в рекурсивной форме, потому что в итеративной форме надо явно хранить состояние, а в рекурсивной оно часто скрыто под капотом.
Поэтому не всегда можно просто "просто написать goto ")))
23 дек 17, 12:09    [21057125]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
Anatoly Moskovsky
Многие алгоритмы намного проще и понятнее выглядят именно в рекурсивной форме, потому что в итеративной форме надо явно хранить состояние, а в рекурсивной оно часто скрыто под капотом.
Поэтому не всегда можно просто "просто написать goto ")))
"строгую хвостовую рекурсию".
23 дек 17, 22:26    [21057734]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Окей. Поскольку топик заглох я подкину дровишек.

В книге - А.Степанов Д.Роуз - От Математики к обобщенному программированию
Во главе 2.1 Степанов рассуждает о методе Египетского умножения. Кратко поясню суть.
Один из множетелей раскладывается на сумму двоичных коэффициентов 1,2,4...e.t.c.
и раскрываются скобки. Далее - умножение сводится к сложению. Есть поинт в том
что количество операций будет минимально. Рекурсия используется в качестве базового
алгоритма.

Далее в главе 2.2 Степанов пытается уйти от рекурсии и фактичкески заменить ее итерацией.
Но для этого он делает несколько эквивалентных преобразований.

Приводится также определение:

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


С позволения Степанова я публикую фрагмент кода (не финальный).
int mult_acc3(int r,int n,int a){
  if (odd(n)){
    r = r + a;
    if (n == 1) return r;
  }
  n = half(n);
  a = a + a;
  return mult_acc3(r,n,a);
}


Далее идет еще цепочка ручных трансформаций где Степанов сводит это к итерации.

По сабжу меня интересовал только рекурсивный вариант. Поэтому я на этом остановлюсь.

Зависимые функции четности и деления пополам - half(),odd() я поскипаю. Они тривиальны.

Интересует также связь этого метода с оптимизацией умножения в длинных целых.
24 дек 17, 14:04    [21058333]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
mayton
Один из множетелей раскладывается на сумму двоичных коэффициентов 1,2,4...e.t.c.
и раскрываются скобки.

если о цели: я может чего не понимаю, но какой смысл выполнять обычный алгоритм "умножение столбиком"?
24 дек 17, 21:57    [21058913]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 10925
kealon(Ruslan)
если о цели: я может чего не понимаю, но какой смысл выполнять обычный алгоритм "умножение столбиком"?
Когда пишется собственная реализация арифметики больших чисел - смысл появляется.
Причины написания могут быть разные.
24 дек 17, 21:59    [21058916]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
Basil A. Sidorov,

я в плане алгоритма, зачем использовать заведомо O(n^2), можно для начала взять хотя бы тот же алгоритм Карацубы
24 дек 17, 22:09    [21058926]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 10925
kealon(Ruslan)
зачем использовать заведомо O(n^2), можно для начала взять хотя бы тот же алгоритм Карацубы
Алгоритм Карацубы настолько сложен, что оправдывает себя только на очень больших числах. Или я неправ?
24 дек 17, 22:23    [21058955]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
Basil A. Sidorov
kealon(Ruslan)
зачем использовать заведомо O(n^2), можно для начала взять хотя бы тот же алгоритм Карацубы
Алгоритм Карацубы настолько сложен, что оправдывает себя только на очень больших числах. Или я неправ?
все они имеют определённый лимит от которого становятся разумны
Алгоритм Фюррера например хоть и O(N*Ln(n)), но проигрывает на мелких числах
24 дек 17, 22:33    [21058971]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
kealon(Ruslan)
mayton
Один из множетелей раскладывается на сумму двоичных коэффициентов 1,2,4...e.t.c.
и раскрываются скобки.

если о цели: я может чего не понимаю, но какой смысл выполнять обычный алгоритм "умножение столбиком"?

Я понимаю внутренне ваше возмущение. Скажу честно что я не сравнивал метод Карацубы
и метод Египтян. Более того я даже не считаю что он (Египетский) хорош. Просто тема топика - рекурсия
и я взял первый материал который под рукой оказался.

А по теме египтян могу предположить что умножение в столбик было им недоступно скорее
всего по причине того что их система записи чисел - непозиционная.

Видимо сравнение и сложение для них было проще.

Сообщение было отредактировано: 24 дек 17, 22:37
24 дек 17, 22:36    [21058980]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
kealon(Ruslan)
Basil A. Sidorov
пропущено...
Алгоритм Карацубы настолько сложен, что оправдывает себя только на очень больших числах. Или я неправ?
все они имеют определённый лимит от которого становятся разумны
Алгоритм Фюррера например хоть и O(N*Ln(n)), но проигрывает на мелких числах

Окей. Давайте их тоже обсудим.

Но на правах топик-стартера я прошу учесть хештеги #C++ и #рекурсия.
24 дек 17, 22:41    [21058986]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
mayton,

да нету никакого возмущения, просто фактически это умножение в столбик, с предварительным переводом одного из операндов в двоичную форму.

собственно по теме:
повлиять на алгоритм компилятора мы в принципе не особо можем, а вот выдать ему код без рекурсии - можем.
ИМХО если идти напрямую от комбинатора неподвижной точки, то можно написать генератор кода для любой итеративной функции, которую возможно так разложить.
Вот только зачем?
24 дек 17, 22:57    [21059004]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Нет. Как раз интересно дать ему код с рекурсией. Но на выходе получить safe-stack-overflow код.

Ну... если не повезло - то хотя-бы увидеть Warning уровня компилляции. "Не шмогла..." дескыть.
25 дек 17, 00:28    [21059078]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
booby
Member

Откуда:
Сообщений: 2451
kealon(Ruslan)
...
если о цели: я может чего не понимаю, но какой смысл выполнять обычный алгоритм "умножение столбиком"?


ничего общего от слова совсем:
столбик сформулирован в терминах позиционного представления числа
а египетскому умножению (он же - russian peasant algorithm) до лампады представление числа.
Он работает в терминах удвоения, деления пополам и определения четности.
К тому, что понятно как удваивать - 100% шансы применить этот алгоритм.
Попробуйте применить столбик к размножению строк.
А египетское умножение отменно обеспечивает умножение целых чисел, возведения их в степень,
возведение в степень квадратных матриц, кватернионов и строк, а как бонус еще и вычисление чисел Фибоначчи.
Возведения в целую степень вообще всего, что может быть мыслимо как полугруппа с ассоциативной операцией.
Книжка эта про обобщенное программирование, а египетское умножение - базовый алгоритм, на примере которого и раскрывается представление об обобщенном программировании.

kealon(Ruslan)
Basil A. Sidorov,

я в плане алгоритма, зачем использовать заведомо O(n^2), можно для начала взять хотя бы тот же алгоритм Карацубы

Зря вы это сказали.
Алгоритмы анализируются в ценах элементарных (базовых для анализа) операций.
Для этого алгоритма элементарной операцией является операция сложения.
И выполняется она Log(n) раз.
То есть, с точки зрения выполнения базовых операций, с ростом масштаба задачи, данный алгоритм масштабируется
как суперконстанта по отношению к числу выполняемых базовых операций.
Надо совсем не иметь представления об обсуждаемом предмете, чтобы задавать вопрос - зачем рассматривать такой алгоритм.

mayton
Зависимые функции четности и деления пополам - half(),odd() я поскипаю. Они тривиальны.

Дело не в том, тривиальны они или нет, а в том, какое поведение они ожидают от применяемого к ним параметра.
В данном случае - поведение (целого) числа.
Именно это и определяет направление дальнейшего будущего обобщения.
Поэтому таким алгоритмом имеет смысл возводить квадратные матрицы в целую степень или размножать строки целое число раз, при условии, что базовая операция умножения матрицы или склейки строк будет предоставлена той полугруппой, которую представляет соответствующий параметр функции.
А вот умножать строки на строки, или матрицы на матрицы таким алгоритмом нельзя.
25 дек 17, 02:53    [21059173]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
bool odd(int n) { return n & 0x1; }

int half(int n) { return n >> 1; }
25 дек 17, 03:06    [21059174]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
booby
Member

Откуда:
Сообщений: 2451
mayton,

не знаю, зачем ты это написал.
Если ты опять про "элементарность реализации", то я опять о том, что существо дела в другом.

Параметры, передаваемые в алгоритм неравноценны и обобщаются по разному.
Для n здесь нет толкового обобщения, отличного от смысла целого числа.

Т.е. параметры у алгоритма неравноценны:
а - может быть представлено любым типом, обеспечивающим поведение полугруппы
n - может быть только типом, эквивалентным целому числу.
25 дек 17, 03:21    [21059182]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Четность. И целочисленное деление на два.
25 дек 17, 03:27    [21059183]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
Все форумы / C++ Ответить