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

@KBAC · Регистрация: 10.05.2010

Author24 — интернет-сервис помощи студентам

Как известно(по некоторым источникам

) любую рекурсию можно представить в виде цикла, но не наоборот. Так вот, надо придумать пример, который будет наглядно показывать , что итеративный вариант единственно возможный в данном случае.
Я по этому поводу пока ничего вразумительного предположить не могу ..

@HIMen · 05.10.2010, 23:53

Сообщение от KBAC

любую рекурсию можно представить в виде цикла, но не наоборот

И наоборот тоже

@KBAC · 06.10.2010, 17:26 **[ТС]**

а я надеялся тут целую дискуссию развернуть..

@odip · 07.10.2010, 07:46

Насчет что любой цикл можно представить в виде рекурсии - чего-то я не уверен

C

double s= 0.0;
for ( i= 0; i<=1000000; i++ ) {
   s+= sin( i );
}

Ну-ка сделайте мне это в виде рекурсии и чтобы ПОСЧИТАЛО !

@mamedovvms · 07.10.2010, 08:17

C++

double f= 0.0;
for ( i= 1; i<=1000000; i++ ) {
   f*= i;
}

может быть я что то не догоняю, но я написал цикл, для поиска факториала, и как вы думаете он сильно отличается от вашего, но для него то точно можно написать рекурсию, и во многих учебниках есть даже примеры

C++

 double Factorial(int N)
  {
    double F;
    if (N<=1) F=1.; else F=Factorial(N-1)*N;
    return F;
  }

так что для вашего цикла будет так

C++

 double Factorial(int N)
  {
    double F;
    if (N=0) F=sin(0).; else F=sin(Factorial(N-1)) + sin(N);
    return F;
  }

@HIMen · 07.10.2010, 11:48

Сообщение от odip

Ну-ка сделайте мне это в виде рекурсии и чтобы ПОСЧИТАЛО !

C#

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 · 07.10.2010, 14:08

odip,
Может, ТС имел ввиду не практическую значимость, а абстрактный пример, в котором цикл действительно нельзя записать в виде рекурсии (в не зависимости от того, будет это фактически работать или нет)?

@KBAC · 07.10.2010, 15:49 **[ТС]**

я на эту тему много голову ломал, что именно мне надо ) у меня с преподом вышел разговор за экзамен в котором он мне сказал : "любую рекурсию можно заменить ... , приведите пример такой итерации". Так что мне не понятно даже в каком направлении должно быть различие .

Добавлено через 1 минуту
не различие а именно невозможность замены

@Nameless One · 07.10.2010, 16:39

Сообщение от odip

Насчет что любой цикл можно представить в виде рекурсии - чего-то я не уверен

C

double s= 0.0;
for ( i= 0; i<=1000000; i++ ) {
   s+= sin( i );
}

Ну-ка сделайте мне это в виде рекурсии и чтобы ПОСЧИТАЛО !

C

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

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 · 07.10.2010, 17:32

Сообщение от Nameless One

рекурсия не простая, а хвостовая

Что-то никак я этой штукой пользоваться не научусь

По теме же - по-моему и циклы и рекурсия полностью взаимозаменяемы, т.к. делают по сути одно и то же, но разными путями. Другое дело - при обычной (не хвостовой) рекурсии действительно может переполнение стека случиться, так и цикл можно криво написать...

@Patch · 07.10.2010, 17:39

Подтверждаю: любую рекурсию можно представить в виде цикла, И НАОБОРОТ.
Преподаватель, похоже, корочки купил...

или просто баран - таких полно.

@LineStown · 07.10.2010, 17:44

Сообщение от Patch

Подтверждаю: любую рекурсию можно представить в виде цикла, И НАОБОРОТ.
Преподаватель, похоже, корочки купил...

или просто баран - таких полно.

Угу, был недавно совсем похожий вопрос про циклы, оказалось препод - баран

@#pragma · 07.10.2010, 17:44

А цикл

C++

1
2
3

do {
   ...
} while ()

Всегда ли он представим в виде рекурсии?

@Nameless One · 07.10.2010, 17:47

#pragma, почему бы и нет?

C

do
{
   тело
}
while(условие);
 
//...
void rec()
{
   тело
   if(условие)
      rec();
}

@#pragma · 07.10.2010, 17:49

Но ведь условие должно проверяться после исполняемого блока. Может,препод в этом контексте спрашивал?

@Nameless One · 07.10.2010, 17:52

#pragma,

C

do
{
тело
}
while(условие);
 
//...
void rec()
{
   тело // сначала выполняется тело
   if(условие) // потом проверяется условие
      rec(); // если условие верно, выполняется еще одна итерация и т.д.
}

@#pragma · 07.10.2010, 17:54

Ой,и правда

Ну тогда сдаюсъ

silent_1991 · 07.10.2010, 18:11

Сообщение от LineStown

Угу, был недавно совсем похожий вопрос про циклы, оказалось препод - баран

Помню-помню

@PointsEqual · 07.10.2010, 18:19

а в чем отличие хвостовой от обычной рекурсии?

silent_1991 · 07.10.2010, 18:29

PointsEqual,
Хвостовая обычно заменяется в итоге на цикл, поскольку сама рекурсивная функция последней операцией содержит вызов самой себя без выполнения каких-либо иных операция, что аналогично переходу на следующую итерацию цикла.

Добавлено через 3 минуты
Т.е., скажем, факториал, в стандартной своей рекурсивной реализации, не заменится при компилятором на цикл, поскольку там после вызова рекурсивной функции её результат умножается на n, а цикл мы умножить ни на что не можем)))

@LineStown 72 / 71 / 8 Регистрация: 04.08.2010 Сообщений: 434
	07.10.2010, 17:44	12
	Сообщение от Patch Подтверждаю: любую рекурсию можно представить в виде цикла, И НАОБОРОТ. Преподаватель, похоже, корочки купил... или просто баран - таких полно. Угу, был недавно совсем похожий вопрос про циклы, оказалось препод - баран 0

@KBAC 2 / 2 / 1 Регистрация: 10.05.2010 Сообщений: 72
		1
	Пример, подтверждающий что не любую итерацию можно заменить рекурсией 05.10.2010, 23:36. Показов 10390. Ответов 45 Метки нет (Все метки) Как известно(по некоторым источникам ) любую рекурсию можно представить в виде цикла, но не наоборот. Так вот, надо придумать пример, который будет наглядно показывать , что итеративный вариант единственно возможный в данном случае. Я по этому поводу пока ничего вразумительного предположить не могу .. 0

@HIMen 4337 / 1506 / 101 Регистрация: 12.04.2009 Сообщений: 2,342
	05.10.2010, 23:53	2
	Сообщение от KBAC любую рекурсию можно представить в виде цикла, но не наоборот И наоборот тоже 0

@KBAC 2 / 2 / 1 Регистрация: 10.05.2010 Сообщений: 72
	06.10.2010, 17:26 [ТС]	3
	а я надеялся тут целую дискуссию развернуть.. 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	07.10.2010, 14:08	7
	odip, Может, ТС имел ввиду не практическую значимость, а абстрактный пример, в котором цикл действительно нельзя записать в виде рекурсии (в не зависимости от того, будет это фактически работать или нет)? 0

@KBAC 2 / 2 / 1 Регистрация: 10.05.2010 Сообщений: 72
	07.10.2010, 15:49 [ТС]	8
	я на эту тему много голову ломал, что именно мне надо ) у меня с преподом вышел разговор за экзамен в котором он мне сказал : "любую рекурсию можно заменить ... , приведите пример такой итерации". Так что мне не понятно даже в каком направлении должно быть различие . Добавлено через 1 минуту не различие а именно невозможность замены 0

@easybudda Модератор 12460 / 7484 / 1754 Регистрация: 25.07.2009 Сообщений: 13,762
	07.10.2010, 17:32	10
	Сообщение от Nameless One рекурсия не простая, а хвостовая Что-то никак я этой штукой пользоваться не научусь По теме же - по-моему и циклы и рекурсия полностью взаимозаменяемы, т.к. делают по сути одно и то же, но разными путями. Другое дело - при обычной (не хвостовой) рекурсии действительно может переполнение стека случиться, так и цикл можно криво написать... 0

@Patch 2343 / 499 / 22 Регистрация: 01.04.2009 Сообщений: 2,200
	07.10.2010, 17:39	11
	Подтверждаю: любую рекурсию можно представить в виде цикла, И НАОБОРОТ. Преподаватель, похоже, корочки купил... или просто баран - таких полно. 0

@#pragma Временно недоступен 957 / 228 / 14 Регистрация: 12.04.2009 Сообщений: 926
	07.10.2010, 17:49	15
	Но ведь условие должно проверяться после исполняемого блока. Может,препод в этом контексте спрашивал? 0

@#pragma Временно недоступен 957 / 228 / 14 Регистрация: 12.04.2009 Сообщений: 926
	07.10.2010, 17:54	17
	Ой,и правда Ну тогда сдаюсъ 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	07.10.2010, 18:11	18
	Сообщение от LineStown Угу, был недавно совсем похожий вопрос про циклы, оказалось препод - баран Помню-помню 0

@PointsEqual ниначмуроФ 851 / 535 / 110 Регистрация: 12.10.2009 Сообщений: 1,913
	07.10.2010, 18:19	19
	а в чем отличие хвостовой от обычной рекурсии? 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	07.10.2010, 18:29	20
	PointsEqual, Хвостовая обычно заменяется в итоге на цикл, поскольку сама рекурсивная функция последней операцией содержит вызов самой себя без выполнения каких-либо иных операция, что аналогично переходу на следующую итерацию цикла. Добавлено через 3 минуты Т.е., скажем, факториал, в стандартной своей рекурсивной реализации, не заменится при компилятором на цикл, поскольку там после вызова рекурсивной функции её результат умножается на n, а цикл мы умножить ни на что не можем))) 1