Отправляет email-рассылки с помощью сервиса Sendsay

Системное программирование, теория и практика

Подписаться Бесплатная новостная рассылка Подписчиков 3 RSS
←   Февраль 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


За последние 60 дней ни разу не выходила


Сайт рассылки: http://pishemprogi.ru
Открыта: 24-01-2009

Автор
Rostislav Luzhnik

Статистика

3 подписчиков
0 за неделю
←   Все выпуски   →

Системное программирование, теория и практика 'Рекурсивный алгоритм'


Рекурсивный алгоритм

Рекурсия является самым популярным методом построения алгоритмов. На этом примере многие учителя любят предлагать своим ученикам теорию алгоритмов. Но рекурсия не так проста, как оказывается, для понимания среднестатическому студенту.
Для начала: рекурсия как таковая не является алгоритмом, но она есть метод построения алгоритмов. Ее очень удобно использовать, но не обязательно эффективно, в тех случаях, когда можно выделить подобие задачи на саму себя, или. свести вычисление задачи определенной размерности N к вычислению подобных задач, но уже меньшей размерности.
Далее, если у нас получается сделать алгоритм без применения рекурсии, то, скорее всего, им и стоит воспользоваться. Давно известно, что рекурсивные вызовы имеют свойство решать одну и ту же задачу несчетное количество раз, что значительно ортажается на времени. И самым запоминающимся примером является традиционное исчисление чисел Фибоначчи, притом двумя способами: рекурсивным и итеративным.
Вспомним, что числами Фибоначчи называются числа, принадлежащие такой последовательности:
F0 = 0;
F1 = 1;
Fn = Fn-1 + Fn-2 для n > 1.
Наша задача состоит в том, чтобы найти по заданному числу n число последовательности Фибоначчи Fn.
Идем дальше. Смотря на определение последовательности, нам сразу приходит на ум использование рекурсии примерно вот таким образом. Приведем кусок такого кода для уяснения:

#include <stdio.h>
#include <time.h>

long F(unsigned int n)
{
  return n <= 1 ? n : F(n-1) + F(n-2);
}

int main()
{
  time_t begin, end;
  long res;

  for(int n = 0; n < 40; n++)
  {
    time(&begin);
    res = F(n);
    time(&end);

    printf(”%-3i\t%-9li\t%-20.3f\n”,n,res,difftime(end,begin));
  }

  return 0;
}

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


Узнайте больше о программах и программировании: Системное программирование
В избранное