Рекурсия, как альтернатива циклу, является одним из полезных средств в арсенале программиста, но содержит в себе «подводные камни». Попробуем разобраться, когда она бывает эффективна.
Простейший пример рекуррентного соотношения: F(0)=1, F(1)=1*F(0), F(2)=2*F(1), … , F(n)=n*F(n-1). Как Вы понимаете, это вычисление факториала. Но можно эти соотношения записать короче: F(n)=n*F(n-1) для n=1,2,…,N, причем F(0)=1.
Рекуррентные соотношения могут быть реализованы как через цикл (от начала к концу), так и через рекурсию (от конца к началу). Часто используют такие структуры данных, для которых целесообразно применять рекурсивные методы при написании программ.
Рекурсивные методы удобны при работе с рекурсивными структурами данных — списками, деревьями.
Примеры применения рекурсивных методов: вычисление факториала, Ханойские башни, закрашивание замкнутой области (см. ниже), подсчет числа слов в тексте, поиск пути в лабиринте, обход деревьев, обработка списков.
Необходимые определения
Метод P называется рекурсивным, если при выполнении тела метода происходит вызов метода P.
Рекурсия может быть прямой, если вызов P происходит непосредственно в теле метода P.
Рекурсия может быть косвенной, если в теле P вызывается метод Q (эта цепочка может быть продолжена), в теле которого вызывается метод P.
Важно! Для того чтобы рекурсия не приводила к зацикливанию, в тело нормального рекурсивного метода всегда встраивается оператор выбора, одна из ветвей которого не содержит рекурсивных вызовов.
Если в теле рекурсивного метода рекурсивный вызов встречается только один раз, значит, что рекурсию можно заменить обычным циклом, что приводит к более эффективной программе, поскольку реализация рекурсии требует временных затрат и работы со стековой памятью.
Приведем традиционный пример рекурсивного определения функции, вычисляющей
Факториал целого числа
// Вычисление факториала в цикле и рекурсивно
// n! = 1*2*3*...*(n-1)*n 0!=1 (ро определению)
// Поясните, почему правильный результат только для n<21 ?
using System;
namespace factorial
{
class Program
{
static void Main(string[] args)
{
// для наглядности введем 10 разных n
for (int i = 0; i < 10; i++)
{
Console.Write("Введите n= ");
int a = Convert.ToInt32(Console.ReadLine());
Console.WriteLine(fact(a));
Console.WriteLine(fakt(a));
Console.ReadKey();
}
}
// Факториал через цикл
static Int64 fact(int n)
{
Int64 f = 1;
for (int i = 1; i <= n; i++)
f = f * i;
return f;
}
// Факториал через рекурсию
static Int64 fakt(int n)
{
Int64 f;
if (n < 1)
f = 1;
else
f = fakt(n - 1) * n;
return f;
}
}
}
Этот пример приводят для пояснения связи между циклом и рекурсией. В рекурсивном методе fakt(n) мы видим две ветви (n<1) и (n>0). Отметим, что можно выразить n! через (n-1)! : n!=n*(n-1)! . Это выражение совпадает со 2 ветвью рекурсии.
Честно говоря, этого примера недостаточно, чтобы убедить вас использовать рекурсивный метод. Если можете написать циклический алгоритм — то всегда используйте только его. Однако есть забавная задача, которая решается только через рекурсию (мне не попадалось ее решение через цикл для произвольного n) — это
Ханойские башни:
«Требуется за минимальное число операций переложить n алмазных колец разного диаметра пирамидки с 1-й на 3-ю через 2-ю иглу. Запрещено перекладывать более одного кольца за одну операцию и помещать кольцо большего диаметра над меньшим (в целях сохранности). В исходном положении — все кольца на игле 1, в конечном — на игле 3 имеют форму пирамиды» :
using System;
namespace HanoiTowers
{
class Program
{
static void Main(string[] args)
{
Console.Write("n="); // число алмазных колец
int n = Convert.ToInt32(Console.ReadLine());
hanoi(n, '1', '2', '3'); // Вызов. Иглы 1,2,3
Console.ReadKey();
}
// Рекурсивная функция
static void hanoi(int n, char a, char b, char c )
{
if (n < 2)
Console.WriteLine(a.ToString() + "->" + c.ToString());
else
{
hanoi(n - 1, a, c, b);
Console.WriteLine(a.ToString() + "->" + c.ToString());
hanoi(n - 1, b, a, c);
}
}
}
}
Минимальное число операций равно 2n-1. Попробуйте придумать более быстрый алгоритм, не изменяя условия задачи. При n=30 мы имеем более 1 миллиарда операций.
А вот практический пример применения рекурсии —
Закрашивание замкнутой области
// Рекурсивное закрашивание
using System;
namespace Закрашивание
{
class Program
{
static void Main()
{
// Задание границ звездочками 13х16
string[] a ={" *** *** ",
" * *** * ",
" * * ",
" * * ",
"* *** *",
"* * * *",
"* * * *",
"* * * *",
"* * * *",
"* * * *",
"* *** *",
"* *",
"***************"};
char[][] b = new char[a.Length][]; // массив b через конструктор
// заполнение массива b[][] строками a[]
for (int y = 0; y < a.Length; y++) b[y] = a[y].ToCharArray();
print(b); // вывод незакрашенной картинки
Console.WriteLine();
// стартовая позиция кисти, попробуй (6,8) и другие !!!
func(b, 3, 8);
print(b); // Вывод после закраски
Console.ReadKey();
}
// Рекурсивное заполнение пробелов символом 'X'
static void func(char[][] b, int x, int y)
{
b[y][x] = 'X';
if (b[y - 1][x] == ' ') func(b, x, y - 1);
if (b[y][x + 1] == ' ') func(b, x + 1, y);
if (b[y + 1][x] == ' ') func(b, x, y + 1);
if (b[y][x - 1] == ' ') func(b, x - 1, y);
}
// покраска в три цвета
static void print(char[][] b)
{
for (int y = 0; y < b.GetLength(0); y++)
{
for (int x = 0; x < b[y].Length; x++)
{
// Console.Write(b[y][x]);
if (b[y][x] == ' ') Console.BackgroundColor = ConsoleColor.Green;
if (b[y][x] == '*') Console.BackgroundColor = ConsoleColor.Yellow;
if (b[y][x] == 'X') Console.BackgroundColor = ConsoleColor.Blue;
Console.Write(" ");
}
Console.WriteLine();
}
}
}
}
Основная идея рекурсии заложена в func(char[][] b, int x, int y): проверка соседних клеток на предмет возможности закрашивания произвольной замкнутой области.
Пример косвенной рекурсии
Даны рекуррентные соотношения:
Cn = Cn-1*x –Sn-1*y,
Sn= Sn-1*x + Cn-1*y,
где:
n = 2, 3, …, N;
x и y – числа, связанные соотношением x2+y2=1;
C1 = x, S1 = y.
Требуется:
- Через рекуррентные соотношения, используя цикл, найти CN и SN.
- Записать решение, используя косвенную рекурсию.
- Сравнить время выполнения алгоритмов для N = 10, 11, … , 32.
Решение
class Program
{
static double x;
static double y;
static void Main()
{
Console.Write("Введите x ( |x| <= 1 ) : ");
x = Convert.ToDouble(Console.ReadLine());
y = Math.Sqrt(1-x*x);
Console.Write("Введите N: ");
int n = Convert.ToInt32(Console.ReadLine());
// через рекурентные соотношения
DateTime t1 = DateTime.Now;
double C = x, C0;
double S = y, S0;
for (int k = 2; k <= n; k++) { C0 = C; S0 = S; C = C0 * x - S0 * y; S = S0 * x + C0 * y; } Console.WriteLine("Результат через рекуррентные соотношения: C = {0}, S = {1}.", C, S); DateTime t2 = DateTime.Now; int w = t2.Minute * 60 + t2.Second - t1.Minute * 60 - t1.Second; Console.WriteLine("Время в секундах: " + w); // через рекурсию t1 = DateTime.Now; Console.WriteLine("Результат через косвенную рекурсию: C = {0}, S = {1}.", CR(n), SR(n)); t2 = DateTime.Now; w = t2.Minute * 60 + t2.Second - t1.Minute * 60 - t1.Second; Console.WriteLine("Время в секундах: " + w); Console.ReadKey(); } // косвенная рекурсия static double CR(int n) { double c; if (n > 1)
c = CR(n - 1) * x - SR(n - 1) * y;
else
c = x;
return c;
}
static double SR(int n)
{
double s;
if (n > 1)
s = SR(n - 1) * x + CR(n - 1) * y;
else
s = y;
return s;
}
}
Отмечу, что в языке логического программирования Prolog конструкции типа цикла могут быть реализованы только через рекурсию.
Завершим раздел рассмотрением двух из трех ключевых принципов ООП — наследования и полиморфизма, считаю принцип инкапсуляции уже достаточно ясным.
NEW: Наш Чат, в котором вы можете обсудить любые вопросы, идеи, поделиться опытом или связаться с администраторами.