Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / C++ Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2 3      [все]
 Тяпничная хвостовая рекурсия.  [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]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
booby
Member

Откуда:
Сообщений: 2451
ок
25 дек 17, 03:30    [21059185]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Точно ОК?
25 дек 17, 03:33    [21059186]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
booby
Member

Откуда:
Сообщений: 2451
точно.
25 дек 17, 03:43    [21059190]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
booby
ничего общего от слова совсем:
столбик сформулирован в терминах позиционного представления числа
и к чему он приводит любое число? вангую что к двоичному представлению

booby
kealon(Ruslan)
Basil A. Sidorov,

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

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

mayton
Нет. Как раз интересно дать ему код с рекурсией. Но на выходе получить safe-stack-overflow код.

Ну... если не повезло - то хотя-бы увидеть Warning уровня компилляции. "Не шмогла..." дескыть.

Далеко полез, чё по проще заставить его посчитать - и то проблема. Компиляторы довольно ограниченная "вещь в себе".
25 дек 17, 09:26    [21059354]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Мне кажется что Буби как-то сходу внес в топик сам вопро определения алгебры для нашего алгоритма.
Мне сложно говорить на эту тему т.к. надо сначала почитать соотв. теорию, а времени
нет и возникают вопросы более насущные и актуальные. Забегая вперед... в последних
главах книги Степанов касается обобщений чисел. Но я-бы предложил поскипать это
и пока говорить о рекурсии.

P.S. Вобщем ... просил я только масла на завтрак мне подать (с) Баллада о королевском бутерброде
25 дек 17, 10:22    [21059520]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2653
White Owl
последний раз я это ковырял в третьем gcc лет пять назад, и классический пример не разворачивался.
int fact(n) {
  if (n==0) return 1;
  return n * fact(n-1);
}


А что вы ожидали от этого примера? Не очень понятен смысл. Если имеется ввиду переход к циклу, то это не похоже на хвостовую рекурсию, потому такой разворот(если я правильно понял смысл этого слова) и не должен произойти

Anatoly Moskovsky
MasterZiv
Это ка бы не цикл, но эффективно как цикл.

Это цикл. Там goto на начало ))


Вероятно речь шла не о полученном наборе инструкций после трансляции программы, а об исходном синтаксисе)
28 дек 17, 01:54    [21068589]     Ответить | Цитировать Сообщить модератору
Между сообщениями интервал более 1 года.
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Докину в тему.

Вариант хвостовой рекурсии в Scala. Для сравнения.
def fact(x: BigInt): BigInt = {
    if (x < 0)
      throw new IllegalArgumentException

    @tailrec def facttail(x: BigInt, accum: BigInt): BigInt =
      if (x == 0)
        accum
      else
        facttail(x - 1, accum * x)

    facttail(x, 1)
}


В данном случае аннотация @tailrec дополнительно информирует компиллятор
о требовании размотки рекурсии в цикл. Не всякая рекурсия разматывается.
Должен присутсвовать аккумулятор.
19 мар 19, 03:22    [21836717]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
mayton,
Scala - функциональный язык, не знаю как в нутрах компилятора сделано, но если так же как в хаскель, т.е. компилируется в комбинаторы, то вполне реальная вещь
kealon(Ruslan)
ИМХО если идти напрямую от комбинатора неподвижной точки, то можно написать генератор кода для любой итеративной функции, которую возможно так разложить.
19 мар 19, 10:32    [21836935]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Возвращаясь к теме С++. Зачем Степанову понадобилась строгая хвостовая?
19 мар 19, 10:42    [21836964]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
mayton
Возвращаясь к теме С++. Зачем Степанову понадобилась строгая хвостовая?
микроконтроллёры например, но то так, пальцем в небо

медленнно работают рекурсивные вызовы + непредсказуемое поведение
19 мар 19, 10:45    [21836969]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Из стековерфлоу.
https://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization#220660
Претендует на хвостовую. Но не строгая.

#include <stdio.h>
static int atoi(const char *str, int n)
{
    if (str == 0 || *str == 0)
        return n;
    return atoi(str+1, n*10 + *str-'0');
}


Забавно если бы я хотел выровнять формальные параметры то сломал-бы простоту и лаконичность
всего atoi. Было-бы что-то вроде.
 n = n * 10 + *str-'0';
 str++;
 return atoi(str, n);
25 мар 19, 01:05    [21842322]     Ответить | Цитировать Сообщить модератору
Между сообщениями интервал более 1 года.
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Еще один пример с хвостиком. От Массачусетских языков. Кодинг - мой. И возможные баги тоже мои.

Первый исходник - лобовое решение факториала.
Второй - с оптимизацией. В книге пишут что tail-recursion обязателен для сертификации всех реализаций Scheme.
;;; Recursive factorial,
;;; Language: MIT/GNU Scheme
;;; Dec-20, 2020 : mayton

(define (fact x)
   (cond
      ((= x 0) 1)
      ((= x 1) 1)
      (else (* x (fact (- x 1))))
   )
)

;;; The same, with tail recursion

(define (fact-tail x)
  (define (fact-internal partial-product x)
     (if (> x 1)
       (fact-internal (* x partial-product) (- x 1))
       partial-product
     )
  )
  (fact-internal 1 x)
)
30 дек 20, 02:37    [22256875]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

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

давай функциональные языки не будем рассматривать, там всё фундаментально понятно и доказано когда можно и когда нельзя - 21059004
30 дек 20, 09:33    [22256895]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Руслан. Большинство "инициативных" топиков здесь требуют немедленного ответа на вопрос "зачем".

Скорее всего низачем. Просто - игры разума.

Сообщение было отредактировано: 30 дек 20, 10:52
30 дек 20, 10:57    [22256944]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
petrav
Member

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

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

А чем по Степанову хвостовая рекурсия отличается от строгой хвостовой?
30 дек 20, 11:27    [22256974]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Ну вот тут-же цитата 21058333
30 дек 20, 11:31    [22256978]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

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

я просто говорю, что для функциональных языков этот вопрос фундаментально закрыт - надо, отсюда и логичное требование в сертификации
30 дек 20, 11:55    [22256991]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Хорошо. Не будем трогать функциональные. Просто к слову пришлось.

Будем издеваться над императивными.
30 дек 20, 14:18    [22257184]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
booby
Member

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

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

А чем по Степанову хвостовая рекурсия отличается от строгой хвостовой?


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

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

Сообщение было отредактировано: 30 дек 20, 15:39
30 дек 20, 15:44    [22257247]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
petrav
Member

Откуда:
Сообщений: 2861
booby
petrav
пропущено...

А чем по Степанову хвостовая рекурсия отличается от строгой хвостовой?


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

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

Спасибо. Вот вы понятно пояснили.

Тока мне кажется, что сама идея этой хвостовой рекурсией не совместима с C++. Что будет с
вызовом деструкторов локальных объектов? Правильно, они похерятся. Т.е. по хорошему
нужно вводить атрибут какой-то для таких функций: типа настаиваю на такой фишке, а
компилятор уже проверяет может или не может.
30 дек 20, 15:58    [22257264]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
booby
Member

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

тут дела так стоят:
Использование рекурсии вообще какой-то - неотделимо от императивного программирования.
Заявить несовместимость рекурсии с языком эквивалентно заявлению о неспособности
реализовать в этом языке циклический алгоритм произвольного вида.

Рекурсия вообще - это идея циклического алгоритма вообще.
Специальные случаи вроде строгой хвостовой позволяют свести алгоритм к простому циклу.
Например, свести самому программисту (и не ошибиться при этом), даже если компилятор этого делать не умеет.
Делать это или нет - вопрос борьбы за время организации вызова и передачи параметров.
30 дек 20, 16:25    [22257281]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
booby
Member

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

ну, для каких-то случаев - еще и за размер стека.
30 дек 20, 16:29    [22257286]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
petrav
Тока мне кажется, что сама идея этой хвостовой рекурсией не совместима с C++. Что будет с
вызовом деструкторов локальных объектов? Правильно, они похерятся. Т.е. по хорошему
нужно вводить атрибут какой-то для таких функций: типа настаиваю на такой фишке, а
компилятор уже проверяет может или не может.
почему они похерятся?
30 дек 20, 20:01    [22257375]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
petrav
Member

Откуда:
Сообщений: 2861
kealon(Ruslan)
petrav
Тока мне кажется, что сама идея этой хвостовой рекурсией не совместима с C++. Что будет с
вызовом деструкторов локальных объектов? Правильно, они похерятся. Т.е. по хорошему
нужно вводить атрибут какой-то для таких функций: типа настаиваю на такой фишке, а
компилятор уже проверяет может или не может.
почему они похерятся?

Они (деструкторы) начнут вызываться в неправильной последовательности. Это принципиально.

Или же они вообще перестанут вызываться.
30 дек 20, 20:07    [22257376]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
petrav
kealon(Ruslan)
пропущено...
почему они похерятся?

Они (деструкторы) начнут вызываться в неправильной последовательности. Это принципиально.

Или же они вообще перестанут вызываться.

А как деструкторы связаны с хвостовой рекурсией?
30 дек 20, 20:27    [22257386]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
petrav
Member

Откуда:
Сообщений: 2861
mayton
petrav
пропущено...

Они (деструкторы) начнут вызываться в неправильной последовательности. Это принципиально.

Или же они вообще перестанут вызываться.

А как деструкторы связаны с хвостовой рекурсией?

Я понял тему топика так:
void foo(int a)
{
    ++a;
    if (a>6)
    {
        return;
    }
    else
    {
       foo(a);
    }
}

Я корректно всё понял? И вместо рекурсии в ассемблере будет jump на начало функции?

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

Откуда: loopback
Сообщений: 51019
petrav

void foo(int a)
{
    ++a;
    if (a>6)
    {
        return;
    }
    else
    {
       foo(a);
    }
}

Я корректно всё понял? И вместо рекурсии будет jump на начало функции?

Я не силен в теории построения компилляторов. Но по моему свертка хвоста превращает рекурсию
в банальный loop. Как там в ассемблере делется loop? Я щас не помню. Много вариантов.
Да можно jump сделать. А можно JNZ (jump-non-zero-flag). Суть вобщем не в этом.
А в том что стек не будем потреблять.

И еще убийственная киллер фича всей функциональщины - все переменные в такой
функции становятся values. Константами. Раз нет цикла. То ничего и не меняется.

Вселенная с застывшим временем.
30 дек 20, 20:41    [22257394]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
petrav
Member

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

Я не силен в теории построения компилляторов. Но по моему свертка хвоста превращает рекурсию
в банальный loop. Как там в ассемблере делется loop? Я щас не помню. Много вариантов.
Да можно jump сделать. А можно JNZ (jump-non-zero-flag). Суть вобщем не в этом.
А в том что стек не будем потреблять.

И еще убийственная киллер фича всей функциональщины - все переменные в такой
функции становятся values. Константами. Раз нет цикла. То ничего и не меняется.

Вселенная с застывшим временем.

Отлично. Я как раз недавно смотрел научно популярный ролик как вернуть время назад. На Физике Побединского.
Но вернёмся к деструкторам и доработаем код.

void foo(int a)
{
    MyObject obj;
    ++a;
    if (a>6)
    {
        return;
    }
    else
    {
       foo(a);
    }
}


Тут два варианта:

- При честной рекурсии у нас деструкторы класса MyObject вызываются в правильной последовательности.
- А при фокусах с разворачиванием рекурсии в цикл что с ними будет? ПНХ?
30 дек 20, 20:49    [22257397]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

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

в вашем примере для компилятора нет хвостовой рекурсии
так как вызов не хвостовой, он такой лишь на первый взгляд
30 дек 20, 20:58    [22257401]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
petrav
Member

Откуда:
Сообщений: 2861
kealon(Ruslan)
petrav,

в вашем примере для компилятора нет хвостовой рекурсии
так как вызов не хвостовой, он такой лишь на первый взгляд

Конечно, я понимаю, что деструктор неявно вызывается в конце функции. Упрощённо.
Но что будет если MyObject изначально был алиасом к int, а потом я переделал MyObject на класс с деструктором?
Поэтому я сразу и написал, что тогда в язык нужно добавить атрибут к функции "настаиваю на хвостовой рекурсии".
Не получилось -- сбой компиляции.
30 дек 20, 21:03    [22257408]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная хвостовая рекурсия.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
petrav
Поэтому я сразу и написал, что тогда в язык нужно добавить атрибут к функции "настаиваю на хвостовой рекурсии".
Не получилось -- сбой компиляции.
я тоже так думаю - "явное лучше неявного"
30 дек 20, 21:25    [22257427]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3      [все]
Все форумы / C++ Ответить