« Структуры данных и алгоритмы. Теория. Усовершенствованные алгоритмы сортировки Структуры данных и алгоритмы. Теория. Динамические структуры данных »

Структуры данных и алгоритмы. Теория. Рекурсия.

January 4, 2007

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

Представьте, что перед человеком и позади него поставили зеркало. Если человек посмотрит в переднее зеркало то увидит в нем себя и разумеется зеркало сзади, в котором он увидит отражение снова себя и переднего зеркала, в котором он увидит снова отражение себя и отражение заднего зеркала в котором… И так далее. Часто для демонстрации возможностей рекурсии используют такие математические объекты как факториал, цепные дроби. В качестве примера далее приводится пример кода рекурсивного и итеративного вычисления факториала:

Как известно из математики факториал числа 
 N! = 1*2*3 … (N-1)*N = (N-1)!*N.
При этом полагается значение 0! = 1.
Рекурсия Итерация 
  1. int factorial (int n){
  2. if (n == 0) return 1;
  3. return n*factorial (n-1);
  4. }
  5. …
  6. printf (“5! = %d” , factorial(5) );
 
  1. int n = 5;
  2. int f = 1;
  3. for (int i=1; i <=n; i++)
  4. f*=i;
  5. printf ("n!= %d" , f);
Рекурсия всегда выполняется в виде некоторой подпрограммы и состоит из условно двух частей: рекурсивной части и не рекурсивной. Давайте мы попытаемся по шагам пройти рекурсивное решение. Мы введем понятие уровня рекурсии: будем нумеровать эти уровни от нуля: уровень той функции которая первый раз вызывает рекурсивный алгоритм. Каждый раз когда рекурсивная процедура будет вызывать сама себя мы будем добавлять единичку к текущему уровню.
Уровень Описание и состояние переменных
0 Пока функция не вызвана
1 Значение N=5, согласно заданному условию результатом значения 5!=5*4! Следовательно, нам необходимо сделать рекурсивный вызов с N=N-1.
2 Значение N=4, мы еще не дошли до ситуации когда не требуется применение рекурсии и следовательно должны снова вызвать себя уже со значение N=3
3 N=3
4 N=2
5 N=1
6 N=0, ну наконец-то, рекурсивный спуск был завершен мы знаем значение факториала при N=0, N!=1 и теперь начинаем подъем.
5 При подъеме уровни рекурсии постепенно уменьшаются пока мы не дойдем до 0. т.е. не вернемся в ту точку откуда был сделан первый рекурсивный вызов. Мы возвращаемся из функции и в качестве результата будет значение factorial = N*1. Здесь 1 – это результат который мы получили с уровня 5. значение N=1. Следовательно, возвращается из функции значение 1.
4 Вычисляем текущее значение factorial = 2*1
3 Вычисляем текущее значение factorial = 3*2
2 Вычисляем текущее значение factorial = 4*6
1 Итак, мы вернулись к первому вызову рекурсивной функции таким образом мы завершаем подъем и как результат получаем factorial = 5 * 24 = 120
0 Работа рекурсивной функции завершена: результатом 5!= 120
Ключевые признаки рекурсии. Давайте разберем следующий теоретический момент. Когда я в таблице описывал спуск с постепенным нарастанием уровня, то остановился, когда N стало равным нулю. До этого мы определили, что значение 0!=1 по определению, а значение факториала для отрицательных значений не определено. Отсюда есть очень важное следствие: рекурсия всегда имеет терминальную или конечную ветвь. Если мы об этом забудем то, получим нечто похожее на бесконечный цикл, который забирал все ресурсы машины и никогда не завершался сам, ведь вы действительно не хотите этого.

Когда стоит применять рекурсию? На этот вопрос есть очень простой ответ: по возможности никогда. Дело в том, что рекурсия всегда является с точки зрения вычислительных ресурсов слишком дорогой и в ряде ситуаций из-за этого просто не работает. В качестве демонстрации попробуйте запустить приведенные выше фрагменты кода для N = 1, 5 , 10 , 100 , 1000, 1000000. В то время как итеративный алгоритм работает и продолжает работать (правда, начиная с некоторого шага выдает неверный результат из-за переполнения переменной F, дело в том, что факториал – это очень быстрорастущая функция и вскоре ее значение превышает предельные 2 миллиарда для целых чисел в C++), а рекурсивная версия начинает завершаться аварийно с сообщением “stack overflow” – переполнение стека или сообщением о попытке доступа к чужой памяти. И это, не говоря о том, что время вычисления в рекурсивной версии заметно больше чем в итеративной. Тогда у вас должен возникнуть вопрос: а зачем нам нужен подобный инструмент? Да потому что рекурсия гораздо гибче, чем итерация, и я снова вам повторю, что есть такой класс задач, которые не имеют решения без использования рекурсии, или их решение слишком неэффективно.

Как проектировать рекурсивные алгоритмы? Да, это действительно сложный вопрос. Прежде всего, определитесь с самой задачей – какова ее природа. Если вам необходимо найти, например, максимальный элемент в массиве, то это обычный цикл с перебором всех элементов и отбором среди них (разумеется, что всякий итеративный алгоритм можно переписать с помощью рекурсии, и честно говоря, мы будем поступать так достаточно часто, но только ради тренировки, пока не набьем руку, пожалуйста, поступайте в будущем более эффективно). Для демонстрации я приведу далее примеры, той же задачи с поиском максимального элемента.
* Рекурсивное решение Итеративное решение
Концепция Что есть максимальный элемент в массиве? Пусть нам будет как-будто очень сложно ответить на этот вопрос и поэтому мы ищем упрощение. Да тяжело найти максимальный среди N элементов, гораздо проще найти его среди (N-1) элементов, а затем сравнить это значение и первый элемент и определить кто-же на самом деле наибольший. 1) Максимальный элемент в массиве из N элементов есть наибольший из первого и максимального элемента в хвосте массива (2..N) 2) (Это терминальная ветвь, она должна обязательно присутствовать). Очевидно что в массиве состоящем из одного элемента, этот элемент и будет максимальным. 1) Предположим, что MAX – максимальный элемент массива – пусть это будет его первый элемент (или второй, в общем любой). 2) Переберем все оставшиеся элементы и для каждого из них проверим истинность первого предположения: может быть мы ошибались и на самом деле некоторый текущий элемент A[i] более подходит на роль максимального: A[i]> MAX, если данное условие выполняется то исправим нашу “ошибку”, положив: MAX = A [i]
Реализация 
  1. int maxRec (int *arr , int n , int from){
  2. if (from == n-1) return arr [n-1];
  3. return max (arr[from], maxRec(arr, n, from+1) );
  4. }
  5. ...
  6. int arr [] = {1 , 2 , 5 , 3 , 5 , 4};
  7. printf ("max = %d" , maxRec(arr , n , 0));
 
  1. int arr [] = {1 , 2 , 5 , 3 , 5 , 4};
  2. int max = arr [0];
  3. for (int I=1; I < 6; I++)
  4. if (max < arr [i])
  5. max = arr [i];
  6. printf ("max = %d"  , max);
Замечания Когда мы формулируем рекурсивный алгоритм то больше внимания мы уделяем описанию характеристик того что должно получится или как оно выглядит. Рекурсивный алгоритм сводится к самому себе, но всегда чуть более простому и близкому к моменту, когда для решения поставленной задачи рекурсия будет не нужна, решение будет тривиально и достижимо с помощью итерации или иного не рекурсивного приема (терминальная ветвь). Здесь основной упор на определение четкой последовательности действий. Пройдя их от начала до конца, мы достигнем поставленной цели.
Задание: рассмотрите примеры приведенных ниже изображений:



Попробуйте в терминах рекурсии описать алгоритм, который служит для построения данных изображений. Если в ходе изучения C, Pascal вы не прошли графические примитивы то воспользуйтесь псевдо-функцией: линия (Хнач, Yнач, Xконечное, Yконечное).

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

Задача о ханойских башнях (алмазные башни, башни Брахмы) известна давно. Мне стоит сначала рассказать древнюю легенду о том, когда произойдет конец света: В далеком Индокитае бог Брахма построил храм, в котором поставил три алмазных стержня, на один из этих стержней он поместил 64 золотых диска, различного диаметра каждый последующий меньше чем предыдущий. Монахи этого храма уже несколько тысячелетий перекладывают эти диски так чтобы переместить их с первого стержня на второй. Считается, что когда все диски займут свое место, то произойдет конец света. К счастью, для этого потребуется очень много времени. При перекладывании дисков существуют два ограничения:
  • за один раз можно переместить только один диск;
  • нельзя поместить диск большего размера на диск меньшего размер.

В терминах рекурсии решение формулируется очень просто:

Что означает переложить пирамидку размера N со стержня A на стержень B используя в качестве вспомогательного стержень C? Согласитесь что упрощение этой задачи – выполнять перемещение не пирамиды размером N, а размером поменьше, например N-1. Тогда сам алгоритм можно сформулировать, например, так:



Алгоритм перекладывания дисков со стержня ”Источник” на стержень ”Приемник” используя “вспомогательный” стержень.

Начальное состояние: Стержень источник – n дисков расположенных согласно правилу “меньший на больший”. Стержень приемник и вспомогательный стержень пусты.

Алгоритм состоит из трех шагов:

1) Переложить со стержня “источника” пирамиду размером (n-1) дисков на “вспомогательный” стержень. Разумеется, что мы, помня первое ограничение, не имеем права взять за один раз все (n-1) дисков. Но ведь помните основное свойство рекурсии: сводим задачу к самой себе, но чуть более простой: когда мы поставили перед собой задачу перемещения пирамиды из (n-1) диска то у нас есть решение данной задачи, описываемое теми тремя пунктами, которые вы сейчас читаете.

(после этого состояние стержней: на стержне источнике у нас будет 1 диск - самый большой (размер n), на стержне вспомогательном пирамида из (n-1) дисков, разумеется правила не должны быть нарушены – меньший на большем. И на целевом стержне ничего не будет.

2) Перекладываем один диск с “источника” на “целевой” стержень – эта операция примитивна и не требует применения рекурсии как для первого шага.

3) Последний шаг – перемещение пирамиды состоящей из (n-1) диска со “вспомогательного” стержня (куда мы ее поместили на шаге 1) на стержень “приемник”. Здесь также мы выполним обращение алгоритма к самому себе, что значит переложить пирамиду размера (n-1), что является более простым, разумеется, работа с пирамидой размера (n-2).

Не забудьте, основное свойство рекурсии – терминальность. В ситуации, когда нам нужно выполнить перемещение пирамиды состоящей всего из одного диска – нем требуется только пункт # 2, и без всякой рекурсии

Согласитесь, что решение очень простое. А теперь маленькое задание:

Задание: согласно приведенной выше схеме необходимо реализовать программный алгоритм, результатом его работы должен быть список операций (текстовых сообщений с пояснением, что, откуда и куда необходимо перемещать) . В качестве исходных данных должно быть число N – количество дисков.

Categories: Структуры данных и алгоритмы

« Структуры данных и алгоритмы. Теория. Усовершенствованные алгоритмы сортировки Структуры данных и алгоритмы. Теория. Динамические структуры данных »