Рекурсивные алгоритмы
Рекурсивным называется способ построения объекта, в котором определение объекта включает аналогичный объект в виде некоторой его части.
Любое рекурсивное определение состоит из двух частей: базовой и рекурсивной.
Базовая часть является не рекурсивной и задает определение для некоторой фиксированной части объектов.
Рекурсивная часть определяет понятие через него же и записывается так, чтобы при цепочке повторных применений она сводилась бы к базовой части.
Пример.
Определение 1 (базовая часть).
3 барана – это стадо.
Определение 2 (рекурсивная часть).
Стадо из n баранов – это стадо из n – 1 барана и еще одного.
Вопрос: является ли стадом группа из пяти баранов?
Обозначим стадо из пяти баранов – Стадо5.
Объект Стадо5 не удовлетворяет первому пункту определения, поскольку пять баранов – это не три.
Согласно второму пункту Стадо5 – стадо, если там есть один баран и остальная часть (Стадо4) – тоже стадо баранов.
Решение относительно объекта Стадо5 откладывается, пока не будет принято решение относительно Стадо4.
Объект Стадо4 также не подходит под первый пункт.
Согласно второму пункту Стадо4 – стадо, если там есть один баран и остальная часть (Стадо3) – тоже стадо баранов.
Решение относительно объекта Стадо4 откладывается.
Объект Стадо3 удовлетворяет первому пункту определения, и значит Стадо3 – стадо.
Теперь и о Стадо4 можно утверждать, что это стадо, а значит, и Стадо5 является стадом.
Функция называется рекурсивной, если ее значение для данного аргумента определяется через значения той же функции для предшествующих аргументов.
Войдя в рекурсивную функцию (программу), процесс движется по тексту программы до тех пор, пока не встретит ее вызов, после чего опять начнет выполняться та же самая функция сначала.
При этом копируются формальные, фактические параметры, локальные переменные и точка возврата.
Каждый новый рекурсивный вызов порождает новый "экземпляр" формальных параметров и локальных переменных, причем старый "экземпляр" не уничтожается, а сохраняется.
Программа рекурсивной функции не меняется, она присутствует в памяти компьютера в единственном экземпляре.
Рекурсия должна иметь внутри себя условие завершения.
Таким образом, рекурсия – мощный механизм, но затратный по времени и по памяти.
При решении конкретных задач надо делать выбор в пользу рекурсии или циклов, исходя из особенностей задачи.
Если задача несложно решается итеративно, рекурсию использовать не стоит. Однако если задача заключается в работе с рекурсивными структурами данных или сама природа задачи рекурсивна, нет смысла отказываться от рекурсии. Но следует иметь в виду затраты на рекурсивные вызовы и стараться избегать их.
Рекурсивная функция (программа) может быть:
линейной (функция содержит единственный вызов самой себя);
смешанной (две или более функций вызывают друг друга попеременно);
ветвящейся (когда рекурсивный вызов содержится в теле функции более одного раза, либо производится в цикле);
вложенной (имеется вызов функции внутри обращения к самой функции).
Линейная рекурсия
Функция содержит единственный вызов самой себя.
В таком случае рекурсия становится эквивалентной циклу. Любой циклический алгоритм можно преобразовать в линейно-рекур-сивный и наоборот.
Пример.
n! = 1∙2∙3… n
n! = n∙(n - 1)!
Циклический алгоритм вычисления факториала:
Int fact(int n)
{ for (int s = 1; n != 0; n--)
s *= n;
return s;
}
Рекурсивный алгоритм вычисления факториала:
Int fact(int n)
{ if (n == 1) return 1;
return n * fact(n - 1);
}
Пусть n = 3. Вызывается fact(3). fact = 3∙ fact(2).
Работа функции fact(3) приостанавливается и вызывается fact(2). fact = 2∙ fact(1).
Работа функции fact(2) приостанавливается. В памяти две копии формальных, фактических параметров, локальных переменных и точек возврата.
Вызывается и работает третья копия.
Для n = 1 fact = 1.
Работа fact(1) завершена.
Выполняется fact(2) = fact(1)∙2 = 1∙2 = 2
Работа fact(2) завершена.
Выполняется fact(3) = fact(2)∙3 = 2∙3 = 6.
Работа fact(3) завершена.
Пример. Разработать рекурсивный алгоритм вычисления квадрата натурального числа
Известно, что (n + 1)2 = n2 + 2 * n + 1 и 12 = 1,
отсюда
| 1, если n = 1;
kv(n) = |
| kv(n - 1) + 2(n - 1) + 1, если n > 1
int kv(int i)
{ if (i == 1)
return 1;
else
return kv(i - 1) + 2 * (i - 1) + 1;
}
Void main()
{ int i;
for(i = 1; i < 10; i++)
cout<<kv(i)<<endl;
}
Смешанная рекурсия
При этом виде рекурсии две или более функций вызывают друг друга попеременно.
Пример. Определить, является ли введенное с клавиатуры число четным.
четное
нечетное
#include <iostream>
using namespace std;
bool isEven(int n);
bool isOdd(int n);
Void main()
{ int n; bool m;
cout<<"Enter number ";
cin>>n;
m = isEven(n);
if(m == true)
cout<<"Number is Even";
else
cout<<"Number is Odd";
}
bool isEven(int n)
{ if(n == 0) //условие окончания
return true;
else
return isOdd(n - 1);
}
bool isOdd(int n)
{ if(n == 0)
return false;
else
return isEven(n - 1);
}
Ветвящаяся рекурсия
Функция вызывается более одного раза внутри рекурсивной функции.
Рассмотрим на примере вычисления числа Фибоначчи.
Последовательность Фибоначчи обладает свойством: каждый следующий член является суммой двух предыдущих.
int Fib (int n)
{ if (n == 0)
return 0;
else
if (n == 1)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
Void main()
{ int i;
for(i = 0; i < 10; i++)
cout<<Fib(i)<<' ';
}
Вложенная (гнездовая) рекурсия
Такая рекурсия обычно не может быть выражена через цикл.
Рассмотрим программу вычисления функции Аккермана
Функция вызывает сама себя три раза.
#include <iostream>
using namespace std;