Рекурсия

Указание пользовательскую коллекцию

Можно указать коллекцию путем реализации интерфейса IEnumerable<T> или IEnumerable. Дополнительные сведения см. в разделах Перечисление коллекции и Практическое руководство. Доступ к классу коллекции с помощью оператора foreach

Хотя можно определить пользовательскую коллекцию, обычно лучше вместо использования коллекции, включенных в платформу.NET Framework, описаны в Kinds of Collections выше в этом разделе.

В следующем примере определяется пользовательский класс с именем коллекции AllColors. Этот класс реализует интерфейс IEnumerable, который требуется, чтобы метод GetEnumerator был реализован.

Метод GetEnumerator возвращает экземпляр класса ColorEnumerator. ColorEnumerator реализует интерфейс IEnumerator, который требует, чтобы были реализованы свойства Current, метод MoveNext, а метод Reset.

private void ListColors()

{

var colors = new AllColors();

foreach (Color theColor in colors)

{

Console.Write(theColor.Name + " ");

}

Console.WriteLine();

}

public class AllColors: System.Collections.IEnumerable

{

Color[] _colors =

{

new Color() { Name = "red" },

new Color() { Name = "blue" },

new Color() { Name = "green" }

};

public System.Collections.IEnumerator GetEnumerator()

{

return new ColorEnumerator(_colors);

}

private class ColorEnumerator: System.Collections.IEnumerator

{

private Color[] _colors;

private int _position = -1;

public ColorEnumerator(Color[] colors)

{

_colors = colors;

}

object System.Collections.IEnumerator.Current

{

get

{

return _colors[_position];

}

}

bool System.Collections.IEnumerator.MoveNext()

{

_position++;

return (_position < _colors.Length);

}

void System.Collections.IEnumerator.Reset()

{

_position = -1;

}

}

}

public class Color

{public string Name { get; set; }

}

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

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

Давайте рассмотрим, что же такое рекурсия.

Рекурсивная задача в общем случае разбивается на ряд этапов. Для решения задачи вызывается рекурсивная функция. Эта функция знает, как решать только простейшую часть задачи - так называемую базовую задачу (или несколько таких задач). Если эта функция вызывается для решения базовой задачи, она просто возвращает результат. Если функция вызывается для решения более сложной задачи, она делит эту задачу на две части: одну часть, которую функция умеет решать, и другую, которую функция решать не умеет. Чтобы сделать рекурсию выполнимой, последняя часть должна быть похожа на исходную задачу, но быть по сравнению с ней несколько проще или несколько меньше. Поскольку эта новая задача подобна исходной, функция вызывает новую копию самой себя, чтобы начать работать над меньшей проблемой - это называется рекурсивным вызовом, или шагом рекурсии. Шаг рекурсии включает ключевое слово return, так как в дальнейшем его результат будет объединен с той частью задачи, которую функция умеет решать, и сформируется конечный результат, который будет передан обратно в исходное место вызова, возможно, в main.

Шаг рекурсии выполняется до тех пор, пока исходное обращение к функции не закрыто, т.е. пока еще не закончено выполнение функции. Шаг рекурсии может приводить к большому числу таких рекурсивных вызовов, поскольку функция продолжает деление каждой новой подзадачи на две части. Чтобы завершить процесс рекурсии, каждый раз, как функция вызывает саму себя с несколько упрощенной версией исходной задачи, должна формироваться последовательность все меньших и меньших задач, в конце концов сходящаяся к базовой задаче. В этот момент функция распознает базовую задачу, возвращает результат предыдущей копии функции и последовательность возвратов повторяет весь путь назад, пока не дойдет до первоначального вызова и не возвратит конечный результат в функцию main.

В качестве примера рассмотрим одну из задач домашнего задания, а именно: вычисление факториала. Напомним, факториал неотрицательного целого числа n, записываемый как n!, равен n*(n-1)*(n-2)*...*1

n! = n*(n-1)*(n-2)*...*1

причем считается, что 1! = 1 и 0! = 1. Например, 5! вычисляется как произведение 5*4*3*2*1 и равен 120.

Факториал целого числа, number, большего или равного 0, может быть вычислен итеративно (нерекурсивно), например, с помощью оператора for следующие образом:

factorial = 1; for (int counter = number; counter >=1; counter--) factorial *= counter;

Рекурсивное определение функции факториал дается следующим соотношением: n!=n*(n-1)! Например, факториал 5! очевидно равен 5*4!. В самом деле: 5!=5*4*3*2*1 5!=5*(4*3*2*l) 5!=5*4!

Вычисление 5! должно происходить в соответствии с рисунком.

Дата добавления: 2014-01-14