Главная » Алгоритмы » Рекурсия

0

Кто получил специальное образование (повезло с преподавателем) или сам занимался этим вопросом, тот, несомненно, знает преимущества рекурсив­ных алгоритмов. В обычных учебниках им отводится до смешного мало места или не отводится вообще. Популярно следующее замечание: "Любая задача, решенная с помощью рекурсии, может быть решена и обычным способом". Это так, если моделировать стек программы. Некоторые задачи, тем не менее, практически невозможно решить без рекурсии. Объем кода неимоверно возрастает, и без всякой пользы.

— это вызов из функции самой себя. Это допустимо даже в Бей­сике. Функция вызывает сама себя, при этом все переменные (стековые), кроме статических, задаются заново. Если у нас есть некоторая функция Foo и переменная dummy, то dummy всегда новая при следующем вызове функции.

Приведем пример "пустой" рекурсии. Функция вызывает сама себя и не со­вершает никакой полезной работы. Единственное, нужно ограничить коли­чество рекурсивных вызовов некоторым реальным числом:

void Foo(int callNumber) {

if(callNumber <= 0) return;

Foo(callNumber-1); }

Пример первого вызова функции:

Foo(10);

Функция Foo вызывает себя 10 раз, и программа завершается. Значение callNumber уменьшается при каждом вызове, и если равно нулю, дальней­ших рекурсивных вызовов нет. Переменная callNumber обозначает глубину рекурсии и обычно называется depth. Ключевое слово void обозначает, что функция не возвращает никакого значения. В языке С нет специально заре­зервированного слова function. Оно подразумевается. В С++ мы можем не писать void (его можно опустить и в некоторых версиях языка С). Тогда будет подразумеваться, что функция возвращает целочисленный тип со зна­ком — int. Размерность типа int равна разрядности регистра аккумулятора (еах или ах) процессора. Для 16-разрядных программ это 16, для 32-раз- рядных — 32 бита. Напишем:

Foo(int depth) {

if(depth > 0) Foo(depth-1);

return 0;

}

Можно, без привычки, не сразу и догадаться, что перед нами сигнатура функции. Возвращаемое значение 0, в данном случае, неинформативно. Некоторые компиляторы позволяют опускать его. Это ненужные тонкости. Желательно, если функция не возвращает значения, писать явно void.

Это же относится и к списку аргументов функции. Если аргументов нет, то в С нужно обязательно указать:

void Foo(void);

В С++ слово void можно опустить и просто написать: void Foo();

Давайте заставим нашу рекурсивную функцию совершить какую-нибудь по­лезную работу. Например, вычислить возведение числа в степень.

int Foo(int value, int n) {

if(n == 0) return 1;

return value * Foo(value,n-1); }

Описанная функция не вычисляет отрицательные степени. Это как раз не­удачный пример рекурсии, и задача может быть легко решена без нее:

int Foo(int value, int n) {

int tmp = 1; for(;n > 0; n—) trap = tmp * value;

return tmp; }

В некоторых случаях рекурсия, тем не менее, оказывается очень полезной. Вот пример.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии