Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

Обычно, в программировании под рекурсией понимают такую реализацию, в которой подпрограмма использует в своем теле вызов самой себя. Такие вызовы называют рекурсивными. Когда функция A в своем теле вызывает только одну рекурсивную функцию (саму себя), то говорят о простой рекурсии. Под косвенной рекурсией понимают явление, когда рекурсивные функции вызывают друг друга (например, функция А вызывает B, а функция B вызывает A).

Прямая рекурсияКосвенная рекурсия
  void A(){
     Операторы;
     A();
     Операторы;
  }
  void A(){
     Операторы;
     B();
     Операторы;
  }   
  void B(){
     Операторы;
     A();
     Операторы;
  }

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

Факториал

Для рекурсивного решения задачи обычно мы стараемся решить задачу через саму себя (как это ни странно), но с меньшими параметрами. Например, самым простым примером рекурсивного решения служит задача о вычислении факториала. Конечно, факториал можно вычислить и без рекурсии, но рекурсивное решение выглядит изящнее. Здесь нужно определить некоторую функцию F(n), которая будет вычислять значение n! через саму себя. В данном случае воспользуемся рекурентной формулой: F(n) = F(n-1)*n. Учтем и условие выхода: если n меньше 2, то ответ равен 1. Таким образом, в тех случаях, когда n меньше 2х, функция не будет себя вызывать, что будет гарантировать выход из рекурсии. Описанные выше рассуждения преобразуем в следущую запись:

//Вычисление факториала
int F(int n){
  if n<2 then return 1;
         else return F(n-1)*n;
}

Числа Фибоначчи

Аналогично определим функцию для вычисления элементов ряда чисел Фибоначчи, исходя из рекурентного выражения F(n) = F(n-1) + F(n-2) :

//Вычисление n-го члена ряда Фибоначчи
int F(int n){
  if n<3 then return 1;
         else return F(n-1)+F(n-2);
}

Заметим, что несмотря на свою красоту, рекурсивная реализация для чисел Фибоначчи весьма не оптимальна и работает очень медленно, сильно уступает своем линейному аналогу.

Задача о Ханойской башне

Ханойская башня
ABC

Задача: Имеется три стержня, на один из которых нанизаны N колец, причем кольца отличаются размером и лежат меньшее на большем. Требуется перенести пирамиду из N колец с одного стержня на другой за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

Предположим, что мы хотим получить в итоге программу, которая по заданному значению N будет нам выводить последовательность действий, решающих задачу, т.е. алгоритм переноса всех колец со стержня А на стержень B. Действие переноса одного кольца будет иметь вид: A -> B, что означает перенос одного верхнего кольца со стержня с именем А, на стержень с именем B. Рассмотрим, как должны выглядеть решения для малых N:

N=1: A -> B
N=2: A -> C, A -> B, C -> B
N=3: A -> B, A -> C, B -> C, A -> B, C -> A, C -> B, A -> B

Решение: Для человека, не знакомого с рекурсией, задача кажется очень сложной. На самом деле поставленная задача о переносе N колец с одного стержня на другой с использованием 3го стержня как вспомогательного легко выражается через 2 подобных задачи для N-1 кольца и оптимальным решением поставленной задачи для N колец будет алгоритм, реализующий это за 2N-1 действий. Рассмотрим, как умея перекладывать N-1 кольцо возможно переложить N колец. Для этого необходимо выполнить следующие 3 действия:

  1. переложить N-1 кольцо с исходного на временный стержень
  2. переложить 1 кольцо с исходного на конечный стержень
  3. переложить N-1 кольцо с временного на конечный стержень

Заметим, что 0 и 1 кольцо мы умеем перекладывать. Для лучшего понимания следует сказать, что N-1 кольцо будет перекладываться через 2 действия с N-2 кольцами, N-2 кольца через 2 действия с N-3 кольцами и т.д. пока не опустимся до нуля. Отметим так же, что при переложении N-1 кольца, N-е (и кольца еще большего диаметра) никак не мешают. Опишем теперь эту рекурентную запись в виде функции:

//Функция, решающая задачу о Ханойской башне
//n - число колец, from - имя стержня-источника, to - имя стержня-приемника, temp - имя временного стержня
void Hanoi(int n, char from, char to, char temp){
  if(n>0){
    Hanoi(n-1, from, temp, to);
    writeln(from, '->', to);
    Hanoi(n-1, temp, to, from);
  }
}

Теперь для того, чтобы получить решение задачи для N=8 достаточно вызвать вышеописанную функцию, например, следующим образом:

Hanoi(8, 'A', 'B', 'C');

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Условный оператор
 Операторы цикла
 Строковые типы данных
 Массивы
 Функции
 Сортировка
 Двумерные массивы
 Рекурсия
 Рекурсия - 1
 Рекурсия - 2
 A. Разворот
 B. Числа Фибоначчи
 C. Перестановки
 D. Функция - 2
 E. Формула
 F. Задача о рюкзаке
 G. Покраска лабиринта
 H. Сумма двух чисел

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483