Форум программистов, компьютерный форум, киберфорум
Pure
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  

Хвостовая рекурсия

Запись от Pure размещена 09.08.2013 в 00:59
Показов 9806 Комментарии 6

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
//хвостовая рекурсия, 2 функции для перевода строки с бинарным числом в десятичное целое
//параметры передаются в глубину, результат накапливается в одном из параметров
//в функции result компилятор оптимизирует вызовы обращая их в цикл.
//стек не переполняется
 
int result ( const char* str_bin, int res, int shift)
{
    if(shift == 0) return res+((str_bin[0]-48));
    return result(str_bin+1, res+((str_bin[0]-48)<<shift),shift-1);
}
 
int calc (const char* str_bin)
{
    return result(str_bin,0,strlen(str_bin)-1);
}
 
int main()
{
std::cout<<calc("1011101");
return 0;
}
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 6
Комментарии
  1. Старый комментарий
    Аватар для alex_x_x
    Хммм, был удивлен, но всякие gcc действительно умеют оптимизировать хвостовую рекурсию. А я думал это пререгатива лиспов да хаскелов
    Запись от alex_x_x размещена 09.08.2013 в 01:32 alex_x_x вне форума
  2. Старый комментарий
    Аватар для Pure
    вот и хорошо, а то я только на студийном проверял
    Запись от Pure размещена 10.08.2013 в 00:58 Pure вне форума
  3. Старый комментарий
    Аватар для Toshkarik
    Немного не понятно вот тут:
    if(shift == 0) return res+((str_bin[0]-48)<<shift);
    Зачем делать сдвиг на shift если shift == 0 ?
    Запись от Toshkarik размещена 10.08.2013 в 15:18 Toshkarik вне форума
  4. Старый комментарий
    Аватар для Pure
    все верно. это можно убрать, все равно сдвига не происходит. Я уже свои строки копипастил просто, стараясь передать СУТЬ, ведь еще можно отметить что int результат - легко переполнить. Но СУТЬ не в этом.


    а она в том, что на уважаемом и любимом вами мегаязыке - вполне себе можно загнать код в требования к хвостовой рекурсии и он будет оптимизирован компилятором в цикл. То бишь любители рекурсии имеют право жить в мире ++
    Запись от Pure размещена 10.08.2013 в 15:24 Pure вне форума
  5. Старый комментарий
    Аватар для Evg
    Цитата Сообщение от alex_x_x
    Хммм, был удивлен, но всякие gcc действительно умеют оптимизировать хвостовую рекурсию. А я думал это пререгатива лиспов да хаскелов
    Хвостовая рекурсия формализуется. Т.е. можно формально описать критерии, по которым компилятор, глядя на тело функции с хвостовой рекурсией, преобразует её в цикл. gcc, думается, далеко не единственный компилятор, который умеет это делать
    Запись от Evg размещена 17.08.2013 в 14:39 Evg вне форума
  6. Старый комментарий
    Аватар для alex_x_x
    Цитата Сообщение от Evg
    Хвостовая рекурсия формализуется. Т.е. можно формально описать критерии, по которым компилятор, глядя на тело функции с хвостовой рекурсией, преобразует её в цикл. gcc, думается, далеко не единственный компилятор, который умеет это делать
    это да, есть реализации диалектов лиспов, которые гарантируют разворачивание хвостовой рекурсии
    просто не думал, что сишные компиляторы таким заморачиваются
    Запись от alex_x_x размещена 10.09.2013 в 05:32 alex_x_x вне форума
 
Новые блоги и статьи
Был там один разговор по поводу свободы в материальном мире.
kumehtar 19.08.2026
Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .
Когда логика программы не спасает от человеческих ошибок
Maks 18.08.2026
В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .
Лето уходит
kumehtar 17.08.2026
Мысли в слух
kumehtar 17.08.2026
Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .
Перемещение строк из ТЧ в другой документ с учетом текущего пробега
Maks 17.08.2026
Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .
Саморегулирующийся социальный контракт для сервера cross-section.
Hrethgir 14.08.2026
С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .
Часы электронные
Uhbif79 12.08.2026
Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .
Часы с будильником на основе класса QLCDNumber
Uhbif79 12.08.2026
Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru