Tooprogram.ru

Компьютерный справочник
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Рекурсия си шарп

Зачем использовать рекурсии в C#?

Только подобрался к использованию рекурсий, и практически сразу возник сабжевый вопрос.

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

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

А вот если описать сложение, скажем, коллекции целых чисел, то разница огромная, и не в пользу рекурсии.

Я допускаю, что описываю криво, но пока ничего лучше родить не смог. Итак, есть класс SomeNums, реализующий IEnumerable(int); в нём есть список num, хранящий собственно множество.

И вот я где-нибудь в Main делаю так:

А затем замеряю время и по сто раз произвожу сложение каждым из способов. Считаю среднее, и (вполне ожидаемо, в общем-то) получаю вывод:

  • Среднее время для рекурсии: 0,034 468
  • Среднее время для цикла: 0,006 387

И, конечно, если я попробую увеличить количество членов множества, то получу переполнение стека.

Я понимаю, что использовать рекурсию так, как это делаю я — некорректно. Но есть ли корректные способы? В общем, есть ли смысл использования рекурсии в C#?

И да, я в курсе, что есть LINQ с его Aggregate, но пост не об этом.

2 ответа 2

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

Кроме того, рекурсия нередко применяется в алгоритмах, там где результат вычисления зависит от результата той же функции вызванной с другими параметрами или там где сложно заранее задать число итераций. Например — quicksort. Даже математические формулы можно выразить с помощью рекуррентной формулы. Взять тот же факториал:

Это объясняет почему вычисление факториала так популярно в учебных материалах.

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

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

Рекурсия

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

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

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

Читать еще:  Что такое дизассемблер

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

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

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

Этот пример приводят для пояснения связи между циклом и рекурсией. В рекурсивном методе fakt(n) мы видим две ветви (n 0). Отметим, что можно выразить n! через (n-1)! : n!=n*(n-1)! . Это выражение совпадает со 2 ветвью рекурсии.

Честно говоря, этого примера недостаточно, чтобы убедить вас использовать рекурсивный метод. Если можете написать циклический алгоритм — то всегда используйте только его. Однако есть забавная задача, которая решается только через рекурсию (мне не попадалось ее решение через цикл для произвольного n) — это Ханойские башни:

«Требуется за минимальное число операций переложить n алмазных колец разного диаметра пирамидки с 1-й на 3-ю через 2-ю иглу. Запрещено перекладывать более одного кольца за одну операцию и помещать кольцо большего диаметра над меньшим (в целях сохранности). В исходном положении — все кольца на игле 1, в конечном — на игле 3 имеют форму пирамиды» :

Минимальное число операций равно 2 n -1. Попробуйте придумать более быстрый алгоритм, не изменяя условия задачи. При n=30 мы имеем более 1 миллиарда операций.

А вот практический пример применения рекурсии — закрашивание замкнутой области:

Основная идея рекурсии заложена в func(char[][] b, int x, int y): проверка соседних клеток на предмет возможности закрашивания произвольной замкнутой области.

Отмечу, что в языке логического программирования Prolog конструкции типа цикла могут быть реализованы только через рекурсию.

Завершим раздел рассмотрением двух из трех ключевых принципов ООП — наследования и полиморфизма, считаю принцип инкапсуляции уже достаточно ясным.

Урок №107. Рекурсия и Числа Фибоначчи

Обновл. 31 Дек 2019 |

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

Рекурсия

Рекурсивная функция (или просто «рекурсия») в C++ — это функция, которая вызывает саму себя. Например:

При вызове countOut(4) на экран выведется push 4 , а затем вызовется countOut(3). countOut(3) выведет push 3 и вызовет countOut(2). Последовательность вызова countOut(n) других функций countOut(n-1) повторяется бесконечное количество раз (аналог бесконечного цикла). Попробуйте запустить у себя.

В уроке №105 мы узнали, что при каждом вызове функции, определённые данные помещаются в стек вызовов. Поскольку функция countOut() никогда ничего не возвращает (она просто снова вызывает countOut()), то данные этой функции никогда не вытягиваются из стека! Следовательно, в какой-то момент память стека закончится и произойдёт переполнение стека.

Условие завершения рекурсии

Рекурсивные вызовы функций работают так же, как и обычные вызовы функций. Однако, программа выше иллюстрирует наиболее важное отличие простых функций от рекурсивных: вы должны указать условие завершения рекурсии, в противном случае функция будет выполняться «бесконечно» (фактически, до тех пор, пока не исчерпается память в стеке вызовов). Условие завершения рекурсии — это условие, которое, при его выполнении, остановит вызов рекурсивной функции саму себя.

В этом условии обычно используется оператор if. Вот пример функции выше, но уже с условием завершения рекурсии (и ещё с одним дополнительным выводом текста):

Когда мы запустим эту программу, то countOut() начнёт выводить:

push 4
push 3
push 2
push 1

Если сейчас посмотреть на стек вызовов, то увидим следующее:

countOut(1)
countOut(2)
countOut(3)
countOut(4)
main()

Из-за условия завершения, countOut(1) не вызовет countOut(0): условие if не выполнится, и поэтому выведется pop 1 и countOut(1) завершит своё выполнение. На этом этапе countOut(1) вытягивается из стека, и управление возвращается к countOut(2). countOut(2) возобновляет выполнение в точке после вызова countOut(1), и поэтому выведется pop 2 , а затем countOut(2) завершится. Рекурсивные вызовы функций countOut постепенно вытягиваются из стека до тех пор, пока не будут удалены все экземпляры countOut.

Читать еще:  Час в рамках системы си является

Таким образом, результат выполнения программы выше:

push 4
push 3
push 2
push 1
pop 1
pop 2
pop 3
pop 4

Стоит отметить, что push выводится в порядке убывания, а pop — в порядке возрастания. Дело в том, что push выводится до вызова рекурсивной функции, а pop выполняется (выводится) после вызова рекурсивной функции, когда все экземпляры countOut вытягиваются из стека (что происходит в обратном порядке, в котором эти экземпляры были введены).

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

Рассмотреть рекурсию с первого взгляда на код не так уж и легко. Лучшим вариантом будет посмотреть, что произойдёт при вызове рекурсивной функции с определённым значением. Например, посмотрим, что произойдёт при вызове функции выше с value = 4 :

sumCount(4). 4 > 1, поэтому возвращается sumCount(3) + 4
sumCount(3). 3 > 1, поэтому возвращается sumCount(2) + 3
sumCount(2). 2 > 1, поэтому возвращается sumCount(1) + 2
sumCount(1). 1 = 1, поэтому возвращается 1. Это условие завершения рекурсии

Теперь посмотрим на стек вызовов:

sumCount(1) возвращает 1
sumCount(2) возвращает sumCount(1) + 2, т.е. 1 + 2 = 3
sumCount(3) возвращает sumCount(2) + 3, т.е. 3 + 3 = 6
sumCount(4) возвращает sumCount(3) + 4, т.е. 6 + 4 = 10

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

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

Рекурсивные функции обычно решают проблему, сначала найдя решение для подмножеств проблемы (рекурсивно), а затем модифицируя это «подрешение», дабы добраться уже до верного решения. В примере выше алгоритм sumCount(value) сначала решает sumCount(value-1), а затем добавляет значение value , чтобы найти решение для sumCount(value).

Во многих рекурсивных алгоритмах некоторые данные ввода производят предсказуемые данные вывода. Например, sumCount(1) имеет предсказуемый вывод 1 (вы можете легко это вычислить и проверить самостоятельно). Случай, когда алгоритм при определённых данных ввода производит предсказуемые данные вывода, называется базовым случаем. Базовые случаи работают как условия для завершения выполнения алгоритма. Их часто можно идентифицировать, рассматривая результаты вывода для следующих значений ввода: 0 , 1, « » или null .

Числа Фибоначчи

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

Спираль Фибоначчи выглядит следующим образом:

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

F(n) = 0, если n = 0
1, если n = 1
f(n-1) + f(n-2), если n > 1

Следовательно, довольно просто написать рекурсивную функцию для вычисления n-го числа Фибоначчи:

Рекурсия си шарп

В этом полном руководстве по C# 4.0 — языку программирования, разработанному специально для среды .NET, — детально рассмотрены все основные средства языка: типы данных, операторы, управляющие операторы, классы, интерфейсы, методы, делегаты, индексаторы, события, указатели, обобщения, коллекции, основные библиотеки классов, средства многопоточного программирования и директивы препроцессора. Подробно описаны новые возможности C#, в том числе PLINQ, библиотека TPL, динамический тип данных, а также именованные и необязательные аргументы. Это справочное пособие снабжено массой полезных советов авторитетного автора и сотнями примеров программ с комментариями, благодаря которым они становятся понятными любому читателю независимо от уровня его подготовки.

Книга рассчитана на широкий круг читателей, интересующихся программированием на C#.Введите сюда краткую аннотацию

Книга: C# 4.0: полное руководство

Рекурсия

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

Читать еще:  Внеочередная поверка си проводится в случаях

Классическим примером рекурсии служит вычисление факториала числа. Факториал числа N представляет собой произведение всех целых чисел от 1 до N. Например, факториал числа 3 равен 1х2×3, или 6. В приведенном ниже примере программы демонстрируется рекурсивный способ вычисления факториала числа. Для сравнения в эту программу включен также нерекурсивный вариант вычисления факториала числа.

// Простой пример рекурсии.
using System;
class Factorial <
// Это рекурсивный метод.
public int FactR(int n) <
int result;
if (n == 1) return 1;
result = FactR(n — 1) * n;
return result;
>
// Это итерационный метод.
public int FactI(int n) <
int t, result;
result = 1;
for (t = 1; t

Factorial f = new Factorial();

Console.WriteLine(«Факториалы, рассчитанные рекурсивным методом.»);
Console.WriteLine(«Факториал числа 3 равен » + f.FactR(3));
Console.WriteLine(«Факториал числа 4 равен » + f.FactR(4));
Console.WriteLine(«Факториал числа 5 равен » + f.FactR(5));
Console.WriteLine();
Console.WriteLine(«Факториалы, рассчитанные итерационным методом.»);
Console.WriteLine(«Факториал числа 3 равен » + f.FactR(3));
Console.WriteLine(«Факториал числа 4 равен » + f.FactR(4));
Console.WriteLine(«Факториал числа 5 равен » + f.FactR(5));
>
>

При выполнении этой программы получается следующий результат.

Факториалы, рассчитанные рекурсивным методом.
Факториал числа 3 равен 6
Факториал числа 4 равен 24
Факториал числа 5 равен 120
Факториалы, рассчитанные итерационным методом.
Факториал числа 3 равен 6
Факториал числа 4 равен 24
Факториал числа 5 равен 120

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

А рекурсивный метод FactR() действует по более сложному принципу. Если метод FactR() вызывается с аргументом 1, то он возвращает значение 1. В противном случае он возвращает произведение FactR(n-1)*n . Для вычисления этого произведения метод FactR() вызывается с аргументом n-1. Этот процесс повторяется до тех пор, пока значение аргумента n не станет равным 1, после чего из предыдущих вызовов данного метода начнут возвращаться полученные значения. Например, когда вычисляется факториал числа 2, то при первом вызове метода FactR() происходит второй его вызов с аргументом 1. Из этого вызова возвращается значение 1, которое затем умножается на 2 (первоначальное значение аргумента n). В итоге возвращается результат 2, равный факториалу числа 2 (1×2). Было бы любопытно ввести в метод FactR() операторы, содержащие вызовы метода WriteLine(), чтобы наглядно показать уровень рекурсии при каждом вызове метода FactR(), а также вывести промежуточные результаты вычисления факториала заданного числа.

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

Ниже приведен еще один пример рекурсии для вывода символьной строки в обратном порядке. Эта строка задается в качестве аргумента рекурсивного метода DisplayRev() .

// Вывести символьную строку в обратном порядке, используя рекурсию.
using System;
class RevStr <
// Вывести символьную строку в обратном порядке.
public void DisplayRev(string str) <
if (str.Length > 0)
DisplayRev(str.Substring(1, str.Length — 1));
else
return;
Console.Write(str[0]);
>
>
class RevStrDemo <
static void Main() <
string s = «Это тест»;

RevStr rsOb = new RevStr();

Ссылка на основную публикацию
Adblock
detector