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

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

Запись от Pure размещена 09.08.2013 в 00:59
Показов 9824 Комментарии 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 вне форума
 
Новые блоги и статьи
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0.
Maks 31.08.2026
При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм
anaschu 30.08.2026
Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
Оттачиваю умение писать js программы.
russiannick 30.08.2026
Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .
мат медиц модель 30. презентация проекта
anaschu 27.08.2026
хоп хоп хоп хидахоп, а я кладую))
Как у меня протекала болезнь
zorxor 27.08.2026
Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .
Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему
kumehtar 26.08.2026
ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .
[EasyBuilder Pro] Памятка по разработке для панелей Weintek
ФедосеевПавел 26.08.2026
Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .
Модель по догадкам
anaschu 25.08.2026
Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru