Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > методы построения Рекурсии

Автор: ShadowC 13.9.2011, 15:30

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

Автор: newbee 13.9.2011, 15:34

SICP. Книга такая, рекурсии учит, правда не на С++, но это не важно при изучении рекурсии.

Автор: IlyaIvanov 13.9.2011, 17:59

Ну здесь все просто. Как в песне Максима Леонидова "Я оглянулся посмотреть не оглянулась ли она чтоб посмотреть не оглянулся ли я" smile

Рекурсия это функция, которая запускает сама себя.
Вот пример :
Вам нужно посчитать n!=1*2*...*n.
Итеративно Вы это делали так

Код


long int f=1;
for (int i=1; i<=n; i++)
f*=i;

Теперь напишем рекурсивно то же самое :

Код


long int f (long int i)
{
if (i==1)
return 1;
return i*f(i-1);
}

Получается что функция которая получила значение 5 возвратит 5* и вызовет сама себя с 4-кой, которая в свою очередь вернет 4* и запустит опять же сама себя с 3-кой. Закончатся рекурсивные запуски, когда параметр будет = 1. Итого получим 5*4*3*2*1. Тот же самый факториал.

Автор: shara 14.9.2011, 09:22

(простити не удержался)

Чтобы понять рекурсию, нужно понять рекурсию... smile

Автор: borisbn 14.9.2011, 11:13

Исчо один

(навеяно предыдущим)
http://goo.gl/Hjkk6

Автор: ShadowC 14.9.2011, 11:39

пля ребят вы прям копетаны,что бы понять рекурсию надо понять рекурсию,хорошо приведу более конкретный пример,если мне надо составить древо рекурсии для ханойской башни,мне что 4 часа сидеть и веточки рисовать просчитывая все возможные варианты?

Автор: 502 14.9.2011, 11:59

Цитата(ShadowC @ 14.9.2011, 11:39

)

а ты что хотел, 5 мин и готово?

Автор: ShadowC 14.9.2011, 12:38

Цитата(502 @ 14.9.2011, 11:59)

Цитата(ShadowC @ 14.9.2011, 11:39

)

а ты что хотел, 5 мин и готово?

ну не 5 минут,но мне кажется это диким,вот так создавать рекурсивные алгоритмы

Автор: RastaDja 14.9.2011, 13:17

вот алгоритм:
   1. Создать функцию foo(Type par)
   2. Внутри функции проверить какой-нибудь алгоритм над параметром par (таких параметров может быть несколько).
   3. Если нашел решение, прекращаешь рекурсию(рекурсия прекращается если ты больше не вызываешь функцию еще раз), если не нашел, вызываешь функцию внутри себя.

Код


void foo(int a)
{
    if( a > 0 )
    {
        cout >> a;
        foo( a - 1 );
    }
    else
    {
        //  прекращается рекурсия, кода нету
    }
}

Автор: newbee 14.9.2011, 13:22

Цитата(ShadowC @ 14.9.2011, 12:39

)

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

Автор: RastaDja 14.9.2011, 13:24

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

Код


int foo1(int par)
{
   int tmp = par * rand();
   if(tmp > 10 && tmp < 100) 
   {
      return foo2(tmp );   //  другая рекурсивная функция
   }
   else
   {
      return foo1();   // рекурсия
   }
}

int foo2(int par)
{
    if( par > 0 )
    {
        return foo2(par - 1)
    }
    else
    {
        return 0;
    }
}

так же внутри foo2() можешь вызвать foo1() и т.д.

Автор: ShadowC 14.9.2011, 14:26

Цитата(newbee @ 14.9.2011, 13:22)

Цитата(ShadowC @ 14.9.2011, 12:39

)

да не про тебя речь,речь про тех кто влез со своими smile

,тем кто посоветовал что-то дельное огромное спасибо и ты в их числе

Автор: xvr 14.9.2011, 16:24

Цитата(ShadowC @ 13.9.2011, 15:30

)

может быть сможете дать какие нибудь ценные советы,

Самое главное в рекурсии - не забыть из нее выйти smile

Я как то смотрел, как один перец писал рекурсивное вычисление факториала (писал он на Pascal'е, но я буду на С)
Первый вариант был таким:

Код


int fact(int v)
{
 return v*fact(v-1);
}

после чего он обвинил компилятор в багах ОС в ущербности - не смогла понимаешь стек выделить побольше smile

Когда ему намекнули, что в рекурсии должна быть как минимум проверка на ее окончание, он родил 2й вариант:

Код


int fact(int v)
{
 int rv=v*fact(v-1);
 if (v==0) return 1;
 return rv;
}

результат - 2й круг обвинений smile

В общем 3й вариант заработал, но это уже было не интересно smile

Автор: ShadowC 14.9.2011, 18:04

Цитата(xvr @ 14.9.2011, 16:24)

Цитата(ShadowC @ 13.9.2011, 15:30

)

может быть сможете дать какие нибудь ценные советы,

Самое главное в рекурсии - не забыть из нее выйти smile

Код


int fact(int v)
{
 return v*fact(v-1);
}

после чего он обвинил компилятор в багах ОС в ущербности - не смогла понимаешь стек выделить побольше smile

Когда ему намекнули, что в рекурсии должна быть как минимум проверка на ее окончание, он родил 2й вариант:

Код


int fact(int v)
{
 int rv=v*fact(v-1);
 if (v==0) return 1;
 return rv;
}

результат - 2й круг обвинений smile

В общем 3й вариант заработал, но это уже было не интересно smile

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

Автор: mes 14.9.2011, 19:25

Цитата(IlyaIvanov @ 13.9.2011, 16:59

)

Код


long int f=1;
for (int i=1; i<=n; i++)
f*=i;

Цитата(IlyaIvanov @ 13.9.2011, 16:59

)

Код


long int f (long int i)
{
if (i==1)
return 1;
return i*f(i-1);
}

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