Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.94
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
#1

Пример, подтверждающий что не любую итерацию можно заменить рекурсией - C++

05.10.2010, 23:36. Просмотров 4114. Ответов 45
Метки нет (Все метки)

Как известно(по некоторым источникам ) любую рекурсию можно представить в виде цикла, но не наоборот. Так вот, надо придумать пример, который будет наглядно показывать , что итеративный вариант единственно возможный в данном случае.
Я по этому поводу пока ничего вразумительного предположить не могу ..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.10.2010, 23:36
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Пример, подтверждающий что не любую итерацию можно заменить рекурсией (C++):

Sleep(8000) - что значит? На что можно заменить в борланд с++? - C++
Не распознаёт Sleep(8000) . Если за комментировать пишет что f заданно но не используется. Как исправить? ...

на что можно заменить функцию? - C++
#include <vcl.h> #include <iostream.h> #include <iomanip.h> float yearzp(float z); //описание функции годовая 3/п const int m=20;...

Как можно найти итерацию, на которой происходит "access violation reading location"? - C++
Ситуация такая что имеется функция которая вызывается в цикле около 1 млн. раз, в какой-то из итераций выскакивает исключение "access...

Заменить любую группу пробелов одним - C++
помогите пожалуйста с лабой. необходимо сжать строку , заменив любую группу пробелов одним пробелом.Исходную строку и результат вывести...

из питона можно сделать что то вроде интерпритатора на любую ос ? - Python
со своим кодом(кодом питона), если да как это делается хотябы "направление"

Доказать, что любую целочисленную денежную сумму, большую 7 руб., можно выплатить без сдачи - C#
Доказать, что любую целочисленную денежную сумму, большую 7 руб., можно выплатить без сдачи трешками и пятерками. Для заданного числа n>7...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Nameless One
Эксперт С++
5771 / 3420 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
07.10.2010, 17:52 #16
#pragma,
C
1
2
3
4
5
6
7
8
9
10
11
12
13
do
{
тело
}
while(условие);
 
//...
void rec()
{
   тело // сначала выполняется тело
   if(условие) // потом проверяется условие
      rec(); // если условие верно, выполняется еще одна итерация и т.д.
}
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
07.10.2010, 17:54 #17
Ой,и правда Ну тогда сдаюсъ
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
07.10.2010, 18:11 #18
Цитата Сообщение от LineStown Посмотреть сообщение
Угу, был недавно совсем похожий вопрос про циклы, оказалось препод - баран
Помню-помню
PointsEqual
ниначмуроФ
834 / 518 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
07.10.2010, 18:19 #19
а в чем отличие хвостовой от обычной рекурсии?
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
07.10.2010, 18:29 #20
PointsEqual,
Хвостовая обычно заменяется в итоге на цикл, поскольку сама рекурсивная функция последней операцией содержит вызов самой себя без выполнения каких-либо иных операция, что аналогично переходу на следующую итерацию цикла.

Добавлено через 3 минуты
Т.е., скажем, факториал, в стандартной своей рекурсивной реализации, не заменится при компилятором на цикл, поскольку там после вызова рекурсивной функции её результат умножается на n, а цикл мы умножить ни на что не можем)))
Nameless One
Эксперт С++
5771 / 3420 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
07.10.2010, 19:14 #21
Цитата Сообщение от silent_1991 Посмотреть сообщение
Хвостовая обычно заменяется в итоге на цикл, поскольку сама рекурсивная функция последней операцией содержит вызов самой себя без выполнения каких-либо иных операция, что аналогично переходу на следующую итерацию цикла.
Вот еще одно определение:
Если рекурсия хвостовая (точнее, это — необходимое
условие, но не достаточное), то возможно у функции есть
одно свойство — после передачи управления рекурсивному вызову самой
себя никакая из локальных переменных этой функции в ее вызывающем
варианте не будет нужна для формирования результата. В таком
случае вызываемый вариант может использовать для переменных
ту же память, что использовал вызывающий.
Цитата Сообщение от silent_1991 Посмотреть сообщение
Хвостовая обычно заменяется в итоге на цикл
Это обычно верно для функциональных языков программирования. Насколько мне известно, только два компилятора языка С++ могут оптимизировать хвостовую рекурсию - это msvs и gcc, да и то в случае указания специальных опций.
danfox
0 / 0 / 0
Регистрация: 05.10.2010
Сообщений: 10
10.10.2010, 15:58 #22
попробуй рассмотреть функцию не всегда определенную
Nameless One
Эксперт С++
5771 / 3420 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
10.10.2010, 16:13 #23
danfox, а поконкретней?
danfox
0 / 0 / 0
Регистрация: 05.10.2010
Сообщений: 10
11.10.2010, 00:27 #24
не смогу уточнить, просто кажется что в этой области надо поискать насчет решения
Nameless One
Эксперт С++
5771 / 3420 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
11.10.2010, 01:54 #25
Если ты имеешь в виду функцию с точками разрыва, то тогда множество аргументов функции просто разбивается на несколько интервалов, исключающих точки разрыва, и функция "рассматривается" (что бы это не значило) уже на этих интервалах на этих интервалах
danfox
0 / 0 / 0
Регистрация: 05.10.2010
Сообщений: 10
11.10.2010, 03:28 #26
именно это и имел в виду
скорее всего не подходит
но если рассматривать ее как единую без разбиения на интервалы то возможно это и будет ответом для данного преподавателя с интересными вопросами
Nameless One
Эксперт С++
5771 / 3420 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
11.10.2010, 05:26 #27
danfox, что ты понимаешь под словом "рассматривать"? Если, к примеру, посчитать интеграл от этой функции, то не получится ни циклом, ни рекурсией
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
11.10.2010, 05:34 #28
danfox,
Такое ощущение, что либо цикл, либо рекурсию (скорее всего рекурсию) вы представляете себе как непрерывный процесс, который и с данными работает непрерывно. Но это не так, компьютер вообще вещь дискретная, и ничего непрерывного в ней нет (если уж не опускаться на самый нижний, физический уровень, но нам туда и не надо), поэтому и цикл, и рекурсия, скажем так, дискретные обработчики данных. И какую бы функцию мы ни "рассматривали" (что бы в данном контексте это не означало), попадём мы в точку разрыва или нет, зависит не от того, чем мы пользуемся в данный конкретный момент, циклом или рекурсией, а только от нашей предусмотрительности (в случае, если точки выбираются по какому-то закону) или же чистой случайности (если точки рандомятся)...
easybudda
Модератор
Эксперт CЭксперт С++
9530 / 5523 / 932
Регистрация: 25.07.2009
Сообщений: 10,602
11.10.2010, 09:51 #29
Цитата Сообщение от danfox Посмотреть сообщение
попробуй рассмотреть функцию не всегда определенную
Вы, если знаете пример, когда итерацию нельзя рекурсией заменить, покажите - нам тоже интересно. А так - метафизика какая-то...
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.10.2010, 10:33 #30
Цитата Сообщение от odip Посмотреть сообщение
Ну-ка сделайте мне это в виде рекурсии и чтобы ПОСЧИТАЛО !
А если на дипблу?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.10.2010, 10:33
Привет! Вот еще темы с ответами:

Объяснить пример с рекурсией - C (СИ)
#include<stdio.h> void gg(int a,int b) { int i=0; if(a==20) return; printf("%d\n",a); printf("%d\n",b); gg(a+1,b-1); ...

Доказать, что любую денежную сумму, большую 7 руб, можно выплатить без сдачи трешками и пятерками - C (СИ)
в общем программа сделанная, но выдает такую ошибку: "function 'fdiv' should have a prototype". объясните новичку в чем проблема. #...

Доказать что любую целочисленную денежную сумму ,большую 7 руб. можно выплатить без сдачи трёшками и пятёрками. - Pascal ABC
1.Доказать что любую целочисленную денежную сумму ,большую 7 руб. можно выплатить без сдачи трёшками и пятёрками.Для данного n>7 найти...

Заменить цикл рекурсией - C (СИ)
Дана функция. float result(double x1, double e) { double x2; float temp; x2 = x1; Ufunction = function; Ufunction1 =...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
11.10.2010, 10:33
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru