Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Рекурсия. Рекурсией программисты на своём мунспике называют вызов функцией самой себя прямо (в теле функции расположен вызов себя) или косвенно (функция вызывает




Читайте также:
  1. Рекурсия

Рекурсией программисты на своём мунспике называют вызов функцией самой себя прямо (в теле функции расположен вызов себя) или косвенно (функция вызывает функцию, которая вызывает функцию, которая… и в одной из этих функций расположен вызов самой первой функции). У хорошей, годной рекурсии должно быть и условие для выхода из рекурсии, иначе получается зацикливание. Типичным примером функций, использующих рекурсию, являются вычисление факториала и функция Аккермана. В более общем смысле, включение некоторой сущностью самой себя целиком (см. пример с зеркалами ниже). Более сложный вариант: «Чтобы понять рекурсию, нужно сперва понять рекурсию».

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("{0}! = {1}",i,factorial(i)); } catch (FormatException) { Console.WriteLine("Неккоректное число"); goto label1; } Console.ReadLine(); } }}

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

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



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

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


Дата добавления: 2015-01-05; просмотров: 14; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.011 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты