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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.94
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
05.10.2010, 23:36     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #1
Как известно(по некоторым источникам ) любую рекурсию можно представить в виде цикла, но не наоборот. Так вот, надо придумать пример, который будет наглядно показывать , что итеративный вариант единственно возможный в данном случае.
Я по этому поводу пока ничего вразумительного предположить не могу ..
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
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
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
10.10.2010, 16:13     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #23
danfox, а поконкретней?
danfox
0 / 0 / 0
Регистрация: 05.10.2010
Сообщений: 10
11.10.2010, 00:27     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #24
не смогу уточнить, просто кажется что в этой области надо поискать насчет решения
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
11.10.2010, 01:54     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #25
Если ты имеешь в виду функцию с точками разрыва, то тогда множество аргументов функции просто разбивается на несколько интервалов, исключающих точки разрыва, и функция "рассматривается" (что бы это не значило) уже на этих интервалах на этих интервалах
danfox
0 / 0 / 0
Регистрация: 05.10.2010
Сообщений: 10
11.10.2010, 03:28     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #26
именно это и имел в виду
скорее всего не подходит
но если рассматривать ее как единую без разбиения на интервалы то возможно это и будет ответом для данного преподавателя с интересными вопросами
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
11.10.2010, 05:26     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #27
danfox, что ты понимаешь под словом "рассматривать"? Если, к примеру, посчитать интеграл от этой функции, то не получится ни циклом, ни рекурсией
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.10.2010, 05:34     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #28
danfox,
Такое ощущение, что либо цикл, либо рекурсию (скорее всего рекурсию) вы представляете себе как непрерывный процесс, который и с данными работает непрерывно. Но это не так, компьютер вообще вещь дискретная, и ничего непрерывного в ней нет (если уж не опускаться на самый нижний, физический уровень, но нам туда и не надо), поэтому и цикл, и рекурсия, скажем так, дискретные обработчики данных. И какую бы функцию мы ни "рассматривали" (что бы в данном контексте это не означало), попадём мы в точку разрыва или нет, зависит не от того, чем мы пользуемся в данный конкретный момент, циклом или рекурсией, а только от нашей предусмотрительности (в случае, если точки выбираются по какому-то закону) или же чистой случайности (если точки рандомятся)...
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
11.10.2010, 09:51     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #29
Цитата Сообщение от danfox Посмотреть сообщение
попробуй рассмотреть функцию не всегда определенную
Вы, если знаете пример, когда итерацию нельзя рекурсией заменить, покажите - нам тоже интересно. А так - метафизика какая-то...
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.10.2010, 10:33     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #30
Цитата Сообщение от odip Посмотреть сообщение
Ну-ка сделайте мне это в виде рекурсии и чтобы ПОСЧИТАЛО !
А если на дипблу?
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
11.10.2010, 10:49     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #31
Цитата Сообщение от easybudda Посмотреть сообщение
Вы, если знаете пример, когда итерацию нельзя рекурсией заменить, покажите - нам тоже интересно. А так - метафизика какая-то...
Ну или пусть объяснит, что имеет в виду, а мы там и сами додумаем
Евгений М.
1033 / 974 / 53
Регистрация: 28.02.2010
Сообщений: 2,817
Завершенные тесты: 2
11.10.2010, 10:49     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #32
Цитата Сообщение от KBAC Посмотреть сообщение
Как известно(по некоторым источникам) любую рекурсию можно представить в виде цикла, но не наоборот.
Эти источники говорят, что существует задача, которую можно решить рекурсивным методом, но невозможно (или пока не найден способ) решить итерационным методом.
Я правильно понял? Если да, то поделитесь с источниками. Там должен быть либо конкретный пример либо задача, которую можно решить рекурсией, но надо решить итерационным методом. Пока мне кажется, что источник - недостоверный.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.10.2010, 11:16     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #33
Евгений М.,
Видимо "некоторые источники" - препод вроде того, который говорил, что for на while не заменяется...
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.10.2010, 11:18     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #34
Цитата Сообщение от silent_1991 Посмотреть сообщение
for на while
заменяется, как и наоборот. Но обе эти замены - наглядные пособия, как делать не надо. Поэтому в нормальных прогах ни один из этих циклов на другой не заменяется.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.10.2010, 11:20     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #35
taras atavin,
Спасибо, в той теме мы ТСу примерно так и ответили. Но препод-то настаивал, что не заменяется. Потому я и привёл здесь этот пример...
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.10.2010, 11:23     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #36
Цитата Сообщение от Евгений М. Посмотреть сообщение
Я правильно понял
Наоборот. Имеется в виду существование задачи, которую можно решить иттеративно, но нельзя рекурсивно. Если задрать размерность, а память ограничить, то так оно и есть. Например, на слабых компах задача вычисления определителя матрицы 130*130 иттеративно через приведение к треугольнйо решается элементарно, а рекурсивно через разложение по строке не решается вовсе.
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
11.10.2010, 11:31     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #37
Цитата Сообщение от taras atavin Посмотреть сообщение
Например, на слабых компах задача вычисления определителя матрицы 130*130 иттеративно через приведение к треугольнйо решается элементарно, а рекурсивно через разложение по строке не решается вовсе.
А рекурсивно, через приведение к треугольной?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.10.2010, 11:32     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #38
taras atavin,
Опять же, я здесь это уже озвучивал, мне кажется, имеется ввиду "можно ли решить вообще", а не "решить на конкретной машине или с конкретными условиями".
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
12.10.2010, 14:24  [ТС]     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #39
Так, вот что я почерпнул из ТВП:

(1)Тезис Тьюринга: "Всякий алгоритм может быть реализован на машине Тьюринга"
Доказательства этому утверждению НЕТ и НЕ может быть, т.к. само понятие алгоритма является неточным, неформальным.
(2)далее по Тьюрингу: Если для некоторой функции существует маш. Тьюринга, которая эту функцию правильно вычисляет, то эта функция называется вычислимой.
(3)по Чёрчу :
каждая стандартно заданная частично рекурсивная функция(ЧРФ) вычислима путем применения процедуры механического характера.
ЧРФ - множество всех арифметических рекурсивных функций.

по- моему, доказано только как быть не с арифметическими функциями ? или наверно для машины- то таковых НЕ существует ?

Добавлено через 3 минуты

Не по теме:

как оно туда ответилось 0_0

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.10.2010, 18:22     Пример, подтверждающий что не любую итерацию можно заменить рекурсией
Еще ссылки по теме:

C++ Все числа с диапазоном от А до В,что заканчиваются на любую парную цифру
Как можно найти итерацию, на которой происходит "access violation reading location"? C++
Подскажите что с рекурсией не так C++

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

Или воспользуйтесь поиском по форуму:
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
13.10.2010, 18:22  [ТС]     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #40
Так, вот что я почерпнул из ТВП:

(1)Тезис Тьюринга: "Всякий алгоритм может быть реализован на машине Тьюринга"
Доказательства этому утверждению НЕТ и НЕ может быть, т.к. само понятие алгоритма является неточным, неформальным.
(2)далее по Тьюрингу: Если для некоторой функции существует маш. Тьюринга, которая эту функцию правильно вычисляет, то эта функция называется вычислимой.
(3)по Чёрчу :
каждая стандартно заданная частично рекурсивная функция(ЧРФ) вычислима путем применения процедуры механического характера.
ЧРФ - множество всех арифметических рекурсивных функций.

по- моему, доказано. только как быть не с арифметическими функциями ? или наверно для машины- то таковых НЕ существует ?
Yandex
Объявления
13.10.2010, 18:22     Пример, подтверждающий что не любую итерацию можно заменить рекурсией
Ответ Создать тему
Опции темы

Текущее время: 14:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru