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

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

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

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

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

Как известно(по некоторым источникам ) любую рекурсию можно представить в виде цикла, но не наоборот. Так вот, надо придумать пример, который будет наглядно показывать , что итеративный вариант единственно возможный в данном случае.
Я по этому поводу пока ничего вразумительного предположить не могу ..
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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...

45
HIMen
4144 / 1393 / 39
Регистрация: 12.04.2009
Сообщений: 2,346
05.10.2010, 23:53 #2
Цитата Сообщение от KBAC Посмотреть сообщение
любую рекурсию можно представить в виде цикла, но не наоборот
И наоборот тоже
0
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
06.10.2010, 17:26  [ТС] #3
а я надеялся тут целую дискуссию развернуть..
0
odip
Эксперт С++
7158 / 3220 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
07.10.2010, 07:46 #4
Насчет что любой цикл можно представить в виде рекурсии - чего-то я не уверен
C
1
2
3
4
double s= 0.0;
for ( i= 0; i<=1000000; i++ ) {
   s+= sin( i );
}
Ну-ка сделайте мне это в виде рекурсии и чтобы ПОСЧИТАЛО !
0
mamedovvms
2917 / 838 / 93
Регистрация: 30.04.2009
Сообщений: 2,627
07.10.2010, 08:17 #5
C++
1
2
3
4
double f= 0.0;
for ( i= 1; i<=1000000; i++ ) {
   f*= i;
}
может быть я что то не догоняю, но я написал цикл, для поиска факториала, и как вы думаете он сильно отличается от вашего, но для него то точно можно написать рекурсию, и во многих учебниках есть даже примеры
C++
1
2
3
4
5
6
 double Factorial(int N)
  {
    double F;
    if (N<=1) F=1.; else F=Factorial(N-1)*N;
    return F;
  }
так что для вашего цикла будет так
C++
1
2
3
4
5
6
 double Factorial(int N)
  {
    double F;
    if (N=0) F=sin(0).; else F=sin(Factorial(N-1)) + sin(N);
    return F;
  }
0
HIMen
4144 / 1393 / 39
Регистрация: 12.04.2009
Сообщений: 2,346
07.10.2010, 11:48 #6
Цитата Сообщение от odip Посмотреть сообщение
Ну-ка сделайте мне это в виде рекурсии и чтобы ПОСЧИТАЛО !
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void f(ref int i, ref double s)
{
    if (i > 1000000) return;
    s += Math.Sin(i);
    i++;
    f(ref i, ref s);
}
static void Main(string[] args)
{
    new Thread(() =>
    {
        double s = 0.0;
        int i = 0;
        f(ref i, ref s);
        Console.WriteLine(s);
    }, 1000000 * 4).Start();
}
Надеялся на StackOverflow?
0
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
07.10.2010, 14:08 #7
odip,
Может, ТС имел ввиду не практическую значимость, а абстрактный пример, в котором цикл действительно нельзя записать в виде рекурсии (в не зависимости от того, будет это фактически работать или нет)?
0
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
07.10.2010, 15:49  [ТС] #8
я на эту тему много голову ломал, что именно мне надо ) у меня с преподом вышел разговор за экзамен в котором он мне сказал : "любую рекурсию можно заменить ... , приведите пример такой итерации". Так что мне не понятно даже в каком направлении должно быть различие .

Добавлено через 1 минуту
не различие а именно невозможность замены
0
Nameless One
Эксперт С++
5775 / 3425 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
07.10.2010, 16:39 #9
Цитата Сообщение от odip Посмотреть сообщение
Насчет что любой цикл можно представить в виде рекурсии - чего-то я не уверен
C
1
2
3
4
double s= 0.0;
for ( i= 0; i<=1000000; i++ ) {
   s+= sin( i );
}
Ну-ка сделайте мне это в виде рекурсии и чтобы ПОСЧИТАЛО !
C
1
2
3
4
5
6
7
8
9
double rec(double result, size_t start, size_t end)
{
    if(start > end)
        return result;
    return rec(result + sin(start), ++start, end);
}
 
//...Вызов функции
double s = rec(0, 0, 1000000);
Между прочим, рекурсия не простая, а хвостовая

Еще вариант:
C
1
2
3
4
5
6
7
8
double rec(size_t start, size_t end)
{
    if(start > end)
        return 0;
    return sin(start) + rec(++start, end);
}
//...
double s = rec(0, 1000000);
1
easybudda
Модератор
Эксперт CЭксперт С++
9683 / 5633 / 956
Регистрация: 25.07.2009
Сообщений: 10,819
07.10.2010, 17:32 #10
Цитата Сообщение от Nameless One Посмотреть сообщение
рекурсия не простая, а хвостовая
Что-то никак я этой штукой пользоваться не научусь
По теме же - по-моему и циклы и рекурсия полностью взаимозаменяемы, т.к. делают по сути одно и то же, но разными путями. Другое дело - при обычной (не хвостовой) рекурсии действительно может переполнение стека случиться, так и цикл можно криво написать...
0
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
07.10.2010, 17:39 #11
Подтверждаю: любую рекурсию можно представить в виде цикла, И НАОБОРОТ.
Преподаватель, похоже, корочки купил... или просто баран - таких полно.
0
LineStown
66 / 66 / 3
Регистрация: 04.08.2010
Сообщений: 420
Завершенные тесты: 1
07.10.2010, 17:44 #12
Цитата Сообщение от Patch Посмотреть сообщение
Подтверждаю: любую рекурсию можно представить в виде цикла, И НАОБОРОТ.
Преподаватель, похоже, корочки купил... или просто баран - таких полно.
Угу, был недавно совсем похожий вопрос про циклы, оказалось препод - баран
0
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
07.10.2010, 17:44 #13
А цикл
C++
1
2
3
do {
   ...
} while ()
Всегда ли он представим в виде рекурсии?
0
Nameless One
Эксперт С++
5775 / 3425 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
07.10.2010, 17:47 #14
#pragma, почему бы и нет?
C
1
2
3
4
5
6
7
8
9
10
11
12
13
do
{
   тело
}
while(условие);
 
//...
void rec()
{
   тело
   if(условие)
      rec();
}
0
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
07.10.2010, 17:49 #15
Но ведь условие должно проверяться после исполняемого блока. Может,препод в этом контексте спрашивал?
0
07.10.2010, 17:49
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.10.2010, 17:49
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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