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

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

Откуда: loopback
Сообщений: 51017
Точно ОК?
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
Сообщений: 51017
Мне кажется что Буби как-то сходу внес в топик сам вопро определения алгебры для нашего алгоритма.
Мне сложно говорить на эту тему т.к. надо сначала почитать соотв. теорию, а времени
нет и возникают вопросы более насущные и актуальные. Забегая вперед... в последних
главах книги Степанов касается обобщений чисел. Но я-бы предложил поскипать это
и пока говорить о рекурсии.

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
Сообщений: 51017
Докину в тему.

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

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

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

Откуда: loopback
Сообщений: 51017
Из стековерфлоу.
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
Сообщений: 51017
Еще один пример с хвостиком. От Массачусетских языков. Кодинг - мой. И возможные баги тоже мои.

Первый исходник - лобовое решение факториала.
Второй - с оптимизацией. В книге пишут что 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
Сообщений: 51017
Руслан. Большинство "инициативных" топиков здесь требуют немедленного ответа на вопрос "зачем".

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

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

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

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

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

Будем издеваться над императивными.
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
Сообщений: 51017
petrav
kealon(Ruslan)
пропущено...
почему они похерятся?

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

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

А как деструкторы связаны с хвостовой рекурсией?
30 дек 20, 20:27    [22257386]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
Все форумы / C++ Ответить