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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.94
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
05.10.2010, 23:36     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #1
Как известно(по некоторым источникам ) любую рекурсию можно представить в виде цикла, но не наоборот. Так вот, надо придумать пример, который будет наглядно показывать , что итеративный вариант единственно возможный в данном случае.
Я по этому поводу пока ничего вразумительного предположить не могу ..
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
HIMen
 Аватар для HIMen
4105 / 1354 / 39
Регистрация: 12.04.2009
Сообщений: 2,346
05.10.2010, 23:53     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #2
Цитата Сообщение от KBAC Посмотреть сообщение
любую рекурсию можно представить в виде цикла, но не наоборот
И наоборот тоже
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
06.10.2010, 17:26  [ТС]     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #3
а я надеялся тут целую дискуссию развернуть..
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
07.10.2010, 07:46     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #4
Насчет что любой цикл можно представить в виде рекурсии - чего-то я не уверен
C
1
2
3
4
double s= 0.0;
for ( i= 0; i<=1000000; i++ ) {
   s+= sin( i );
}
Ну-ка сделайте мне это в виде рекурсии и чтобы ПОСЧИТАЛО !
mamedovvms
2913 / 834 / 93
Регистрация: 30.04.2009
Сообщений: 2,613
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;
  }
HIMen
 Аватар для HIMen
4105 / 1354 / 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?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
07.10.2010, 14:08     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #7
odip,
Может, ТС имел ввиду не практическую значимость, а абстрактный пример, в котором цикл действительно нельзя записать в виде рекурсии (в не зависимости от того, будет это фактически работать или нет)?
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
07.10.2010, 15:49  [ТС]     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #8
я на эту тему много голову ломал, что именно мне надо ) у меня с преподом вышел разговор за экзамен в котором он мне сказал : "любую рекурсию можно заменить ... , приведите пример такой итерации". Так что мне не понятно даже в каком направлении должно быть различие .

Добавлено через 1 минуту
не различие а именно невозможность замены
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
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);
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
07.10.2010, 17:32     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #10
Цитата Сообщение от Nameless One Посмотреть сообщение
рекурсия не простая, а хвостовая
Что-то никак я этой штукой пользоваться не научусь
По теме же - по-моему и циклы и рекурсия полностью взаимозаменяемы, т.к. делают по сути одно и то же, но разными путями. Другое дело - при обычной (не хвостовой) рекурсии действительно может переполнение стека случиться, так и цикл можно криво написать...
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
07.10.2010, 17:39     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #11
Подтверждаю: любую рекурсию можно представить в виде цикла, И НАОБОРОТ.
Преподаватель, похоже, корочки купил... или просто баран - таких полно.
LineStown
 Аватар для LineStown
63 / 63 / 3
Регистрация: 04.08.2010
Сообщений: 399
07.10.2010, 17:44     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #12
Цитата Сообщение от Patch Посмотреть сообщение
Подтверждаю: любую рекурсию можно представить в виде цикла, И НАОБОРОТ.
Преподаватель, похоже, корочки купил... или просто баран - таких полно.
Угу, был недавно совсем похожий вопрос про циклы, оказалось препод - баран
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
07.10.2010, 17:44     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #13
А цикл
C++
1
2
3
do {
   ...
} while ()
Всегда ли он представим в виде рекурсии?
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
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();
}
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
07.10.2010, 17:49     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #15
Но ведь условие должно проверяться после исполняемого блока. Может,препод в этом контексте спрашивал?
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
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
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
07.10.2010, 17:54     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #17
Ой,и правда Ну тогда сдаюсъ
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
07.10.2010, 18:11     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #18
Цитата Сообщение от LineStown Посмотреть сообщение
Угу, был недавно совсем похожий вопрос про циклы, оказалось препод - баран
Помню-помню
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
07.10.2010, 18:19     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #19
а в чем отличие хвостовой от обычной рекурсии?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.10.2010, 18:29     Пример, подтверждающий что не любую итерацию можно заменить рекурсией
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
07.10.2010, 18:29     Пример, подтверждающий что не любую итерацию можно заменить рекурсией #20
PointsEqual,
Хвостовая обычно заменяется в итоге на цикл, поскольку сама рекурсивная функция последней операцией содержит вызов самой себя без выполнения каких-либо иных операция, что аналогично переходу на следующую итерацию цикла.

Добавлено через 3 минуты
Т.е., скажем, факториал, в стандартной своей рекурсивной реализации, не заменится при компилятором на цикл, поскольку там после вызова рекурсивной функции её результат умножается на n, а цикл мы умножить ни на что не можем)))
Yandex
Объявления
07.10.2010, 18:29     Пример, подтверждающий что не любую итерацию можно заменить рекурсией
Ответ Создать тему
Опции темы

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