ReSQL.ru
     
powered by simpleCommunicator - 2.0.58     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная хвостовая рекурсия.
25 сообщений из 56, страница 2 из 3
  2  все
Тяпничная хвостовая рекурсия.
    #39575144
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
ок
...
Рейтинг: 0 / 0
25.12.2017, 03:30
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #39575145
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Точно ОК?
...
Рейтинг: 0 / 0
25.12.2017, 03:33
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #39575148
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
точно.
...
Рейтинг: 0 / 0
25.12.2017, 03:43
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #39575187
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
boobyничего общего от слова совсем:
столбик сформулирован в терминах позиционного представления числаи к чему он приводит любое число? вангую что к двоичному представлению

boobykealon(Ruslan)Basil A. Sidorov,

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

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

Ну... если не повезло - то хотя-бы увидеть Warning уровня компилляции. "Не шмогла..." дескыть.
Далеко полез, чё по проще заставить его посчитать - и то проблема. Компиляторы довольно ограниченная "вещь в себе".
...
Рейтинг: 0 / 0
25.12.2017, 09:26
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #39575227
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Мне кажется что Буби как-то сходу внес в топик сам вопро определения алгебры для нашего алгоритма.
Мне сложно говорить на эту тему т.к. надо сначала почитать соотв. теорию, а времени
нет и возникают вопросы более насущные и актуальные. Забегая вперед... в последних
главах книги Степанов касается обобщений чисел. Но я-бы предложил поскипать это
и пока говорить о рекурсии.

P.S. Вобщем ... просил я только масла на завтрак мне подать (с) Баллада о королевском бутерброде
...
Рейтинг: 0 / 0
25.12.2017, 10:22
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #39577181
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
White Owlпоследний раз я это ковырял в третьем gcc лет пять назад, и классический пример не разворачивался.
Код: plaintext
1.
2.
3.
4.
int fact(n) {
  if (n==0) return 1;
  return n * fact(n-1);
}



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

Anatoly MoskovskyMasterZivЭто ка бы не цикл, но эффективно как цикл.
Это цикл. Там goto на начало ))

Вероятно речь шла не о полученном наборе инструкций после трансляции программы, а об исходном синтаксисе)
...
Рейтинг: 0 / 0
28.12.2017, 01:54
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
Тяпничная хвостовая рекурсия.
    #39788139
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Докину в тему.

Вариант хвостовой рекурсии в Scala. Для сравнения.
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
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 дополнительно информирует компиллятор
о требовании размотки рекурсии в цикл. Не всякая рекурсия разматывается.
Должен присутсвовать аккумулятор.
...
Рейтинг: 0 / 0
19.03.2019, 03:22
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #39788222
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,
Scala - функциональный язык, не знаю как в нутрах компилятора сделано, но если так же как в хаскель, т.е. компилируется в комбинаторы, то вполне реальная вещь
kealon(Ruslan)ИМХО если идти напрямую от комбинатора неподвижной точки, то можно написать генератор кода для любой итеративной функции, которую возможно так разложить.
...
Рейтинг: 0 / 0
19.03.2019, 10:32
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #39788235
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Возвращаясь к теме С++. Зачем Степанову понадобилась строгая хвостовая?
...
Рейтинг: 0 / 0
19.03.2019, 10:42
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #39788238
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
maytonВозвращаясь к теме С++. Зачем Степанову понадобилась строгая хвостовая?микроконтроллёры например, но то так, пальцем в небо

медленнно работают рекурсивные вызовы + непредсказуемое поведение
...
Рейтинг: 0 / 0
19.03.2019, 10:45
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #39790703
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Из стековерфлоу.
https://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization#220660
Претендует на хвостовую. Но не строгая.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
#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. Было-бы что-то вроде.
Код: plaintext
1.
2.
3.
 n = n * 10 + *str-'0';
 str++;
 return atoi(str, n);
...
Рейтинг: 0 / 0
25.03.2019, 01:05
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
Тяпничная хвостовая рекурсия.
    #40032487
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Еще один пример с хвостиком. От Массачусетских языков. Кодинг - мой. И возможные баги тоже мои.

Первый исходник - лобовое решение факториала.
Второй - с оптимизацией. В книге пишут что tail-recursion обязателен для сертификации всех реализаций Scheme.
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
;;; 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)
)
...
Рейтинг: 0 / 0
30.12.2020, 02:37
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #40032503
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,

давай функциональные языки не будем рассматривать, там всё фундаментально понятно и доказано когда можно и когда нельзя - 21059004
...
Рейтинг: 0 / 0
30.12.2020, 09:33
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #40032529
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Руслан. Большинство "инициативных" топиков здесь требуют немедленного ответа на вопрос "зачем".

Скорее всего низачем. Просто - игры разума.
...
Рейтинг: 0 / 0
30.12.2020, 10:57
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #40032545
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton

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

А чем по Степанову хвостовая рекурсия отличается от строгой хвостовой?
...
Рейтинг: 0 / 0
30.12.2020, 11:27
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #40032548
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну вот тут-же цитата 21058333
...
Рейтинг: 0 / 0
30.12.2020, 11:31
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #40032558
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,

я просто говорю, что для функциональных языков этот вопрос фундаментально закрыт - надо, отсюда и логичное требование в сертификации
...
Рейтинг: 0 / 0
30.12.2020, 11:55
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #40032621
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Хорошо. Не будем трогать функциональные. Просто к слову пришлось.

Будем издеваться над императивными.
...
Рейтинг: 0 / 0
30.12.2020, 14:18
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #40032647
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
petrav
mayton

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

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


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

Если алгоритм обладает строгой строгой хвостовой рекурсией, то использование удобной
рекурсивной записи программистом бесплатно с точки зрения накладных расходов.
"умный" компилятор рекурсию полностью исключит и заменит на цикл.
...
Рейтинг: 0 / 0
30.12.2020, 15:44
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #40032651
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
booby
petrav
пропущено...

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


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

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

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

Тока мне кажется, что сама идея этой хвостовой рекурсией не совместима с C++. Что будет с
вызовом деструкторов локальных объектов? Правильно, они похерятся. Т.е. по хорошему
нужно вводить атрибут какой-то для таких функций: типа настаиваю на такой фишке, а
компилятор уже проверяет может или не может.
...
Рейтинг: 0 / 0
30.12.2020, 15:58
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #40032662
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
petrav,

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

Рекурсия вообще - это идея циклического алгоритма вообще.
Специальные случаи вроде строгой хвостовой позволяют свести алгоритм к простому циклу.
Например, свести самому программисту (и не ошибиться при этом), даже если компилятор этого делать не умеет.
Делать это или нет - вопрос борьбы за время организации вызова и передачи параметров.
...
Рейтинг: 0 / 0
30.12.2020, 16:25
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #40032666
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
booby,

ну, для каких-то случаев - еще и за размер стека.
...
Рейтинг: 0 / 0
30.12.2020, 16:29
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #40032709
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
petrav
Тока мне кажется, что сама идея этой хвостовой рекурсией не совместима с C++. Что будет с
вызовом деструкторов локальных объектов? Правильно, они похерятся. Т.е. по хорошему
нужно вводить атрибут какой-то для таких функций: типа настаиваю на такой фишке, а
компилятор уже проверяет может или не может.
почему они похерятся?
...
Рейтинг: 0 / 0
30.12.2020, 20:01
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #40032710
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
kealon(Ruslan)
petrav
Тока мне кажется, что сама идея этой хвостовой рекурсией не совместима с C++. Что будет с
вызовом деструкторов локальных объектов? Правильно, они похерятся. Т.е. по хорошему
нужно вводить атрибут какой-то для таких функций: типа настаиваю на такой фишке, а
компилятор уже проверяет может или не может.
почему они похерятся?

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

Или же они вообще перестанут вызываться.
...
Рейтинг: 0 / 0
30.12.2020, 20:07
| Ответить | Цитировать | Написать  
Тяпничная хвостовая рекурсия.
    #40032717
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petrav
kealon(Ruslan)
пропущено...
почему они похерятся?

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

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

А как деструкторы связаны с хвостовой рекурсией?
...
Рейтинг: 0 / 0
30.12.2020, 20:27
| Ответить | Цитировать | Написать  
25 сообщений из 56, страница 2 из 3
  2  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная хвостовая рекурсия.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=57&msg=39575227&tid=2017275]:
 0ms
get settings:
 11ms
get forum list:
 16ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 37ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 61ms
get tp. blocked users:
 2ms
others: 263ms
total:  407ms
созд. / загр.: 407ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]