Спонсоры сайта:

Наличие этой страницы в поиске?

Информеры ТИЦ и PR

  Yandex ТИЦ:  
   Google PR:  

Путешественникам, меломанам, бизнесменам, вебмастерам, новости.

Содержание | <<< | >>>

Рекурсия





В языке С функция может вызывать сама себя. В этом случае такая функция называется рекурсивной. Рекурсия — это процесс определения чего-либо на основе самого себя, из-за чего рекурсию еще называют рекурсивным определением.

Простым примером рекурсивной функции является factr(), которая вычисляет факториал целого неотрицательного числа. Факториалом числа n (обозначается n!) называется произведение всех целых чисел, от 1 до n включительно (для 0, по определению, факториал равен 1.). Например, 3! — это 1×2×3, или 6. Здесь показаны factr() и эквивалентная ей функция, в которой используется итерация:

/* рекурсивная функция */
int factr(int n) {
  int answer;

  if(n==1) return(1);
  answer = factr(n-1)*n; /* рекурсивный вызов */
  return(answer);
}

/* неркурсивная функция */
int fact(int n) {
  int t, answer;

  answer = 1;

  for(t=1; t<=n; t++)
    answer=answer*(t);

  return(answer);
}

Нерекурсивное вычисление факториала, то есть вычисление с помощью fact(), выполняется достаточно просто. В этой функции в теле цикла, выполняющемся для t от 1 до n, вычисленное ранее произведение последовательно умножается на каждое из этих чисел. (Значение факториала для 0 получается, конечно, с помощью оператора присваивания. Значение факториала для 1 также получается умножением не на ранее полученное произведение, а на заранее подготовленное число, тоже равное 1.)

Работа же рекурсивной функции factr() чуть более сложная. Когда factr() вызывается с аргументом 0, то она сразу возвращает 1. Если же аргумент больше 0, то возвращается произведение factr(n-1)*n. Чтобы вычислить значение этого выражения, factr() вызывается с аргументом n-1. Это выполняется до тех пор, пока n не станет равным 0. Когда это произойдет, вызовы функции начнут возвращать вычисленные ими значения факториалов.

При вычислении 2! первый вызов factr() влечет за собой второй, теперь уже рекурсивный вызов с аргументом 1, который, в свою очередь, влечет третий, тоже рекурсивный вызов с аргументом 0. Этот вызов возвращает число 1, которое затем умножается на 1, а потом на 2 (первоначальное значение n). Ответ в данном случае равен 2. Попробуйте самостоятельно вычислить 3!. (Вам, возможно, захочется вставить в функцию factr() выражения printf(), чтобы видеть уровень каждого вывода, и то, какие будут промежуточные ответы.)

Когда функция вызывает сама себя, новый набор локальных переменных и параметров размещается в памяти в стеке, а код функции выполняется с самого своего начала, причем используются именно эти новые переменные. При рекурсивном вызове функции новая копия ее кода не создается. Новыми являются только значения, которые использует данная функция. При каждом возвращении из рекурсивного вызова старые локальные переменные и параметры извлекаются из стека, и сразу за рекурсивным вызовом возобновляется работа функции. При использовании рекурсивных функций стек работает подобно "телескопической" трубе, выдвигающейся вперед и складывающейся обратно.

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

Главным преимуществом рекурсивных функций является то, что с их помощью упрощается реализация некоторых алгоритмов, а программа становится понятнее. Например, алгоритм быстрой сортировки (описанный в части IV) трудно реализовать итеративным способом. Кроме того, для некоторых проблем, особенно связанных с искусственным интеллектом, больше подходят рекурсивные решения. И наконец, некоторым людям легче думать рекурсивными категориями, чем итеративными.

В тексте рекурсивной функции обязательно должен быть выполнен условный оператор, например if, который при определенных условиях вызовет завершение функции, т.е. возврат, а не выполнит очередной рекурсивный вызов. Если такого оператора нет, то после вызова функция никогда не сможет завершить работы. Распространенной ошибкой при написании рекурсивных функций как раз и является отсутствие в них условного оператора. При создании программ не отказывайтесь от функции printf(); тогда вы сможете увидеть, что происходит на самом деле и сможете прервать выполнение, когда обнаружите ошибку.


Содержание | <<< | >>>

C++ исходники. Все примеры - рабочие:

часы:

Dev C++ WinAPI Стрелочные часы Analog Clock

Dev C++ WinAPI Цифровые прозрачные часы. Текст на рабочем столе. Digital transparent clock. Text on desktop

Dev C++ OLE WinApi CALENDAR and DIGITAL CLOCK (15kb). Календарь и цифровые часы

Dev C++ OLE WinAPI Календарь и цифровые часы почти Vista SideBar всего 21kb

плееры:

Microsoft Visual C++ 2008 Direct Show DVD Mini Player 10.5kb

Dev C++ WinAPI Микро медиа плеер 3.5kb

Dev C++ WinAPI Мини медиа плеер 4.5kb

Dev C++ WinAPI Hint Всплывающая подсказка

Dev C++ WinAPI RECT - имитатор кнопки

Dev C++ WinAPI Заполнить ListBox

Dev C++ WinAPI Заполнить, редактировать, сохранить, загрузить ListBox (PlayList)

Dev C++ WinAPI Индикатор уровня

Dev C++ WinAPI MP3 Микро плеер Открыть с помощью...

Dev C++ WinAPI Своя кнопка

изображения:

Dev C++ GDI+ WinAPI Mini FotoResizer (16kb), изменяет размеры всех фото (JPG) до указанного размера в выбраной папке и её подпапках

Dev C++ WinAPI Сохранить BITMAP экрана, десктопа, окна, клиентской области.

Dev C++ WinAPI Изменить размер изображения BMP RESIZE. Загрузка изображений из ФАЙЛА, вывод на экран и сохранение в файл.

Dev C++ WinAPI Загрузка изображений из РЕСУРСОВ и вывод на экран.

Dev C++ GDI+ WinAPI. Преобразовать изображения из одного формата в другой (JPG в BMP, GIF, PNG и обратно ), используя дополнительные библиотеки GDI+. Загрузка изображений из файла и сохранение в файл.

Dev C++ GDI+ WinAPI масштабирование JPG RESIZE

Dev C++ OLE WinAPI. Преобразовать изображения из JPG в BMP, используя дополнительные библиотеки OLE. Загрузка изображений из РЕСУРСОВ и сохранение в файл.

Dev C++ OLE WinAPI преобразовать JPG в BMP, используя дополнительные библиотеки OLE. Загрузка изображений из ФАЙЛА и сохранение в файл.

Dev C++ OLE WinAPI масштабирование BMP RESIZE

разное:

Dev C++ WinAPI Dev C++ Преобразовать цвет точки экрана в HTML код

Dev C++ WinAPI NOTIFYICONDATA WS_EX_TOOLWINDOW Иконка в области уведомлений (notification area, tray, трей). Удалить с панели задач (taskbar).

Dev C++ WinAPI ShellExecute Создать ссылку на WEB сайт

Dev C++ WinAPI ShellExecute Создать окно со ссылкой на WEB сайт

Dev C++ WinAPI CreateProcess ShellExecute WinExec Запуск приложения из приложения

Dev C++ OLE WinAPI Создать регион Regions PopUp Меню Menu

Dev C++ FindFiles. Поиск файлов заданного типа (в примере *.JPG) в папке и её подпапках

библиотеки:

Скачать библиотеку GDI+ для Dev C++

Скачать справочнник с примерами языка C.