C - рекурсия

Здравейте!

Чета една книжка за C.
Но нещо немога да схвана обяснението за рекурсията

За пример е даден следния код:

#include <stdio.h>

void recurse(int i);

int main(void)
{
recurse(0);
printf("\n");

system("PAUSE");
return 0;
}

void recurse(int i)
{
if(i<10) {
recurse(i+1);
printf("%d ", i);
}

}

Програмата отпечатва 9 8 7 6 5 4 3 2 1 0.

Рекурсията е фунцкия която може да извика сама себе си.
Добре...

Донякъде схванах смисъла, но пак нещо не ми е ясно.
Някой може ли да ми обясни по-просто как този код отпечатва 9 8 7 6 5 4 3 2 1 0.

Поздрави!

а ти защо не проиграеш програмата на ръка? не се ли научиш да проиграваш парчета код на ръка нямаш шанс.

размени местата на

recurse(i+1);
printf("%d ", i);

и ще ги отпечатва в обратен ред

Рекурсията не е функция, а понятие. Ако една функция извиква себе си (пряко или непряко) имаш рекурсия.
Идеята при рекурсията е да решиш една задача, чрез свеждането й до същата, но по-малка задача докато стигнеш до тривиален случай. Примерът който е даден не е особено удачен, защото това не се вижда добре.
Добър пример са досадно известните числа на Фибоначи.

F(0) = 0
F(1) = 1
F(I) = F(I-2)+F(I-1)

те образуват следната редица:

0 : 0
1 : 1
2 : 1
3 : 2
4 : 3
5 : 5
6 : 8
7 : 13
...

Ето една рекурсивна функция, която по зададен параметър N , N >= 0, намира съответното число на Фибоначи:

unsigned Fib( unsigned n )

{

 switch(n)

 {

  case 0: return 0;

  case 1: return 1;

 }

 return Fib(n-2) + Fib(n-1);

}

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Извикването recurse(0) е еквивалентно на следния код, който (предполагам, би трябвало) ще ти помогне да разбереш какво става всъщност:

// recurse(0)

{

  //recurse(1);

  {

    //recurse(2);

    {

      //recurse(3);

      {

        //recurse(4);

        {

          //recurse(5);

          {

            //recurse(6);

            {

              //recurse(7);

              {

                //recurse(8);

                {

                  //recurse(9);

                  {

                    //recurse(10);

                    {

                    }

                    printf("9 ");

                  }

                  printf("8 ");

                }

                printf("7 ");

              }

              printf("6 ");

            }

            printf("5 ");

          }

          printf("4 ");

        }

        printf("3 ");

      }

      printf("2 ");

    }

    printf("1 ");

  }

  printf("0 ");

}

"Всички науки са или физика, или колекциониране на пощенски марки." (Е. Ръдърфорд)

Всъщност голямото предимство на рекурсията се очаква да бъде по-лесна четимост. Откъм сложност на алгоритъма, предпочитат се итеративните подходи. Най-лошото, което можеш да направиш, е да смяташ рекурсивно числата на Фибоначи. Тогава от линеен, алгоритъмът се превръща в експоненциален. Най-често е желателно да не се използва рекурсия.

Има и случай, когато рекурсията е неизбежна.

Whenever you find yourslef on the side of the majority, it is time to reform.
~Mark Twain

"Има и случай, когато рекурсията е неизбежна."
впрочем няма, но е доста по удобно да напишеш
do_next(x) {
if (left) do_next(left);
if (right) do_next(right);
}
от колкото да въртиш 5 вложени цикъла :)

Ами сещам се за унищожаване на свързан списък.

Whenever you find yourslef on the side of the majority, it is time to reform.
~Mark Twain

Не съм съгласен, в някои случай сложността на алгоритъм алтернативен на рекурсията граничи с невъзможност. Ето ти един прост пример - да събереш имената на всички директории които се съдържат индиректно в някаква дадена директория. С рекурсия това е елементарно, но ако се опиташ да я избегнеш ще трябва доста да се поизпотиш. Аз се опитах да измисля преди време точно по този повод някакво нерекурсивно решение, ама все към рекурсия ме влечеше. Не си спомням да намерих алтернатива.

Сега като споменах този пример се сетих, абе в ООП как точно се пада по родова линия извикване на метод от същия метод, но от друга инстанция на класа. Т.е. примерно getDirs() calls getDirs() на своя поддир, нещо като баджанашка рекурсия ли е, що ли?


Мечтата е мисъл, мисълта е идея, всяка идея се реализира. Аз не мечтая, а реализирам идеите си.

"Ето ти един прост пример - да събереш имената на всички директории които се съдържат индиректно в някаква дадена директория."

един стек и си готов
дефакто самата рекурсията използва стек, просто прави нещата по "четливи" :)

абе хора стегнете се - стига сте говорили глупости -

единия унищожавал свързан списък с рекурсия,

другия - директории обхождал... интересно като имаш толкова вложени колкото аз имам какъв стек ще ти трябва...

Сигнатура!

Стекът си е стек - пази данни. А как ще организираш самото събиране на данните?

Мечтата е мисъл, мисълта е идея, всяка идея се реализира. Аз не мечтая, а реализирам идеите си.

Че кво лошо има в обхождането?

Едно време даже Хиподил възпяха тази процедура:

А може би, а може би обхождане с език,
защо ли не, защо ли не, обхождане с език?


Мечтата е мисъл, мисълта е идея, всяка идея се реализира. Аз не мечтая, а реализирам идеите си.

без да имам нужда от рекурсии.
И съответно не бях наясно яде ли се пие ли се?
Ма се сблъсквам един ден с някакво проблемче дето реве за рекусрсийка - така де все пак имах най-бегла представа за какво става дума.
Е спретнах я и го реших.
Та ако успееш да чакълдисаш общия принцип - достатъчно е.
Някой ден ако ти дотрябва ще я разбереш

Bеer? Mоre?
Плацебото

Има ли наистина случаи, в които е неизбежна или винаги е сводима до итерация ...

абе напоследък тенденцията беше към писане на четлив код, не на бърз
така, че ако едно нещо се представя рекурсивно (дървовидна структура), тогава е напълно логично да направиш алгоритъм-а рекурсивен
ако ще се правим на тежкари, тогава трябва да ходим да работим към някой екип за разработване на хипер бързи алгоритми, които само създателите им ще знаят как работят

Пич понятието ефективност нещо говори ли ти ?

template <class T> CList<T>::DestroyList()
{
ST *pNext = NULL;
ST *pCur = GetHead(); // първият елемент

while( pCur )
{
pNext = pCur->m_pNext;

delete pCur;
pCur = pNext;
}

}


Фрашкано с рекурсия, а ?

CArray<CString, CString&> GetSubDirs( CString &a_rstrDir )
{
CArray<CString, CString&> arstrName;
CFileFind ffWander;
bool bAny;
CString strSub;
int iDir;

arstrName.Add( a_rstrDir );
iDir = 0;

do
{
// Обхождане на ,,следващата'' директория
strSub = arstrName [iDir++] + "\\*.*";
bAny = ffWander.FindFile( strSub );

while( bAny )
{
bAny = ffWander.FindNextFile();

if ( ffWander.IsDots() )
continue;

if( ffWander.IsDirectory() )
arstrName.Add( ffWander.GetFilePath() );
}
}
while( bAny );

return arstrName;
}

Съществува теорема в теорията на алгоритмите, която доказва, че всеки рекурсивен алгоритъм може да се представи като итеративен и обратно. Отделен е въпросът доколко тази сводимост е лесна. В този смисъл threed е прав.
Повечето случаи се решават лесно с итерация и тя е за предпочитане от програмна гледна точка, но не мисля да пропускаш рекурсията, дори и само в теоретичен аспект. Понякога рекурсията просто се набива в очите, но са редки случаите, когато е трудно да й се намери итеративен еквивалент. Добро обяснение на твоя пример е дал xp. И аз мисля, че примера от тази книга не е сполучлив. Като класически и много прост пример е изчисляването на факториел. Опитай с него, докато не го разбереш. Там базовото условие е само едно:

n! = n*(n-1)! <=> f(n) = n*f(n-1)
0! = 1 <=> f(0) = 1 <-- базово условие
n - естествено число.

Факториала, числата на Фибоначи и т.н. са примери за проста рекурсия. Съществува и сложна рекурсия, при която 2 или повече функции се извикват помежду си.

void main() { main(); }

CArray<CString, CString&> GetSubDirs( CString &a_rstrDir )
{
CArray<CString, CString&> arstrName;
CFileFind ffWander;
bool bAny;
CString strSub;
int iDir;

arstrName.Add( a_rstrDir );
iDir = 0;

do
{
// Обхождане на ,,следващата'' директория
strSub = arstrName [iDir++] + "\\*.*";
bAny = ffWander.FindFile( strSub );

while( bAny )
{
bAny = ffWander.FindNextFile();

if ( ffWander.IsDots() )
continue;

if( ffWander.IsDirectory() )
arstrName.Add( ffWander.GetFilePath() );
}
}
while( iDir < arstrName.GetSize() ); // вместо while( bAny )

return arstrName;
}