2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Рекурсивные функции C++
Сообщение26.04.2010, 20:08 
расскажите мне пожалуста кто-нибудь о рекурсивных функциях...если можно на примере деревьев..

 
 
 
 Re: Рекурсивные функции C++
Сообщение27.04.2010, 20:44 
Рекурсивные ф-ии - ф-ии, вызывающие сами себя. Старайтесь вообще никогда не использовать рекурсивные функции, т.к. рекурсия сильно замедляет работу программы. И вообще вызов любой(не встраиваемой) функции замедляет работу.

Как правило, в начале такой функции пишется условие выхода из рекурсии. Например, ф-ия факторила
Код:
int fuck(int n)
{
  if (n == 0) //Условие выхода из рекурсии
    return 1;
  return n*fuck(n - 1);
}


В то же время эту ф-ию можно(и нужно) переписать без рекурсии.
Код:
int fact(int n)
{
  if(n == 0)
    return 1;
  int temp = 1;
  for(int i = 1; i <= n; i++)
  {
    temp = temp*i;
  }
  return temp;
}


Кроме того, глубина рекурсии конечна, то есть следующая программа не будет работать сколь угодно долго, а очень даже быстро прекратит работу
Код:
void stack_overload()
{
  cout<<"-";
  return stack_overload();
}


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

Например, алгоритм обхода ЛКП:
Код:
void CTree<T>::Walk(CTree<T>* item)
{
  if (!item) return;

  Walk(item->Left);          //идём влево
  cout << item->value <<" "; //обратно в корень
  Walk(item->Right);         //идём вправо
}

 
 
 
 Re: Рекурсивные функции C++
Сообщение27.04.2010, 22:44 
Аватара пользователя
malin в сообщении #314008 писал(а):
Рекурсивные ф-ии - ф-ии, вызывающие сами себя. Старайтесь вообще никогда не использовать рекурсивные функции, т.к. рекурсия сильно замедляет работу программы. И вообще вызов любой(не встраиваемой) функции замедляет работу.

Или хорошо знайте Ваш компилятор и пишите так, чтобы рекурсия была соптимизирована до менее затратных операций. GCC умеет оптимизировать хвостовую рекурсию:
код: [ скачать ] [ спрятать ]
Используется синтаксис ASM
  1. .globl fuck
  2.         .type   fuck, @function
  3. fuck:
  4. .LFB3:
  5.         .cfi_startproc
  6.         testl   %edi, %edi
  7.         movl    $1, %eax
  8.         je      .L3
  9.         .p2align 4,,10
  10.         .p2align 3
  11. .L4:
  12.         imull   %edi, %eax
  13.         subl    $1, %edi
  14.         jne     .L4
  15. .L3:
  16.         rep
  17.         ret
  18.         .cfi_endproc
  19. .LFE3:
  20.         .size   fuck, .-fuck
  21.         .p2align 4,,15
  22. .globl fact
  23.         .type   fact, @function
  24. fact:
  25. .LFB4:
  26.         .cfi_startproc
  27.         cmpl    $0, %edi
  28.         je      .L8
  29.         jle     .L8
  30.         movl    $1, %edx
  31.         movl    $1, %eax
  32.         .p2align 4,,10
  33.         .p2align 3
  34. .L9:
  35.         imull   %edx, %eax
  36.         addl    $1, %edx
  37.         cmpl    %edx, %edi
  38.         jge     .L9
  39.         rep
  40.         ret
  41.         .p2align 4,,10
  42.         .p2align 3
  43. .L8:
  44.         movl    $1, %eax
  45.         ret
  46.         .cfi_endproc
  47. .LFE4:
  48.         .size   fact, .-fact
  49.         .section        .rodata.str1.1,"aMS",@progbits,1
  50.  

 
 
 
 Re: Рекурсивные функции C++
Сообщение30.04.2010, 04:34 

(Оффтоп)

Вот никогда бы не догадался, что функция fuck() вычисляет факториал, а, скажем, не выводит сообщение о критической ошибке. :)

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group