Рекурсивные алгоритмы си шарп

Рекурсивные методы

уважаемые посетители блога, если Вам понравилась, то, пожалуйста, помогите автору с лечением. Подробности тут.

Рекурсивный метод — это метод, который вызывает сам себя. Также, в литературе вы можете встретить понятие «рекурсивная функция». Применительно к языку программирования C# эти два понятия равнозначны. Использование рекурсии позволяет сократить исходный код программы и, иногда, сделать его более понятным.

Классический пример рекурсии — вычисление факториала

Вычисление факториала числа — это, видимо, самая популярная задача, решаемая практически всеми студентами на всевозможных языках программирования. Из курса математики мы знаем, что:

1. факториал 0 равен 1
2. факториал 1 равен 1
3. факториал отрицательного числа не существует
4. факториал положительного числа, например, 5 будет равен 1*2*3*4*5 = 120 и записывается как 5! = 1*2*3*4*5 = 120

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

static int Factorial(int n)

и, затем, вызвать этот метод в своей программе, например, так:

static void Main(string[] args)

Что необходимо знать, чтобы рекурсивный метод работал. Во-первых, рекурсивный метод обязательно должен содержать в себе условие выхода из метода. В примере с факториалом — это условие if :

как только n станер равной 1 или в метод передадут 0 , то работа метода завершается — срабатывает оператор return . Во-вторых, исходя из определения рекурсивного метода, где-то в методе должен быть вызов самого себя. В нашем случае, вызов осуществляется в этой строке:

Схематично, работу метода вычисления факториала можно представить следующим образом (на примере 3!)

На каждом шаге выполнения метода до достижения условия выхода из рекурсии в стеке создается запись о вычислении. Как только достигается условие выхода, записи возвращаются из стека и производится окончательное вычисление значения метода. Проверить это можно, запустив приложение и установив точку останова на вызове метода Factorial .

Недостатки рекурсивных методов

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

Сложность отладки рекурсивных методов

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

Попадание в бесконечную рекурсию и переполнение стека

Как было указано выше, одним из главнейших условий при разработке рекурсивного метода — это наличие условия выхода из метода (или, как ещё говорят — базового сценария). Если рекурсивный метод достаточно большой, то можно упустить этот момент и тогда метод будет вызывать себя до тех пор, пока не произойдет переполнение стека. Например, уберем из нашего метода условие if и попробуем запустить программу. Достаточно быстро вы увидите в консоли вместо решения ошибку вот такого плана:

При этом, чем больше будет в рекурсивном методе различных вычислений, тем быстрее произойдет переполнение стека.

Большее время выполнения по сравнению с обычными методами

Обычно, на выполнение рекурсивного метода затрачивается большее количество времени, чем на нерекурсивный метод. Например, перепишем вычисление факториала с использованием обычного цикла for :

static long Factorial_2(int n)

и теперь сравним скорость работы этих методов, например, на вычислении факториала 20 (результат должен быть равен 2 432 902 008 176 640 000 ). Ниже представлен результат измерения времени в тактах:

Даже на таком простом примере видно, что метод вычисления факториала без рекурсии справился с задачей на порядок быстрее.

Итого

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

уважаемые посетители блога, если Вам понравилась, то, пожалуйста, помогите автору с лечением. Подробности тут.

Источник

Рекурсивные алгоритмы си шарп

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

Рекурсивная функция факториала

Возьмем, к примеру, вычисление факториала, которое использует формулу n! = 1 * 2 * … * n . То есть по сути для нахождения факториала числа мы перемножаем все числа до этого числа. Например, факториал числа 4 равен 24 = 1 * 2 * 3 * 4 , а факторил числа 5 равен 120 = 1 * 2 * 3 * 4 * 5 .

Определим метод для нахождения факториала:

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

На уровне языка программирования для возвращения базового варианта применяется оператор return :

То есть, если вводимое число равно 1, то возвращается 1

Другая особенность рекурсивных функций: все рекурсивные вызовы должны обращаться к подфункциям, которые в конце концов сходятся к базовому варианту:

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

int Factorial(int n) < if (n == 1) return 1; return n * Factorial(n - 1); >int factorial4 = Factorial(4); // 24 int factorial5 = Factorial(5); // 120 int factorial6 = Factorial(6); // 720 Console.WriteLine($"Факториал числа 4 = "); Console.WriteLine($"Факториал числа 5 = "); Console.WriteLine($"Факториал числа 6 = ");

Рассмотрим поэтапно, что будет в случае вызова Factorial(4) .

Сначала идет проверка, равно ли число единице:

В реальности выливается в

Рекурсивная функция Фибоначчи

Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фибоначчи. n-й член последовательности Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. То есть последовательность Фибоначчи будет выглядеть так 0 (0-й член), 1 (1-й член), 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . Для определения чисел этой последовательности определим следующий метод:

int Fibonachi(int n) < if (n == 0 || n == 1) return n; return Fibonachi(n - 1) + Fibonachi(n - 2); >int fib4 = Fibonachi(4); int fib5 = Fibonachi(5); int fib6 = Fibonachi(6); Console.WriteLine($"4 число Фибоначчи = "); Console.WriteLine($"5 число Фибоначчи = "); Console.WriteLine($"6 число Фибоначчи = ");

Здесь базовый вариант выглядит следующий образом:

То есть, если мы ищем нулевой или первый элемент последовательности, то возвращается это же число — 0 или 1. Иначе возвращается результат выражения Fibonachi(n — 1) + Fibonachi(n — 2);

Рекурсии и циклы

Это простейшие пример рекурсивных функций, которые призваны дать понимание работы рекурсии. В то же время для обоих функций вместо рекурсий можно использовать циклические конструкции. И, как правило, альтернативы на основе циклов работают быстрее и более эффективны, чем рекурсия. Например, вычисление чисел Фибоначчи с помощью циклов:

static int Fibonachi2(int n) < int result = 0; int b = 1; int tmp; for (int i = 0; i < n; i++) < tmp = result; result = b; b += tmp; >return result; >

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

Источник

Рекурсия

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

Классическим примером рекурсии служит вычисление факториала числа:

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 < class Program < // Рекурсивный метод static int factorial(int i) < int result; if (i == 1) return 1; result = factorial(i - 1) * i; return result; >static void Main(string[] args) < label1: Console.WriteLine("Введите число: "); try < int i = int.Parse(Console.ReadLine()); Console.WriteLine("! = ",i,factorial(i)); > catch (FormatException) < Console.WriteLine("Некорректное число"); goto label1; >Console.ReadLine(); > > >

Обратите внимание, что рекурсивный метод factorial вызывает сам себя, при этом переменная i с каждым вызовом уменьшается на 1.

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

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

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

Источник